Monte Carlo algorithm
![]() | This article includes a list of general references, but it lacks sufficient corresponding inline citations. (August 2011) |
In
The name refers to the Monte Carlo casino in the Principality of Monaco, 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]
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
While 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
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
The
Classes of Monte Carlo and Las Vegas algorithms
Randomized algorithms are primarily divided by its two main types, Monte Carlo and Las Vegas, however, these represent only a top of the hierarchy and can be further categorized.[4]
- Las Vegas
- Sherwood—"performant and effective special case of Las Vegas"
- Numerical—"numerical Las Vegas"
- Monte Carlo
- Atlantic City—"bounded error special case of Monte Carlo"
- Numerical—"numerical approximation Monte Carlo"
"Both Las Vegas and Monte Carlo are dealing with decisions, i.e., problems in their decision version."[4] "This however should not give a wrong impression and confine these algorithms to such problems—both types of randomized algorithms can be used on numerical problems as well, problems where the output is not simple ‘yes’/‘no’, but where one needs to receive a result that is numerical in nature."[4]
Efficiency | Optimum | Failure (LV) / Error (MC) | |
---|---|---|---|
Las Vegas (LV) | Probabilistic | Certain | |
Sherwood | Certain, or Sherwood probabilistic
(stronger bound than regular LV) |
Certain | 0 |
Numerical | Probabilistic, certain, or
Sherwood probabilistic |
Certain | or 0 |
Monte Carlo (MC) | Certain | Probabilistic | (probability which through repeated runs grows sub-exponentially
will inhibit usefulness of the algorithm; typical case is ) |
Atlantic City | Certain | Probabilistic | |
Numerical | Certain | Probabilistic | (algorithm type dependent) |
Previous table represents a general framework for Monte Carlo and Las Vegas randomized algorithms.[4] Instead of the mathematical symbol one could use , thus making probabilities in the worst case equal.[4]
Applications in computational number theory and other areas
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.
For algorithms that are a part of Stochastic Optimization (SO) group of algorithms, where probability is not know in advance and is empirically determined, it is sometimes possible to merge Monte Carlo and such an algorithm "to have both probability bound calculated in advance and a Stochastic Optimization component."[4] "Example of such an algorithm is Ant Inspired Monte Carlo."[4][5] In this way, "drawback of SO has been mitigated, and a confidence in a solution has been established."[4][5]
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
- S2CID 5385337.
- .
- ^ Metropolis, N. (1987). "The beginning of the Monte Carlo method" (PDF). Los Alamos Science (1987 Special Issue dedicated to Stanislaw Ulam): 125–130.
- ^ ISBN 978-981-99-3761-5.
- ^ ISSN 0957-4174.
Sources
- ISBN 0-521-47465-5.
- ISBN 0-262-53196-8.
- Berman, Kenneth A.; Paul, Jerome L. (2005). "Ch 24. Probabilistic and Randomized Algorithms". Algorithms: Sequential, Parallel, and Distributed. ISBN 0-534-42057-5.