# Monte Carlo algorithm

This article includes a list of general references, but it remains largely unverified because it lacks sufficient corresponding inline citations. (August 2011) |

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]}

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 a dual of Monte Carlo algorithms that never return an incorrect answer--however, they may make random choices as part of their working. As a result, 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[edit]

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 less than 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*.

## Amplification[edit]

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* 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−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.

## Complexity classes[edit]

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 1⁄2.

## Applications in computational number theory[edit]

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[edit]

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

## References[edit]

### Citations[edit]

**^**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. S2CID 5385337.**^**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.**^**Metropolis, N. (1987). "The beginning of the Monte Carlo method" (PDF).*Los Alamos Science*(1987 Special Issue dedicated to Stanislaw Ulam): 125–130.

### Sources[edit]

- 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.