Engineering / Mathematics — Probabilistic Algorithms
Probabilistic Algorithms: Foundations
The model of randomised computation, Las Vegas and Monte Carlo algorithms, and what a probabilistic guarantee means.
Executive summary
A probabilistic algorithm has access to a source of random bits and its output or running time may depend on them. The guarantee is over the algorithm's own coins, with the input fixed and possibly adversarial.
The two families — always correct but variable in time, or always fast but occasionally wrong — call for different analyses.
Learning objectives
- Define the randomised computation model.
- Distinguish Las Vegas from Monte Carlo algorithms.
- State what a probabilistic guarantee does and does not claim.
01The model
A probabilistic algorithm is a deterministic algorithm with an extra input tape of independent uniform bits. Fixing the input, the output and running time become random variables over the coin sequence.
Average-case analysis over random inputs is a genuinely weaker and less useful guarantee, because real inputs are rarely random and may be chosen by someone with an interest in the algorithm performing badly.
02Las Vegas and Monte Carlo
Las Vegas
Always produces a correct answer; the running time is a random variable. Randomised quicksort and finding a quadratic non-residue are examples. Analysed by expected running time.
Monte Carlo
Runs in bounded time; the answer may be wrong with bounded probability. Miller–Rabin is the canonical example. Analysed by error probability.
The two are interconvertible under conditions. A Las Vegas algorithm truncated at a time bound becomes Monte Carlo. A Monte Carlo algorithm whose answers can be verified becomes Las Vegas by repeating until verification succeeds.
| Type | Correctness | Running time | Amplification |
|---|---|---|---|
| Las Vegas | Always correct | Random | Not needed |
| Monte Carlo, one-sided | One answer always right | Bounded | Repeat; error multiplies |
| Monte Carlo, two-sided | Either answer may err | Bounded | Repeat and take majority |
03One-sided and two-sided error
Miller–Rabin has one-sided error: it never declares a prime composite, so a composite verdict is certain and only a probable-prime verdict carries doubt. Repetition drives the doubt down geometrically.
Two-sided error means either verdict may be wrong. Amplification then requires a majority vote across repetitions rather than a single conclusive failure, and the analysis needs a concentration bound rather than a simple product.
04Frequently asked questions
Why use randomness when deterministic algorithms exist?
Because the randomised versions are usually far faster. Deterministic primality testing is polynomial via AKS but Miller-Rabin is orders of magnitude quicker, and every deployed implementation uses the randomised test.
Where do the random bits come from?
An operating system entropy source conditioned into a deterministic generator. The quality matters absolutely: predictable randomness has broken deployed key generation more than once.
Does a small error probability mean the answer is probably right?
For the algorithm's verdict, yes, but the inference needs care. Converting a test's error rate into a probability that a specific number is prime requires Bayes' theorem and the prior density of primes.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 148-155.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.