Monte Carlo Algorithm - Amplification

Amplification

For a Monte Carlo algorithm with one-sided errors, the failure probability can be reduced (and the success probability amplified) by running the algorithm k times. Consider again the Solovay–Strassen algorithm which is (1/2)-correct false-biased. One may run this algorithm multiple times returning a false answer if it reaches a false response within k iteration, and otherwise returning true. Thus, if number is prime then the answer is always correct, and if the number is composite then the answer is correct with probability at least 1−(1−1/2)k = 1−2−k.

For Monte Carlo decision algorithms with two-sided error, the failure probability may again be reduced by running the algorithm k times and returning the majority function of the answers.