Why put a coin inside an algorithm at all
Every algorithm you have met so far has been deterministic: same input, same steps, same answer, every single time. A randomized algorithm breaks that rule on purpose — it is allowed to flip coins as it runs, so the same input can send it down different paths. That sounds like throwing away control, and the natural worry is that it must also throw away reliability. The surprise of this whole rung is that a tiny bit of randomness, spent wisely, buys speed and simplicity that determinism struggles to match.
Here is the key shift in mindset. Recall from the asymptotics rung how we talked about worst, best, and average case. Average-case analysis is fragile: it averages over an assumed distribution of inputs, so an adversary who feeds you the bad inputs on purpose defeats it. Randomization moves the dice out of the input and into the algorithm. Now the input can be the single nastiest case imaginable, fixed in advance — and we still average, but over OUR coin flips, which the adversary cannot see or steer. The guarantee stops being 'good on typical inputs' and becomes 'good on every input, in expectation over my own randomness.' That relocation of the randomness is the entire point.
Two ways to gamble: answer or time
Once you allow coin flips, exactly two things can go wrong, and which one you let go wrong defines the two great families. A Las Vegas algorithm is one whose answer is ALWAYS correct; the coins only affect how long it runs. Its running time is a random variable, and we quote its EXPECTED time. A Monte Carlo algorithm is the mirror image: it always finishes within a fixed time bound, but its answer is correct only with some probability — it is allowed to be wrong, with a chance you control.
A homely picture nails it. Las Vegas is a careful tourist who refuses to leave the city until they have truly found the right hotel — they will get there, but you cannot promise a friend exactly when. Monte Carlo is a tourist on a strict train schedule: they leave at a guaranteed hour no matter what, but there is a small chance they board the wrong train. One gambles its clock and keeps its honesty; the other gambles its honesty and keeps its clock. You never get to gamble neither — that would just be a deterministic algorithm — and a method that gambled both, free to be both slow and wrong, would be useless.
A worked pair: quicksort vs Freivalds
Make it concrete with one algorithm from each family. Randomized quicksort is Las Vegas. You sort by picking a pivot uniformly at random, partitioning, and recursing. No matter which pivots the coins choose, the output is a correctly sorted array — correctness never wavers. What the coins control is the work: a lucky run splits evenly and costs O(n log n); an unlucky run keeps picking extreme pivots and degrades toward O(n^2). The headline result, which the linearity-of-expectation guide will prove, is that the EXPECTED time is O(n log n) on every input. Be honest about the fine print: O(n log n) is the expectation, and the worst case is still O(n^2) — randomization makes that worst case astronomically unlikely, not impossible.
Now the Monte Carlo mirror: Freivalds' algorithm for checking a matrix product. Someone hands you three n-by-n matrices A, B, C and claims A times B equals C. Recomputing A times B to check costs about O(n^3). Freivalds instead picks a random 0/1 vector r and tests whether A times (B times r) equals C times r — three matrix-vector products, just O(n^2) work. If A times B really equals C, the test passes for sure. If they differ, the test catches it with probability at least one half. So a single pass is fast and one-sided: it never falsely rejects a true product, but it might let a wrong one slip through, with probability at most one half.
FREIVALDS(A, B, C): # all n x n
r <- random 0/1 vector of length n
x <- B * r # O(n^2)
if A * x == C * r: # O(n^2)
return "probably equal"
else:
return "definitely NOT equal" # never wrong hereCheap confidence: hammer the error down
A one-half chance of being wrong sounds alarming until you see how violently you can crush it. The trick for a ONE-SIDED Monte Carlo algorithm — one that errs in only one direction, like Freivalds saying 'equal' — is independent repetition. Run it k times with fresh coins. If A times B truly differs from C, each run independently catches the difference with probability at least one half, so the only way to be fooled is for ALL k runs to miss. Because the coins are independent, those misses multiply: the probability of being fooled is at most (1/2)^k.
- One run of Freivalds: error probability at most 1/2. Fast, but you would not bet your job on it.
- Run it 10 times with independent coins and accept only if ALL ten say 'equal'. Error probability at most (1/2)^10, under 1 in 1000 — and the cost is still just 10 times O(n^2), i.e. O(n^2), far below the O(n^3) of recomputing.
- Want 1 in a million? Run 20 times: (1/2)^20 is under a millionth. Each extra run HALVES the error, so confidence grows exponentially while cost grows only linearly. That asymmetry is the whole magic.
Two honest cautions. First, this clean halving works because Freivalds is one-sided: a single 'NOT equal' is a definite proof, so repeating only needs to catch the difference once. For a TWO-sided algorithm that can err either way, you cannot just accept-if-all-agree; you take a MAJORITY vote over many runs, and the error still shrinks fast — but proving it needs the tail-bound machinery of the next guides, not a one-line product. Second, 'probability at most (1/2)^k' is over your coins, not a frequency claim about inputs; a real coin source matters, since a predictable pseudo-random generator can be gamed by an adversary who knows it.
Converting between the two
The two families are not sealed boxes; there is a clean bridge in one direction and a leakier one back. The easy direction: any Las Vegas algorithm can be turned into Monte Carlo. Take a Las Vegas method with expected time T, run it, but slam a hard deadline at, say, 10 times T. By the Markov-type reasoning we will sharpen later, it almost always finishes in time; if the deadline strikes first, just halt and emit any answer (or 'don't know'). You have traded a guaranteed-correct-but-open-ended method for a guaranteed-fast-but-occasionally-wrong one. Honesty in, honesty out: the chance of a bad answer is exactly the chance the clock ran out.
The reverse direction — Monte Carlo back to Las Vegas — needs one extra gift: a fast way to CHECK whether a candidate answer is correct. If you have such a checker, wrap the Monte Carlo algorithm in a loop: run it, check the output; if correct, return it; if not, throw fresh coins and try again. Every iteration is correct-or-retry, so whatever you finally return is guaranteed right — that is Las Vegas. The number of tries is random (geometric in the per-run success probability), so the TIME is now the random quantity, exactly as a Las Vegas method demands. The catch is the checker: without an efficient way to verify an answer, this conversion is stuck, which is why it is the harder direction.
So how do you pick a family for a real task? Ask what you can least afford to lose. If a wrong answer is catastrophic but you can tolerate a variable finish time, build Las Vegas and quote expected time — randomized quicksort, randomized selection, the kind of sorting you would actually ship. If you face a hard real-time deadline and a small, controllable error is acceptable — a streaming counter, a primality screen, a fingerprint check — reach for Monte Carlo and drive the error down by repetition. The deepest lesson of this rung is that randomness is not sloppiness; it is a resource you spend on purpose, and naming WHICH guarantee you are buying — the answer or the clock — is the first and most clarifying decision you make.