Several entries on this site hand control to Math.random() partway through —
Quicksort's pivot, Welzl's Smallest Enclosing Circle's
insertion order, Karger's Algorithm's edge
contraction, Miller–Rabin's witness
base. Each page explains its own mechanism on its own terms. None of them names which of two
fundamentally different promises that coin flip is allowed to break — and the two are not the
same risk wearing different clothes. A Las Vegas algorithm always returns the
correct answer; randomness only decides how long that takes. A Monte Carlo
algorithm always finishes in bounded time; randomness decides whether the answer it hands back is
actually correct. Every number below is a number its own source page already proved or
measured — this page only reads them side by side for the first time.
Quicksort with a random pivot is the cleanest case. The sort's correctness
comes from the partition invariant alone — "every element left of the pivot is
≤ the pivot and every element right of it is ≥ the pivot" holds no
matter which index got chosen as pivot, so recursing on the two resulting ranges is guaranteed to
finish sorted regardless of how lucky or unlucky the draws were. What the random draw actually
controls is how balanced each split is, which is purely a running-time question. As
quicksort's own Pitfalls section puts it: "random pivot selection has no single input that
reliably triggers O(n²) — the bad case depends on the random draws, not the
data." An unlucky run can still draw a bad pivot at every level — it's just vanishingly
improbable, never impossible, and never wrong.
Quickselect reuses the identical partition step to
find a single rank instead of sorting everything, with the same shape: expected
O(n), worst case O(n²), and an answer that's correct on every single
run — the only place Quickselect's own guaranteed-worst-case variant, median-of-medians, improves on it is
the running-time bound, not correctness, which was never in question either way.
Welzl's Smallest Enclosing Circle
randomizes a different thing — the order points are inserted in, not a per-step dice
roll — but lands on the same promise shape. Its own Complexity section states the bound plainly:
"O(n) expected...
worst case (adversarial or unshuffled order) degrades toward O(n²)" — and that
page verified the answer itself against an O(n⁴) brute-force oracle across
5,000 trials with zero mismatches. Shuffle order can make Welzl's algorithm slow. It can never
make it wrong.
Karger's Algorithm inverts the bargain. A single run costs a bounded,
predictable amount of work — no input makes one run take unboundedly long — but it can, and
routinely does, return a cut that isn't the true global minimum. Its own page derives the exact
floor: for the demo's 6-node graph, a single run finds the true minimum cut with probability at
least 2/(n(n−1)) = 2/30 ≈ 6.7%
— low enough that the page's measured live success rate, which "comes in well above 6.7%, because a
triangle-bridge-triangle shape has an unusually obvious weak point," is still well under even
odds on most runs. The fix isn't a better single run — the standard move is to repeat the whole
algorithm independently many times and keep the smallest cut found, since the true minimum can
only ever be matched or missed, never undercounted.
Miller–Rabin makes the identical bargain with a much tighter per-trial
guarantee. Each witness base costs a fixed, small amount of modular exponentiation — no input
makes one witness check slow — but a composite number can genuinely fool a specific witness, the
exact failure mode its own page demonstrates with 2047 passing base 2 outright. Rabin's theorem
bounds how bad this can get: "at most 1/4 of the bases in
[1, n−1] are false witnesses — so k independent random bases fail to
catch a composite with probability at most 4⁻ᵏ."
Both algorithms above are Monte Carlo, and both get more trustworthy with independent repeats
— but "Monte Carlo" names a shape of promise, not one fixed speed of convergence. Drag
the slider to pick a repeat count and watch each algorithm's own guaranteed worst-case failure
probability shrink at its own rate, using exactly the two bounds quoted above
((1 − 2/30)ᴿ for Karger's on its own 6-node demo graph, 4⁻ᴿ for
Miller–Rabin) — nothing re-derived, just the same formulas each page already proved, evaluated at
a repeat count you choose.
Not every randomized entry on this site fits either bucket. Reservoir Sampling never gambles on a
right-or-wrong answer at all — its own page proves by induction that every item seen in a stream
of length n ends up in a size-k sample with exactly probability
k/n, no better and no worse, for every item, every time. There's no failure mode to
bound, because there's no notion of "wrong" output in the first place — the randomness isn't
insurance against a risk, it is the mechanism that makes the output's distribution
uniform at all. The fixed-memory stream sketches compared in Choosing a Probabilistic Structure
(Bloom Filter, Count-Min Sketch, and others) sit closer to the Monte Carlo side of that line —
each one trades space for a bounded, quantified error rate on a query — but over repeated
membership or count queries against one structure, not a single yes/no decision the way Karger's
or Miller–Rabin make it. Worth keeping separate from both buckets above rather than forced into
either.
For Monte Carlo, independent repeats multiply a real error probability down — literally:
Miller–Rabin's bound is 4⁻ᵏ precisely because each of the k witnesses
is an independent trial, and Karger's amplification works the same way, just with a much weaker
per-trial floor on a small graph. Repetition is a dial that buys arbitrarily high confidence at a
linear cost in trials, because there was a real probability of error to begin with.
For Las Vegas, there is no error to buy down — the answer was never wrong on any single run. What repetition buys instead is protection against an unlucky slow run: impose a time cutoff and restart with a fresh random draw whenever a run is taking unusually long, and the restart is exactly as correct as the run it replaced, with independent (not cursed) luck on the draws. This trades expected time for bounded worst-case latency — it has nothing to do with correctness, because correctness was never the thing at risk. Don't confuse this with average-case running time either, which is a claim about a distribution over inputs an adversary could pick, not over an algorithm's own coin flips — Amortized Analysis's own "amortized isn't average case" section draws that separate line in full.
Calling a Las Vegas algorithm "probably correct." It isn't a probabilistic claim at all — quicksort with a random pivot is always correctly sorted, on every single run, with probability exactly 1. Describing it the way Monte Carlo's bargain works — "usually right" — misdescribes a guarantee that's actually unconditional.
Running a Las Vegas algorithm several times and taking a majority vote. There is only ever one correct answer to agree with, and every single run already returns it — a "majority" of identical correct answers measures nothing. (Contrast with Karger's Algorithm, where running several times and keeping the smallest cut found is exactly the right move, precisely because different runs there really can disagree.)
Trusting a Monte Carlo bound without checking the trials are actually independent. Karger's own Pitfalls section names a case where one silent implementation change — deduplicating parallel edges into a plain set of connected pairs instead of preserving multiplicity — drops the real measured success rate from 37.2% to 23.7% on the identical graph, over the identical number of trials. No amount of extra repeats fixes a bound that was quietly proven for a different (correct) algorithm than the one actually running.