算法高级教程2.5MonteCarloalgorithms.pptVIP

* if q is not too large, then the fingerprinting Iq(x) can be sent as a short string. The number of bits to be transmitted is thus O(logq). If Iq(x) ≠ Iq(y), then obviously x ≠y. Let Xj be Monte Carlo is similar to brute-force algorithm, but instead of comparing the pattern Y with Xj , compares the fingerprint Iq(Y) with Iq(Xj) The key step of this Monte Carlo algorithm is how to compute the fingerprint of Xj+1 from the fingerprint of Xj . * The computational method is If we let then The computation of each of Wq,Iq(Y) and Iq(1) costs O(m) time. When implementing the computation of Iq(Xj+1) from Iq(Xj) ,only cost O(n) time. So the running time is O(n+m) time. * * Now we analyze the frequency with which this algorithm will fail. A false match will occur only if for some j we have but This is only possible if the chosen prime q divides This product cannot exceed (2m)n , and hence the number of prime that divide it cannot exceed π(mn). If we choose M=2mn2, then the probability of a false match cannot exceed = ， * The probability of failure depends only on the length of the text X. To convert the algorithm into a Las Vegas algorithm, whenever the two fingerprints Iq(Y) and Iq(Xj) match, the two strings are tested for equality. The expected time complexity of this Las Vegas algorithm becomes * 6. Amplification of stochastic advantage Biased: known with certainty one of the possible answer is always correct. Error can be reduced by repeat the algorithm. Unbiased: example coin flip Is it still possible to decrease the error probability arbitrarily by repeating the algorithm? The answer is that it depends on the original error probability. * The first obvious remark is that amplification of the stochastic advantage is impossible in general unless p1/2 because there is always the worthless ?-corret algorithm Stupid(I) 1 if coinflip=heads then return true 2 else return false Whose stochastic “advantage”