Monte Carlo algorithm
Encyclopedia
In computing
, a Monte Carlo algorithm is a randomized algorithm
whose running time is deterministic, but whose output may be incorrect with a certain (typically small) probability
.
The related class of Las Vegas algorithm
s is also randomized, but in a different way: they take an amount of time that varies randomly, but always produce the correct answer. A Monte Carlo algorithm can be converted into a Las Vegas algorithm whenever there exists a procedure to verify that the output produced by the algorithm is indeed correct. If so, then the resulting Las Vegas algorithm is merely to repeatedly run the Monte Carlo algorithm until one of the runs produces an output that can be verified to be correct.
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.
is always expected to be correct, this is not the case for Monte Carlo algorithms. For decision problem
s, 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 behaves likewise, mutatis mutandis
. 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.
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.
BPP describes decision problem
s 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 no, the algorithm always says so, but it may answer no incorrectly for some instances where the correct answer is yes. In contrast, the complexity class ZPP describes problems solvable by polynomial expected time Las Vegas algorithms. , 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 be bounded away from 1/2.
.
Computing
Computing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...
, a Monte Carlo algorithm is a randomized algorithm
Randomized algorithm
A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
whose running time is deterministic, but whose output may be incorrect with a certain (typically small) probability
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
.
The related class of Las Vegas algorithm
Las Vegas algorithm
In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. In other words, a Las Vegas algorithm does not gamble with the verity of the result; it gambles only with the resources...
s is also randomized, but in a different way: they take an amount of time that varies randomly, but always produce the correct answer. A Monte Carlo algorithm can be converted into a Las Vegas algorithm whenever there exists a procedure to verify that the output produced by the algorithm is indeed correct. If so, then the resulting Las Vegas algorithm is merely to repeatedly run the Monte Carlo algorithm until one of the runs produces an output that can be verified to be correct.
The name refers to the grand casino
Monte Carlo Casino
The Monte Carlo Casino is a gambling and entertainment complex located in Monte Carlo, Monaco. It includes a casino, the Grand Théâtre de Monte Carlo, and the office of Les Ballets de Monte Carlo....
in the Principality of Monaco at Monte Carlo
Monte Carlo
Monte Carlo is an administrative area of the Principality of Monaco....
, which is well-known around the world as an icon of gambling.
One-sided vs two-sided error
Whereas the answer returned by a deterministic algorithmDeterministic algorithm
In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states...
is always expected to be correct, this is not the case for Monte Carlo algorithms. For decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s, 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 behaves likewise, mutatis mutandis
Mutatis mutandis
Mutatis mutandis is a Latin phrase meaning "by changing those things which need to be changed" or more simply "the necessary changes having been made"....
. 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
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
. 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.
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
Majority function
In Boolean logic, the majority function is a function from n inputs to one output. The value of the operation is false when n/2 or more arguments are false, and true otherwise....
of the answers.
Complexity classes
The complexity classComplexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
BPP describes decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s that can be solved by polynomial-time Monte Carlo algorithms with a bounded probability of two-sided errors, and the complexity class RP
RP (complexity)
In complexity theory, RP is the complexity class of problems for which a probabilistic Turing machine exists with these properties:* It always runs in polynomial time in the input size...
describes problems that can be solved by a Monte Carlo algorithm with a bounded probability of one-sided error: if the correct answer is no, the algorithm always says so, but it may answer no incorrectly for some instances where the correct answer is yes. In contrast, the complexity class ZPP describes problems solvable by polynomial expected time Las Vegas algorithms. , 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
PP (complexity)
In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time...
, describes decision problems with a polynomial-time Monte Carlo algorithm that is more accurate than flipping a coin but where the error probability cannot be bounded away from 1/2.
Applications in computational number theory
Well-known Monte Carlo algorithms include the Solovay–Strassen primality test, the Miller–Rabin primality test, and certain fast variants of the Schreier–Sims algorithm in computational group theoryComputational group theory
In mathematics, computational group theory is the study ofgroups by means of computers. It is concernedwith designing and analysing algorithms anddata structures to compute information about groups...
.
See also
- Monte Carlo methodMonte Carlo methodMonte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulations of physical and mathematical systems...
s, algorithms used in physical simulation and computational statisticsComputational statisticsComputational statistics, or statistical computing, is the interface between statistics and computer science. It is the area of computational science specific to the mathematical science of statistics....
based on taking random samples