Randomised Algorithms

Every deterministic algorithm has a nemesis — an input, sometimes vanishingly rare, on which it does its absolute worst. Sort an already-sorted array with textbook quicksort and you hit the \Theta(n^2) disaster; an adversary who has read your code can hand you that input on purpose. The radical idea of a randomised algorithm is to stop being predictable: let the algorithm flip its own coins and make choices the adversary cannot foresee. The input is fixed and possibly malicious; the randomness lives inside the algorithm, where no enemy can reach it.

This small shift buys enormous things: algorithms that are simpler, faster, and — crucially — carry performance guarantees on every input rather than merely on a "typical" one. The analysis reuses exactly the tools from average-case analysis — linearity of expectation, indicator variables — but now the expectation is over the coins we control, not over inputs we hope are benign.

Two species: Las Vegas and Monte Carlo

Randomised algorithms split into two great families, distinguished by where the randomness shows up — in the running time, or in the correctness.

The names are Babai's joke: Las Vegas gambles with time (you always leave with the right answer, eventually), Monte Carlo gambles with correctness (you leave on schedule, but maybe with the wrong answer). Keep the pair straight and half the subject organises itself.

Boosting confidence: amplification by repetition

The Monte Carlo bargain looks alarming — an algorithm that is wrong sometimes? — until you see how cheaply you can drive the error down. Suppose a one-sided Monte Carlo test says "yes" correctly with probability at least p and can only err by saying "no" when the answer is really "yes". Run it k independent times and answer "yes" if any run does. It fails only if all k runs miss — and because the runs are independent,

\Pr[\text{all } k \text{ wrong}] \le (1-p)^k \quad\Longrightarrow\quad \Pr[\text{correct}] \ge 1-(1-p)^k.

Because 1-p < 1, that failure probability decays exponentially in k. Even a barely-better-than-a-coin test with p = 0.5 reaches one-in-a-million error after just 20 repetitions. The chart shows success probability climbing toward certainty as you stack repetitions — steeper the larger the per-trial success p.

This is why "randomised" does not mean "unreliable". You choose your own risk: to make the error smaller than the chance of a cosmic ray flipping a bit in your RAM, a few dozen rounds suffice, at a cost that is merely a constant factor.

A Las Vegas star: randomised QuickSelect

QuickSelect finds the k-th smallest element without fully sorting. It partitions around a pivot (exactly like quicksort) but then recurses into only the side that contains the answer. Choosing the pivot at random is what makes it fast on every input.

function quickSelect(a: number[], k: number): number { // returns the k-th smallest element (1-indexed) of a if (a.length === 1) return a[0]; const pivot = a[Math.floor(Math.random() * a.length)]; // random pivot: the whole trick const less = a.filter((x) => x < pivot); const equal = a.filter((x) => x === pivot); const more = a.filter((x) => x > pivot); if (k <= less.length) return quickSelect(less, k); if (k <= less.length + equal.length) return pivot; // pivot is the answer return quickSelect(more, k - less.length - equal.length); }

A random pivot lands in the middle half of the values with probability 1/2, and such a pivot shrinks the problem to at most 3/4 of its size. So on average every two partitions cut the array by a constant fraction, and the expected total work is a geometric series:

\mathbb{E}[T(n)] \le n + \tfrac{3}{4}\,\mathbb{E}[T(n)]\cdot\text{(amortised)} \;\Rightarrow\; \mathbb{E}[T(n)] = \Theta(n).

Expected linear time to find a median, on any input at all — no sorting, no n\log n. The worst case is still \Theta(n^2) (every pivot could, with tiny probability, be the extreme), but no adversary can force it: the bad case depends on our coins, which the adversary never sees.

Picture a game. A deterministic algorithm is a fixed strategy written down in advance; the adversary reads it and plays the one input that exploits it — checkmate every time. A randomised algorithm is really a probability distribution over many strategies, and the adversary must commit to an input before your coins are flipped. Now, however cleverly the input is chosen, it is bad for only a small fraction of your possible coin outcomes, so your expected cost is low. This is precisely von Neumann's minimax theorem in disguise (Yao's principle makes it exact): moving from a pure strategy to a mixed one strips the adversary of the ability to target you. Randomness is not luck — it is unpredictability, and unpredictability is what defeats a worst-case enemy.

The clean 1-(1-p)^k bound has two fine-print conditions people forget. First, the repetitions must be independent — same input, but fresh, independent coins each time. Re-running with the same random seed just reproduces the same (possibly wrong) answer; (1-p)^k silently assumed independence when it multiplied the failure probabilities. Second, majority-vote amplification for a two-sided error (the algorithm can be wrong in both directions) needs a Chernoff-bound argument and a per-trial edge bounded away from 1/2 — you cannot boost a coin that is right exactly half the time. For the one-sided "yes-biased" case above, a single correct run settles it, which is why OR-amplification is so clean there.