Monte Carlo algorithm

In computing, a Monte Carlo algorithm is a randomized algorithm whose output may be incorrect with a certain (typically small) probability. Two examples of such algorithms are Karger–Stein algorithm[1] and Monte Carlo algorithm for minimum Feedback arc set.[2]

Not to be confused with Monte Carlo method.

The name refers to the grand casino in the Principality of Monaco at Monte Carlo, which is well-known around the world as an icon of gambling. The term "Monte Carlo" was first introduced in 1947 by Nicholas Metropolis.[3]

Las Vegas algorithms are the subset of Monte Carlo algorithms that always produce the correct answer. Because they make random choices as part of their working, the time taken might vary between runs even with the same input.

If there is a procedure for verifying whether the answer given by a Monte Carlo algorithm is correct, and the probability of a correct answer is bounded above zero, then with probability one running the algorithm repeatedly while testing the answers will eventually give a correct answer. Whether this process is a Las Vegas algorithm depends on whether halting with probability one is considered to satisfy the definition.

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 ½ and true with probability less than ½. Thus, false answers from the algorithm are certain to be correct, whereas the true answers remain uncertain; this is said to be a ½-correct false-biased algorithm.

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 ½-correct false-biased. One may run this algorithm multiple times returning a false answer if it reaches a false response within k iterations, and otherwise returning true. Thus, if the 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−½)^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.

Complexity classes

The complexity class BPP describes decision problems that can be solved by polynomial-time Monte Carlo algorithms with a bounded probability of two-sided errors, and the complexity class RP describes problems that can be solved by a Monte Carlo algorithm with a bounded probability of one-sided error: if the correct answer is false, the algorithm always says so, but it may answer false incorrectly for some instances where the correct answer is true. In contrast, the complexity class ZPP describes problems solvable by polynomial expected time Las Vegas algorithms. ZPP ⊆ RP ⊆ BPP, but it is not known whether any of these complexity classes is distinct from each other; that is, Monte Carlo algorithms may have more computational power than Las Vegas algorithms, but this has not been proven. Another complexity class, PP, describes decision problems with a polynomial-time Monte Carlo algorithm that is more accurate than flipping a coin but where the error probability cannot necessarily be bounded away from ½.

Applications in computational number theory

Well-known Monte Carlo algorithms include the Solovay–Strassen primality test, the Baillie–PSW primality test, the Miller–Rabin primality test, and certain fast variants of the Schreier–Sims algorithm in computational group theory.

See also

• Monte Carlo methods, algorithms used in physical simulation and computational statistics based on taking random samples
• Atlantic City algorithm
• Las Vegas algorithm

References

Citations

1. Karger, David R.; Stein, Clifford (July 1996). "A New Approach to the Minimum Cut Problem". J. ACM. 43 (4): 601–640. doi:10.1145/234533.234534. ISSN 0004-5411.
2. Kudelić, Robert (2016-04-01). "Monte-Carlo randomized algorithm for minimal feedback arc set problem". Applied Soft Computing. 41: 235–246. doi:10.1016/j.asoc.2015.12.018.
3. Metropolis, N. (1987). "The beginning of the Monte Carlo method" (PDF). Los Alamos Science (1987 Special Issue dedicated to Stanislaw Ulam): 125–130.CS1 maint: ref=harv (link)

Sources

• Motwani, Rajeev; Raghavan, Prabhakar (1995). Randomized Algorithms. New York: Cambridge University Press. ISBN 0-521-47465-5.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Ch 5. Probabilistic Analysis and Randomized Algorithms". Introduction to Algorithms (2nd ed.). Boston: MIT Press and McGraw-Hill. ISBN 0-262-53196-8.
• Berman, Kenneth A.; Paul, Jerome L. (2005). "Ch 24. Probabilistic and Randomized Algorithms". Algorithms: Sequential, Parallel, and Distributed. Boston: Course Technology. ISBN 0-534-42057-5.