Las Vegas vs Monte Carlo

Two ways an algorithm can use randomness, distinguished by what is uncertain.

	Las Vegas	Monte Carlo
Output	always correct	may be wrong
Running time	random variable	deterministic (or bounded)
Guarantee	”correct, probably fast"	"fast, probably correct”
Failure mode	runs long	wrong answer
Complexity class	ZPP	BPP (two-sided), RP / co-RP (one-sided)

Las Vegas examples

Algorithm	Random time because
Randomised quicksort	pivot quality varies; $O(n\log n)$ expected
nth_element (introselect)	same; $O(n)$ expected
Pollard’s rho	the walk length is random
Welzl’s enclosing circle	insertion order; $O(n)$ expected
Seidel’s LP	constraint order
Treap operations	tree shape; $O(\log n)$ expected
Randomised incremental Delaunay	insertion order
Hash table with rehashing	collision resolution

The answer is never wrong — only the clock is uncertain. That makes Las Vegas algorithms safe to submit: the risk is TLE, not WA, and the probability of a bad run is astronomically small.

Monte Carlo examples

Algorithm	Error type
Miller-Rabin	one-sided — “composite” is always right
Karger’s min cut	one-sided — may return a larger cut
Freivalds’ $AB=C$ check	one-sided — “not equal” is always right
String hashing equality	one-sided — “different” is always right
Tutte matrix matching test	one-sided
Monte Carlo integration	two-sided, with an error bar
MCTS	two-sided
Simulated annealing	no guarantee at all

One-sided error is the useful kind

When one of the two answers is always correct, repetition drives the error to zero exponentially:

$\mathrm{Pr}[\text{still wrong after }k\text{ runs}]={\epsilon }^k.$

Miller-Rabin’s “composite” verdict is a proof; only “probably prime” carries risk. Hashing’s “hashes differ” is a proof; only “hashes equal” can be a collision. Recognising which side is certain tells you where to add verification.

Converting between them

Las Vegas → Monte Carlo. Run for a fixed time budget; if it has not finished, output anything. Correct whenever it terminates in time.

Monte Carlo → Las Vegas. Only possible when the answer is verifiable. Repeat until verification passes:

$\mathbb{E}[\text{runs}]=\frac{1}{\mathrm{Pr}[\text{success}]}.$

Pollard’s rho is exactly this — a randomised walk (Monte Carlo in spirit) whose output is checked by division, making the whole thing Las Vegas.

Choosing an error probability

With $k$ independent repetitions and per-run error $\epsilon$:

$\epsilon$	$k$	Total error
$1/2$	20	$10^{-6}$
$1/2$	60	$10^{-18}$
$1/4$	30	$10^{-18}$
$4^{-1}$ (Miller-Rabin per base)	30	$10^{-18}$

A rule of thumb: aim for an error below $10^{-9}$ per submission. That is far below the probability of a hardware fault, and it costs only a handful of extra iterations.

In competitive programming

Situation	Safe?
Las Vegas (randomised quicksort, treap)	yes — always correct
Randomised hashing with a time-seeded base	yes — collision probability $\approx qn/2^{61}$
Fixed-seed hashing	no — hackable
Miller-Rabin with deterministic bases	yes — provably correct for 64-bit
Monte Carlo with $10^{-18}$ error	yes in practice
Simulated annealing on an exact-answer problem	no — no guarantee
Randomised algorithm on an interactive problem	check the statement; some forbid it

The complexity classes

Class	Meaning
ZPP	Las Vegas, expected polynomial time
RP	Monte Carlo, one-sided error (no false “yes”)
co-RP	one-sided the other way
BPP	two-sided error $\le \frac{1}{3}$
PP	error $<\frac{1}{2}$ (much weaker; contains NP)

$\mathrm{ZPP}=\mathrm{RP}\cap \mathrm{co}\text{-}\mathrm{RP}$. Whether $\mathrm{P}=\mathrm{BPP}$ is open, but widely believed true — most experts expect randomness does not add computational power, only convenience. See Complexity Theory.

See also: Randomized Algorithms · Complexity Theory · Birthday Paradox