Monte Carlo Algorithm - One-sided Vs Two-sided Error

One-sided Vs Two-sided Error

Whereas the answer returned by a deterministic algorithm is always expected to be correct, this is not the case for Monte Carlo algorithms. For decision problems, these algorithms are generally classified as either false-biased or true-biased. A false-biased Monte Carlo algorithm is always correct when it returns false; a true-biased algorithm is always correct when it returns true. While this describes algorithms with one-sided errors, others might have no bias; these are said to have two-sided errors. The answer they provide (either true or false) will be incorrect, or correct, with some bounded probability.

For instance, the Solovay–Strassen primality test is used to determine whether a given number is a prime number. It always answers true for prime number inputs; for composite inputs, it answers false with probability at least 1/2 and true with probability at most 1/2. Thus, false answers from the algorithm are certain to be correct, whereas the true answers remain uncertain; this is said to be a (1/2)-correct false-biased algorithm.