A Monte Carlo algorithm is a randomized algorithm that may return an incorrect result, but whose probability of error is bounded under stated assumptions. It typically guarantees a specified bound on running time, trading certainty of correctness for computational efficiency. Its guarantees concern each fixed input: the probability is taken over the algorithm’s internal random choices, not necessarily over a distribution of inputs. The term also has a broader numerical meaning, encompassing methods that estimate quantities through random sampling.
Definition and scope
An ordinary deterministic algorithm follows the same computational path whenever it receives the same input. A randomized algorithm additionally uses random choices, so its output, running time, or both may vary between executions.
In the standard decision-problem setting, a Monte Carlo algorithm computes a Boolean function with error bound if, for every valid input ,
where denotes the internal random choices. Its running time is bounded by a stated function of input length, usually a polynomial in complexity-theoretic discussions. A conventional constant error bound is , although other constants below can generally be reduced through repetition.
This is a worst-case-over-inputs, probabilistic-over-randomness guarantee. An algorithm that succeeds on most inputs but systematically fails on certain inputs does not satisfy it merely because its average success rate is high.
In numerical computation, an output is usually an estimate rather than a yes-or-no answer. The corresponding guarantee may instead take the form
where is the target quantity, is the estimate, is an error tolerance, and is the permitted failure probability. Thus, “incorrect” can mean “outside the required tolerance,” rather than simply unequal to an exact value.
Relationship to other algorithmic approaches
Monte Carlo and Las Vegas algorithms
A Las Vegas algorithm always returns a correct answer when it returns an answer, but its running time depends on random choices. Its performance is commonly described by an expected running-time bound.
The central distinction is therefore:
| Approach | Correctness | Running time |
|---|---|---|
| Monte Carlo | Allows a bounded probability of error | Typically has a specified worst-case bound |
| Las Vegas | Guarantees correctness of returned answers | Random; often analyzed in expectation |
The names refer to different uses of randomness, not different application domains. Randomized quicksort, for example, is normally classified as Las Vegas: random pivot choices affect execution time, but not the correctness of the sorted output.
A Las Vegas algorithm with a finite expected running time can sometimes be turned into a Monte Carlo algorithm by imposing a deadline and producing a fallback answer on timeout. The timeout probability then bounds the added error. Converting in the other direction requires additional structure, such as an efficient way to verify candidate answers; it is not universally possible.
Approximation and randomization
A Monte Carlo algorithm is not necessarily an approximation algorithm. It may seek an exact answer, such as whether an integer is prime, while allowing a small probability of answering incorrectly. Conversely, a deterministic approximation algorithm may always satisfy its approximation guarantee without using randomness.
Randomized approximation methods combine the two ideas: an approximate answer must meet a specified accuracy requirement with a specified probability.
One-sided and two-sided error
Monte Carlo decision algorithms are commonly divided according to which answers can be wrong.
One-sided error means that one class of inputs is always handled correctly, while the other class may be misclassified. For example, a test may never call a prime number composite, yet occasionally classify a composite number as probably prime. The direction must be stated: “one-sided” alone does not identify which answer is conclusive.
Two-sided error means that either answer may be wrong, although the error probability is bounded separately for every input.
This distinction affects how repeated executions should be combined. For a one-sided test, one conclusive result may settle the decision. For a two-sided test, majority voting is a standard method of reducing error.
In computational complexity, the class BPP consists of decision problems solvable in polynomial time with bounded two-sided error. The class RP uses one-sided error: no-instances are always rejected, while yes-instances are accepted with probability at least . The complementary orientation gives co-RP.
Error reduction by repetition
Suppose each execution has error probability at most . If executions use independent random choices, running the algorithm times and taking a majority vote reduces the error exponentially in .
For odd , a standard concentration bound gives
When is bounded away from , reaching error probability at most therefore requires only repetitions.
For a one-sided algorithm whose inconclusive or misleading outcome occurs with probability at most , requiring that outcome in all independent repetitions yields an error bound of .
Independence is important. Repeating an execution with exactly the same random seed generally reproduces the same behavior rather than providing a new independent trial. Repetition also cannot repair a flawed mathematical model or a systematically incorrect implementation.
Representative examples
Miller–Rabin primality testing
The Miller–Rabin primality test is a standard example of a one-sided Monte Carlo algorithm. It tests algebraic conditions that every prime must satisfy. If a tested base violates those conditions, the input is certainly composite. If the conditions hold, the input remains a probable prime.
For an odd composite integer , at most one quarter of bases chosen uniformly from pass a single strong probable-prime test. Consequently, independent random rounds give a false probable-prime probability of at most
This is a probability over the selected bases for a fixed composite input. It is not automatically the probability that a number is composite after passing the test; that latter interpretation also depends on how candidate numbers were selected.
For certain bounded input ranges, suitable predetermined bases give deterministic tests. Such variants should be distinguished from the randomized algorithm.
Polynomial identity testing
Polynomial identity testing asks whether an algebraically represented polynomial is identically zero. Expanding an expression into all its terms may be expensive, so an algorithm can instead evaluate it at randomly chosen points.
The Schwartz–Zippel lemma states that if a nonzero multivariate polynomial over a field has total degree at most , and each variable is sampled independently and uniformly from a finite subset of that field, then
An identically zero polynomial evaluates to zero everywhere. A nonzero evaluation therefore proves nonidentity, whereas a zero evaluation may be misleading. Choosing a sufficiently large sampling set and repeating the test gives a controlled one-sided error probability.
Matrix product verification
Freivalds’ algorithm checks a proposed matrix product without directly computing every entry of . For matrices, it selects a random binary vector and tests whether
If the product is correct, the equality always holds. If it is incorrect, a uniformly sampled binary vector fails to reveal the error with probability at most . A round uses arithmetic operations, compared with for straightforward matrix multiplication. Independent repetition reduces the probability of accepting an incorrect product.
Numerical Monte Carlo methods
The broader family of Monte Carlo methods uses random sampling to estimate integrals, probabilities, expected outcomes, and other quantities. The term became established through computational work associated with Stanisław Ulam, John von Neumann, and collaborators in the 1940s, particularly on particle transport.
A basic example estimates the expected value from independent samples:
If each sample has finite variance , then
The standard deviation of the estimator therefore decreases as . Halving it ordinarily requires four times as many samples.
This sampling-rate exponent does not explicitly depend on dimension, helping explain Monte Carlo methods’ usefulness for high-dimensional integration. Nevertheless, variance, sample-generation cost, and the difficulty of representing rare events may depend strongly on dimension and problem structure.
Applications include particle transport, financial simulation, statistical inference, and light-transport estimation in computer graphics. Monte Carlo tree search uses sampled outcomes to guide search decisions, but its name does not by itself imply a fixed finite-run error guarantee of the kind used in complexity theory.
Practical limitations and reliability
Randomness assumptions. Proofs commonly assume independent, uniformly distributed random bits or samples. Implementations generally use a pseudorandom number generator, whose finite state and deterministic behavior must be considered. In adversarial environments, predictability may matter as well as statistical quality.
Sampling bias and dependence. Samples drawn from the wrong distribution can invalidate an error guarantee. Correlation can reduce the effective amount of information obtained from repeated trials. Confidence calculations must reflect the actual sampling process.
Numerical error. Mathematical guarantees may assume exact arithmetic. Rounding, overflow, or unstable computations introduce errors distinct from random sampling error.
Accumulation across many decisions. A small per-execution failure probability is not automatically a small system-wide failure probability. If a system makes decisions, each with error probability at most , the probability of at least one error is at most by the union bound, capped at 1. Independence is not required for this bound.
Verification and failure consequences. Where outputs can be efficiently checked, verification can detect some failures or support a different algorithmic design. Where checking is difficult, reliability depends more directly on the validity of the probabilistic analysis and its implementation assumptions.