i. Randomized Algorithms

Use randomness to make an algorithm simpler, faster, or possible at all. The recurring theme: an adversary can construct a bad input for a deterministic algorithm, but cannot predict your coin flips. Hashing and verification are in Randomized Hashing and Verification, sampling and sketches in Sampling and Streaming, color coding and random-walk SAT in Randomized Search, heuristics in Heuristic Optimization.

Why randomness helps	Example
defeats adversarial input	random 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	randomized incremental geometry

Las Vegas and Monte Carlo

	Las Vegas	Monte Carlo
output	always correct	may be wrong with probability $\le \epsilon$
running time	a random variable	deterministic (or bounded)
guarantee	”correct, probably fast"	"fast, probably correct”
failure mode	runs long (TLE)	wrong answer (WA)
complexity class	ZPP	RP / co-RP (one-sided), BPP (two-sided)
examples	quicksort, quickselect, Pollard’s rho, Welzl, Seidel’s LP, treaps, randomized incremental Delaunay, hash tables with rehashing	Miller–Rabin, Karger, Freivalds, string hashing, Tutte matrix test, Monte Carlo integration (two-sided, with an error bar), MCTS; simulated annealing has no guarantee at all
convert	stop after a time budget and output anything: Monte Carlo	repeat until a verifier accepts: Las Vegas, $\mathbb{E}[\text{runs}]=1/\mathrm{Pr}[\text{success}]$ (Pollard’s rho: a random walk whose output is checked by division)

One-sided error is the useful kind. If one answer is always right (Miller–Rabin’s “composite”, Freivalds’ and hashing’s “different”), $k$ independent repetitions push the error to ${\epsilon }^k$; recognising which side is certain tells you where to add verification.

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

Rule of thumb: aim for an error below $10^{-9}$ per submission, far below the probability of a hardware fault, for a handful of extra iterations.

In contests	Safe?
Las Vegas (randomized quicksort, treap)	yes: always correct
hashing with a time-seeded base	yes: collision probability about $qn/2^{61}$
fixed-seed hashing or shuffling	no: hackable (Codeforces has anti-tests for common seeds)
Miller–Rabin with the deterministic 64-bit bases	yes: provably correct
Monte Carlo with $10^{-18}$ error	yes in practice
simulated annealing on an exact-answer problem	no
randomized algorithm on an interactive problem or a reproducibility-checking judge	read the statement

Class	Meaning
ZPP	Las Vegas, expected polynomial time
RP	one-sided error: never a 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 \text{co-RP}$; whether $\mathrm{P}=\mathrm{BPP}$ is open but widely believed: randomness is expected to add convenience, not power. See Complexity Theory.

Las Vegas, carefully. Every output is valid; analyse the expected work over the random choices for every fixed legal input. Expected linear time is not a deadline; a heuristic that may silently fail is not Las Vegas merely because it retries; a retry limit changes the guarantee unless exhaustion is handled. Keep correctness and termination arguments separate (randomized pivots change quicksort’s running time, never the correctness of partitioning). Monte Carlo, carefully. Identify the random choices, state the failure bound, and union-bound over all comparisons or queries ($Q$ events of error $\le p$ give $\le Qp$). A fixed seed exposed to an adaptive adversary breaks the probability model, and two hashes are independent only if their randomness is; “large modulus” alone is not a proof.

Random numbers and shuffling

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() ^ (ull)new char);
ll randInt(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
 
template<class T> void fisherYates(vector<T>& v) {      // what std::shuffle(all(v), rng) does
    for (int i = sz(v) - 1; i > 0; i--) swap(v[i], v[randInt(0, i)]);
}
 
ll quickselect(vector<ll> a, int k) {                  // k-th smallest (0-based), expected O(n)
    int l = 0, r = sz(a) - 1;
    while (true) {
        if (l == r) return a[l];
        ll p = a[randInt(l, r)];
        int i = l, j = r, m = l;                       // 3-way partition: < p | == p | > p
        while (m <= j) { if (a[m] < p) swap(a[i++], a[m++]); else if (a[m] > p) swap(a[m], a[j--]); else m++; }
        if (k < i) r = i - 1; else if (k > j) l = j + 1; else return p;
    }
}

Never use a fixed seed, rand(), random_shuffle or srand(time(0))

A fixed seed is predictable and hackable. rand() is low quality (weak low bits) and rand() % n is biased when $n$ does not divide RAND_MAX + 1. random_shuffle used rand() and was removed in C++17. srand(time(0)) has one-second granularity: submissions in the same second share a seed. Seed from the clock, XOR an address in for extra entropy. The common shuffle bug swap(v[i], v[rand() % n]) (full range at every step) is not uniform.

What shuffling protects	Killer input without it
quicksort with the first element as pivot	already sorted: $O(n^2)$
Welzl’s enclosing circle	points ordered so each is outside: $O(n^3)$
Seidel’s LP, randomized incremental Delaunay	adversarial insertion order
Kuhn’s matching	adversarial adjacency order: shuffling adjacency lists is a cheap real speed-up against anti-Kuhn tests
hash tables	colliding keys: $O(n)$ per operation
unbalanced BSTs	sorted insertion: a linked list

Proof: Fisher–Yates is uniform, and quickselect is expected linear

Fisher–Yates. Step $i$ (from $n-1$ down to 1) chooses uniformly which of the $i+1$ remaining elements ends at position $i$; the choices are independent. So each of the $n\cdot (n-1)\cdots 2=n!$ choice sequences has probability $\frac{1}{n!}$, and distinct sequences give distinct permutations (position $i$‘s element is determined by step $i$): every permutation has probability $\frac{1}{n!}$. The buggy version has $n^n$ equally likely sequences, and $n!$ does not divide $n^n$ for $n\ge 3$, so it cannot be uniform.

Quickselect. Call a round good if the pivot’s rank lies in the middle half of the current range; this happens with probability $\ge \frac{1}{2}$, and then the range shrinks to at most $\frac{3}{4}$ of its size. The expected number of rounds while the size is in $(n(\frac{3}{4}{)}^{j+1},n(\frac{3}{4}{)}^j]$ is at most 2, each costing $O(n(\frac{3}{4}{)}^j)$, so the expected total is $O(n{\sum }_{j}2(\frac{3}{4}{)}^j)=O(n)$. It is Las Vegas: the answer is always correct. Checked: shuffle frequencies of all $4!=24$ permutations pass a chi-square test, and quickselect agrees with sorting on random arrays.

Probability tools

Tool	Statement
linearity of expectation	$\mathbb{E}[\sum X_i]=\sum \mathbb{E}[X_i]$, no independence needed
union bound	$\mathrm{Pr}[\bigcup A_i]\le \sum \mathrm{Pr}[A_i]$: crude but almost always enough
Markov	$X\ge 0$: $\mathrm{Pr}[X\ge a]\le \mathbb{E}[X]/a$
Chebyshev	$\mathrm{Pr}[|X-\mu |\ge a]\le \mathrm{Var}(X)/a^2$
Chernoff	independent $X_i\in [0,1]$, $\mu =\mathbb{E}[\sum X_i]$, $0<\delta \le 1$: $\mathrm{Pr}[\sum X_i\ge (1+\delta )\mu ]\le e^{-{\delta }^2\mu /3}$, $\mathrm{Pr}[\sum X_i\le (1-\delta )\mu ]\le e^{-{\delta }^2\mu /2}$, so $\mathrm{Pr}[|\sum X_i-\mu |\ge \delta \mu ]\le 2e^{-{\delta }^2\mu /3}$
backwards analysis	”what is the probability that the last element added was important?”: clean $O(n)$ expected bounds for randomized incremental algorithms (Seidel’s LP, Welzl, Delaunay)

Chernoff is what licenses “with high probability”: a sum of independent bounded variables is very close to its mean.

Proof: Markov, Chebyshev, Chernoff and a backwards-analysis example

Markov. $a\cdot [X\ge a]\le X$ pointwise; take expectations. Chebyshev. Markov applied to $(X-\mu {)}^2\ge a^2$.

Chernoff. For $t>0$ and $x\in [0,1]$, convexity gives $e^{tx}\le 1+x(e^t-1)$, so $\mathbb{E}[e^{t{X}_i}]\le 1+p_i(e^t-1)\le e^{p_i(e^t-1)}$ with $p_i=\mathbb{E}[X_i]$; by independence $\mathbb{E}[e^{tX}]\le e^{\mu (e^t-1)}$. Markov on $e^{tX}$ gives $\mathrm{Pr}[X\ge (1+\delta )\mu ]\le e^{\mu (e^t-1)-t(1+\delta )\mu }$; with $t=\ln (1+\delta )$ this is $(e^{\delta }/(1+\delta {)}^{1+\delta }{)}^{\mu }$. Since $\ln (1+\delta )\ge \frac{2\delta }{2+\delta }$, the exponent satisfies $(1+\delta )\ln (1+\delta )-\delta \ge \frac{{\delta }^2}{2+\delta }\ge \frac{{\delta }^2}{3}$ for $\delta \le 1$. The lower tail is the same computation with $t<0$ and $(1-\delta )\ln (1-\delta )+\delta \ge \frac{{\delta }^2}{2}$.

Backwards analysis example. Insert $n$ distinct numbers in random order and count how often the running minimum changes. The $i$-th inserted element is the minimum of the first $i$ with probability $\frac{1}{i}$ (any of them is equally likely to be last), so the expected number of changes is $H_n=O(\log n)$. Welzl and Seidel use the same argument: the last inserted constraint is “important” (defines the answer) with probability $O(d/i)$, so expensive recomputation is rare.

Derandomization

Method	Idea
conditional expectations	fix the random choices one at a time, always taking the branch whose conditional expectation stays at least the target
pairwise independence	many analyses need only pairwise independence: $O(\log n)$ random bits, which can be enumerated
fixed witness sets	Miller–Rabin with 7 fixed bases (or the first 12 primes) is deterministic for all 64-bit inputs: Primality and Factorization

Usually not worth it in practice, but conditional expectations is a genuine proof and construction technique. Example: a random side for every vertex cuts each edge with probability $\frac{1}{2}$, so some cut has at least $m/2$ edges; fixing vertices greedily finds one deterministically.

vector<int> halfCut(int n, const vector<pair<int, int>>& edges) {   // >= m/2 cut edges (no self-loops), O(n + m)
    vector<vector<int>> adj(n); for (auto [u, v] : edges) adj[u].push_back(v), adj[v].push_back(u);
    vector<int> side(n, -1);
    for (int v = 0; v < n; v++) {                       // put v opposite to the majority of its placed neighbours
        int c0 = 0, c1 = 0;
        for (int u : adj[v]) if (side[u] == 0) c0++; else if (side[u] == 1) c1++;
        side[v] = c0 >= c1 ? 1 : 0;
    }
    return side;
}

Proof: the conditional-expectation cut has at least m/2 edges

Let $E$ be the expected number of cut edges when the unplaced vertices are coloured at random. Initially $E=m/2$. Placing $v$ settles the edges from $v$ to already placed neighbours; edges to unplaced vertices stay cut with probability $\frac{1}{2}$ either way. Putting $v$ on the side opposite the majority cuts at least half of the settled edges, which is at least their expected contribution, so $E$ never decreases. At the end nothing is random and the cut has $E\ge m/2$ edges. Checked on random graphs.

Randomized algorithms worth knowing

Algorithm	Randomness used for	Note
quicksort, nth_element	pivot	Sorting
treap, skip list	priorities, levels	Treaps, Data Structure Catalog
Miller–Rabin, Pollard’s rho	witnesses, the pseudo-random walk	Primality and Factorization
Karger, Karger–Stein	random edge contraction	Global Min Cut
Welzl, Seidel’s LP	insertion order	Minimum Enclosing Circle, Linear Programming
string hashing, Zobrist and set hashing	the base, random weights	Hashing and Verification
Tutte matrix matching	matrix entries	General Matching
Freivalds’ check, Schwartz–Zippel	test vectors / points	Hashing and Verification
reservoir sampling, sketches	which item to keep, hash functions	Sampling and Streaming
color coding, random-walk SAT	random colours, random flips	Randomized Search
simulated annealing, MCTS	move acceptance, playouts	Heuristic Optimization, Game Search

When randomness is not allowed (some interactive or hacking formats, reproducibility-checking judges), read the statement; otherwise randomize by default: it costs one line and removes a whole category of failure.

Related notes

• Probability and Expectation
• Complexity Theory