Randomized Algorithms

Use randomness to make an algorithm simpler, faster, or possible at all.

Why randomness helps

Reason	Example
Defeats adversarial input	randomised pivot in quicksort; a random hash base
Avoids worst cases without analysis	treaps instead of red-black trees
Breaks symmetry	leader election, Karger’s contraction
Samples instead of enumerating	Monte Carlo integration
Finds witnesses fast	Miller-Rabin — most bases are witnesses
Simplifies the code	randomised incremental geometry

The recurring theme: an adversary can construct a bad input for a deterministic algorithm, but cannot predict your coin flips.

The two classes

	Las Vegas	Monte Carlo
Answer	always correct	correct with probability $\ge p$
Running time	random	fixed
Examples	quicksort, Pollard’s rho, Welzl	Miller-Rabin, Karger, hashing
Convert	run until success	repeat and take the majority / any success

See Las Vegas vs Monte Carlo.

The essential tools

Random number generation

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long r = uniform_int_distribution<long long>(1, n)(rng);
shuffle(v.begin(), v.end(), rng);

Never use a fixed seed, rand(), or random_shuffle

• A fixed seed is predictable and hackable — Codeforces problems include anti-tests for common seeds.
• rand() is low quality and its low bits are often nearly non-random; rand() % n is biased.
• random_shuffle is removed in C++17 and used rand() internally.
• Seed from the clock (and ideally XOR in an address for extra entropy).

Concentration bounds

Chernoff: for independent $X_i\in [0,1]$ with $\mu =\mathbb{E}[\sum X_i]$,
$\mathrm{Pr}\left[\left|\sum X_i-\mu \right|\ge \delta \mu \right]\le 2e^{-{\delta }^2\mu /3}.$

Markov: $\mathrm{Pr}[X\ge a]\le \mathbb{E}[X]/a$ for non-negative $X$.

Union bound: $\mathrm{Pr}[\bigcup A_i]\le \sum \mathrm{Pr}[A_i]$ — crude but almost always sufficient.

These say “a sum of independent bounded variables is very close to its mean”, which is what licenses the phrase “with high probability”.

Backwards analysis

“What is the probability that the last element added was important?” Gives clean $O(n)$ expected bounds for randomised incremental algorithms — see Seidel’s LP, Welzl, and randomised Delaunay.

Randomised algorithms worth knowing

Algorithm	Randomness used for
Quicksort / nth_element	pivot choice
Treap	node priorities
Skip list	level assignment
Miller-Rabin	witness bases
Pollard’s rho	the pseudo-random walk
Karger’s min cut	edge contraction
Welzl’s enclosing circle	insertion order
String hashing	the base
Tutte matrix matching	matrix entries
Freivalds’ matrix product check	test vector
Simulated annealing	move acceptance
Reservoir sampling	which item to keep

Freivalds’ algorithm

Verify $AB=C$ for $n\times n$ matrices in $O(n^2)$ instead of $O(n^{\omega })$: pick a random 0/1 vector $r$ and check $A(Br)=Cr$. If $AB\ne C$, the test fails with probability $\ge \frac{1}{2}$; repeat $k$ times for error $2^{-k}$.

A perfect illustration: verifying is easier than computing, and randomness closes the gap.

Derandomisation

Some randomised algorithms can be made deterministic:

• Method of conditional expectations — fix the random choices one at a time, always taking the branch that keeps the conditional expectation good.
• Pairwise independence — many analyses need only pairwise independence, which requires $O(\log n)$ random bits and can then be enumerated.
• Fixed witness sets — Miller-Rabin with 12 fixed bases is deterministic for all 64-bit inputs.

Usually not worth it in practice, but the conditional-expectation method is a genuine proof technique.

See also: Las Vegas vs Monte Carlo · Random Shuffling · Birthday Paradox