Probability Basics for Algorithms

Why Probability Lives at the Heart of Algorithms

Most beginners meet algorithms in their deterministic form: given the same input, you get the same answer, every time. But almost every algorithm that scales — hash tables, skip lists, bloom filters, randomized quicksort, primality testing, neural-net training, consensus, load balancing — is analyzed probabilistically. Either the algorithm itself flips coins, or its inputs are modeled as random, or its performance is the expectation over the random choices the system makes. Probability is not an extra topic; it is the language in which the running times of modern data structures are written.

Mental model. Worst-case analysis answers "what could happen?" Average-case and randomized analysis answer "what does happen?" Real systems run a billion times a day; the right notion of cost is what happens on average, with high probability, not on the one adversarial input that might never appear.

This section gives you exactly the probability you need for the rest of the book: sample spaces and events, conditional probability and Bayes, expectation and the linearity trick that destroys 90% of seemingly hard analyses, variance, the three classical tail bounds (Markov, Chebyshev, Chernoff), and two paradigm-defining examples — the coupon collector and the birthday paradox — that explain, respectively, why caches get cold and why hash collisions happen far sooner than intuition suggests.

Sample Spaces, Events, and Axioms

A probability space is three objects:

1. A sample space $\Omega$ — the set of all possible outcomes of the random experiment.
2. A collection of events — subsets of $\Omega$. An event happens when the realized outcome lies inside the subset.
3. A probability measure $P$ assigning each event a number in $[0, 1]$.

For a fair die, $\Omega = \{1,2,3,4,5,6\}$, the event "even" is $E = \{2, 4, 6\}$, and $P(E) = \tfrac{3}{6} = \tfrac{1}{2}$.

Kolmogorov's Three Axioms

1. Non-negativity: $P(A) \geq 0$ for every event $A$.
2. Normalization: $P(\Omega) = 1$. Something happens.
3. Countable additivity: for pairwise disjoint events $A_1, A_2, \ldots$, $P\!\left(\bigcup_i A_i\right) = \sum_i P(A_i)$.

Two consequences are used constantly. The complement rule: $P(A^c) = 1 - P(A)$. And inclusion–exclusion for two events: $P(A \cup B) = P(A) + P(B) - P(A \cap B)$. Almost every probability puzzle in algorithms reduces to picking the right complementary event — we will use this trick to derive the birthday paradox in a moment.

Conditional Probability and Independence

The probability of event $A$ given that we know event $B$ happened is

$P(A \mid B) = \frac{P(A \cap B)}{P(B)}, \quad \text{provided } P(B) > 0.$

Conditioning is the operation that updates beliefs in light of new information. In algorithms it shows up whenever you say things like "given that the hash table has load factor $\alpha$, the expected probe length is ..."

Two events are independent when knowing one does not change the probability of the other:

$A \perp B \iff P(A \cap B) = P(A) \, P(B) \iff P(A \mid B) = P(A).$

Bayes' Rule and the Spam Filter

Rearranging the definition of conditional probability gives one of the most useful identities in computer science:

$P(A \mid B) = \frac{P(B \mid A) \, P(A)}{P(B)}.$

This is Bayes' rule. The denominator is usually expanded by the law of total probability: $P(B) = P(B \mid A) P(A) + P(B \mid A^c) P(A^c)$.

Worked example: the email spam filter

Suppose 30% of incoming email is spam, so $P(S) = 0.30$. The word "winner" appears in 60% of spam but only 1% of non-spam: $P(W \mid S) = 0.60$, $P(W \mid S^c) = 0.01$. Your inbox just received a message containing "winner." What is the probability it's spam?

Apply Bayes:

$P(S \mid W) = \frac{P(W \mid S) P(S)}{P(W \mid S) P(S) + P(W \mid S^c) P(S^c)} = \frac{0.60 \cdot 0.30}{0.60 \cdot 0.30 + 0.01 \cdot 0.70} = \frac{0.18}{0.187} \approx 0.963.$

A message containing "winner" is spam with probability about 96%. Notice three things: the prior $P(S)$ matters (raise it and the posterior climbs), the likelihood ratio $P(W\mid S) / P(W \mid S^c) = 60$ dominates, and the "evidence" $P(W)$ only enters as a normalizing constant. This is the entire mathematical engine of naive Bayes spam classifiers, the workhorse of email filtering before deep learning.

Random Variables and Expectation

A random variable $X$ is a function from the sample space to the reals, $X : \Omega \to \mathbb{R}$. Roll a die and let $X$ be the face value; $X(\omega) = \omega$. Random variables are the abstraction that lets us talk about numbers derived from random experiments — the running time of randomized quicksort, the number of probes in a hash table, the height of a skip list.

The expectation (mean, average value) of a discrete random variable is the probability-weighted sum:

$E[X] = \sum_{x} x \cdot P(X = x).$

For a fair six-sided die, $E[X] = (1+2+3+4+5+6)/6 = 3.5$. The expectation is not a value $X$ ever takes; it is the long-run average over many independent trials.

Linearity of Expectation: The Killer Technique

If there is one piece of probability you absolutely must internalize for algorithm analysis, it is this:

$E[X + Y] = E[X] + E[Y], \quad \text{regardless of whether } X, Y \text{ are independent.}$

And by induction, for any finite sum,

$E\!\left[\sum_{i=1}^{n} X_i\right] = \sum_{i=1}^{n} E[X_i].$

The independence-free clause is what makes this so powerful: you can decompose a complicated random variable into a sum of simple ones, compute each piece's expectation in isolation, and add. Many analyses that look like they need joint distributions in fact only need this one identity.

Indicator Variables: Quicksort and Empty Buckets

An indicator random variable $\mathbb{1}_A$ is 1 when event $A$ happens and 0 otherwise. Its expectation is exactly the probability: $E[\mathbb{1}_A] = P(A)$. The combination "decompose into indicators, then apply linearity" is a recipe that solves an enormous fraction of algorithmic expected-value questions.

Example 1: Expected number of empty buckets in a hash table

Throw $m$ keys into $n$ buckets uniformly at random. Let $X$ be the number of empty buckets. What is $E[X]$?

Let $X_i = \mathbb{1}\{\text{bucket } i \text{ is empty}\}$. Then $X = X_1 + X_2 + \ldots + X_n$. The probability that bucket $i$ is missed by all $m$ independent throws is $(1 - 1/n)^m$, so $E[X_i] = (1 - 1/n)^m$. By linearity,

$E[X] = n \left(1 - \tfrac{1}{n}\right)^m \approx n \, e^{-m/n}.$

The same indicator trick gives the expected size of any bucket ($m/n$, the load factor) and the expected number of collisions. This is the entire average-case analysis of chained hashing in three lines.

Example 2: Expected comparisons in randomized quicksort

Pick a random pivot at every recursive call. For input $[a_1, \ldots, a_n]$ with sorted order $s_1 < s_2 < \ldots < s_n$, let $X_{ij}$ be the indicator that $s_i$ and $s_j$ are compared during the run ($i < j$). Two elements are compared iff one of them is the first pivot chosen from the range $\{s_i, \ldots, s_j\}$; among the $j - i + 1$ elements in that range, exactly two ($s_i$ and $s_j$) trigger a comparison, so $P(X_{ij} = 1) = 2 / (j - i + 1)$. Then

$E[\text{comparisons}] = \sum_{i < j} \frac{2}{j - i + 1} = 2 \sum_{k=2}^{n} (n - k + 1)\frac{1}{k} \leq 2 n H_n = O(n \log n).$

Three lines of indicator-plus-linearity reproduce the famous $O(n \log n)$ expected runtime of randomized quicksort — without ever solving a recurrence.

Variance and Concentration

Expectation tells you the center of a distribution. To know how tightly the random variable concentrates around that center, you need the second moment. Variance is defined as

$\mathrm{Var}(X) = E\!\left[(X - E[X])^2\right] = E[X^2] - (E[X])^2.$

The square root, $\sigma_X = \sqrt{\mathrm{Var}(X)}$, is the standard deviation — the typical deviation from the mean, in the same units as $X$.

Unlike expectation, variance is not linear in general. But for independent random variables it is:

$X \perp Y \Rightarrow \mathrm{Var}(X + Y) = \mathrm{Var}(X) + \mathrm{Var}(Y).$

For a sum of $n$ independent identically distributed random variables, the standard deviation grows like $\sqrt{n}$, not like $n$. This $\sqrt{n}$ scaling is why averages over large samples concentrate — and is the reason Monte Carlo methods work at all.

Markov, Chebyshev, Chernoff

Tail bounds answer the question: how unlikely is it for $X$ to be far from its mean? Three classical inequalities, each tighter than the last, are the workhorses of randomized algorithm analysis.

Markov's inequality — the dumbest bound

For any non-negative random variable $X$ and $a > 0$,

$P(X \geq a) \leq \frac{E[X]}{a}.$

Why "dumbest"? Because it uses only the mean, no higher-order information. Yet it is enough to prove, for example, that a randomized algorithm with expected running time $T$ exceeds $10 T$ with probability at most $1/10$.

Chebyshev's inequality — uses the variance

$P\!\left(|X - E[X]| \geq k \sigma_X\right) \leq \frac{1}{k^2}.$

At $k = 2$, at most 25% of the mass lies more than two standard deviations from the mean — for any distribution with finite variance. The price for generality is that Chebyshev is loose for nice distributions (Gaussians have only ~5% past $2\sigma$).

Chernoff bounds — exponentially tight for sums of indicators

For $X = \sum_{i=1}^{n} X_i$ a sum of independent $\{0,1\}$ indicators with $\mu = E[X]$, and any $\delta > 0$,

$P\!\left(X \geq (1 + \delta) \mu\right) \leq \exp\!\left(-\frac{\delta^2 \mu}{2 + \delta}\right).$

The probability of a large deviation decays exponentially in $\mu$. This is what makes randomized load balancing, sketching, and PAC-learning work: with sample size $O(\log(1/\delta) / \varepsilon^2)$ you get $\varepsilon$-accurate estimates with confidence $1 - \delta$. Chernoff is the reason a hash function with two-universal independence is essentially as good as a fully random function for most analyses.

Coupon Collector: Why Caches Get Cold

You buy cereal boxes; each one contains a uniformly random coupon from a set of $n$ distinct coupons. How many boxes do you expect to buy before you have all $n$?

Decompose: let $T_i$ be the number of additional boxes needed to get a new coupon, given that you already have $i - 1$ distinct coupons. The chance that any particular box gives a new coupon is $(n - i + 1)/n$, so $T_i$ is geometric with mean $E[T_i] = n / (n - i + 1)$. The total time is $T = T_1 + T_2 + \ldots + T_n$, and by linearity of expectation,

$E[T] = \sum_{i=1}^{n} \frac{n}{n - i + 1} = n \sum_{k=1}^{n} \frac{1}{k} = n \, H_n \sim n \ln n.$

The harmonic number $H_n$ from the previous sections returns! Collecting all $n$ coupons takes $\Theta(n \log n)$ draws on average. That extra $\log n$ factor is the reason the last few coupons take so long — the same reason an LRU cache spends a disproportionate fraction of misses on the rarest items.

The Birthday Paradox

Throw $m$ balls into $n$ bins independently and uniformly. What is the probability that some bin gets two or more balls?

The complement — all balls land in distinct bins — is easier:

$P(\text{no collision}) = \frac{n}{n}\cdot\frac{n-1}{n}\cdot\frac{n-2}{n}\cdots\frac{n-m+1}{n} = \prod_{i=0}^{m-1}\left(1 - \frac{i}{n}\right).$

Therefore, $P(\text{collision}) = 1 - \prod_{i=0}^{m-1}(1 - i/n)$. Using $1 - x \leq e^{-x}$, we get the approximation

$P(\text{collision}) \approx 1 - \exp\!\left(-\binom{m}{2}/n\right) \approx 1 - \exp\!\left(-\tfrac{m^2}{2n}\right).$

The collision probability hits 1/2 when $m \approx \sqrt{2 n \ln 2} \approx 1.177 \sqrt{n}$. For $n = 365$ days, that is $m \approx 22.5$ — the famous result that 23 randomly chosen people are more likely than not to share a birthday. The headline takeaway, used everywhere in computer science:

Birthday principle. When drawing $m$ items uniformly from a set of size $n$, the first collision happens at $m = \Theta(\sqrt{n})$, not at $m = \Theta(n)$.

This is why a 64-bit hash gives only ~32 bits of collision resistance — you can find a collision in roughly $2^{32}$ evaluations. It is why MD5 is broken for collision resistance long before it is broken for preimages. It is why hash tables collide far earlier than load factor 1, and why every well-designed system either chains, uses a much larger digest (SHA-256), or salts its hash inputs.

Interactive: Birthday Paradox Simulator

Use the controls below to set the bin count $n$ and the draw count $m$, then run a Monte Carlo sample. The blue bar shows the theoretical collision probability from the closed-form formula; the amber bar shows the empirical fraction of trials in which at least one collision occurred. Watch how rapidly the empirical estimate snaps onto the theoretical value as you increase trials — that is the law of large numbers, and the reason simulation works as a verification tool.

Try the "Birthdays" preset with $m = 23$ — you should see ~50%. Now set $n = 256$ with $m = 20$; despite drawing only 20 items, a collision happens about 55% of the time. The histogram shows when the first collision tends to fall — for small $n$, the first-collision draw is concentrated near $\sqrt{n}$, not uniformly distributed.

Code: Monte Carlo in Python and TypeScript

Two implementations of the same Monte Carlo experiment we just ran in the browser. We deliberately use the same algorithm in both languages so you can see the math survive translation: pick $m$ uniformly random integers in $[0, n)$, return whether any value repeats, repeat $T$ times, divide.

Python: NumPy-free, dependency-free, easy to read

m=23, n=365 -> draw 23 integers in [0, 365); ~50% of trials hit a duplicate.

n=365 -> values like 142, 7, 298, ... .

If x=142 was drawn earlier this trial, x in seen is True -> return.

trials=20,000 gives empirical estimates accurate to about ±0.007 by Chebyshev.

For m=23, n=365: the product is ≈ 0.493, so collision probability ≈ 0.507.

1import random
2from math import prod
3
4def has_collision(m: int, n: int) -> bool:
5    """Throw m balls into n bins; return True iff any bin gets 2+ balls."""
6    seen = set()
7    for _ in range(m):
8        x = random.randrange(n)        # uniform in [0, n)
9        if x in seen:
10            return True
11        seen.add(x)
12    return False
13
14def empirical_collision_prob(m: int, n: int, trials: int = 10_000) -> float:
15    hits = sum(has_collision(m, n) for _ in range(trials))
16    return hits / trials
17
18def theoretical_collision_prob(m: int, n: int) -> float:
19    if m > n:
20        return 1.0
21    return 1 - prod((n - i) / n for i in range(m))
22
23# Demonstration: classic birthdays, n = 365
24random.seed(0)
25m, n = 23, 365
26emp = empirical_collision_prob(m, n, trials=20_000)
27thr = theoretical_collision_prob(m, n)
28print(f"m={m}, n={n}: empirical={emp:.3f}, theoretical={thr:.3f}")
29# Output (deterministic with seed=0):
30#   m=23, n=365: empirical=0.510, theoretical=0.507

TypeScript: same algorithm, browser-ready

n=365, Math.random()=0.4127 -> Math.floor(150.63) = 150.

trials=20,000, hits ~ 10,150 -> empirical ~ 0.508.

1function hasCollision(m: number, n: number): boolean {
2  // Single trial: m balls into n bins, return true on first repeat.
3  const seen = new Set<number>();
4  for (let i = 0; i < m; i++) {
5    const x = Math.floor(Math.random() * n);   // uniform in [0, n)
6    if (seen.has(x)) return true;
7    seen.add(x);
8  }
9  return false;
10}
11
12function empiricalCollisionProb(m: number, n: number, trials: number): number {
13  let hits = 0;
14  for (let t = 0; t < trials; t++) if (hasCollision(m, n)) hits++;
15  return hits / trials;
16}
17
18function theoreticalCollisionProb(m: number, n: number): number {
19  if (m > n) return 1;
20  let p = 1;
21  for (let i = 0; i < m; i++) p *= (n - i) / n;
22  return 1 - p;
23}
24
25// Birthday paradox, m = 23 people, n = 365 days
26const m = 23, n = 365;
27const emp = empiricalCollisionProb(m, n, 20_000);
28const thr = theoreticalCollisionProb(m, n);
29console.log(`empirical=${emp.toFixed(3)} theoretical=${thr.toFixed(3)}`);
30// e.g. empirical=0.508 theoretical=0.507

Where Probability Powers Real Systems

Almost every modern data structure and algorithm derives its guarantees from probability. A short tour:

In every row of that table, removing the probability collapses the guarantee: a deterministic quicksort has $O(n^2)$ worst-case, a deterministic skip list is impossible to define cleanly, a deterministic primality test (AKS, 2002) is much slower than Miller-Rabin in practice. Modern systems pay for randomness in coin flips and get back simplicity, speed, or both.

Pitfalls and Probabilistic Fallacies

1. Confusing $P(A \mid B)$ with $P(B \mid A)$ (the prosecutor's fallacy)

"The probability of this DNA match by chance is 1 in a million" is $P(\text{match} \mid \text{innocent})$; the question the jury cares about is $P(\text{innocent} \mid \text{match})$. Bayes with the population prior often gives wildly different numbers, as the medical-test QuickCheck above made vivid. Always pin down which conditional probability you actually mean.

2. Assuming independence when events are correlated

The 2008 financial crisis was, in part, a probability bug: mortgage defaults across geographies were modeled as independent. They were not. Independence is a strong assumption and must be justified, not defaulted to.

3. Ignoring variance (the St. Petersburg paradox)

A game pays $2^k$ dollars when a fair coin first lands heads on flip $k$. The expected payoff is $E[X] = \sum_{k=1}^{\infty} 2^k \cdot 2^{-k} = \infty$. Yet nobody would pay even \$50 to play. The expectation is infinite but the distribution is so heavy-tailed that any finite sample is dominated by tail outliers; mean is the wrong summary statistic. Variance and tail bounds matter.

4. The hot-hand fallacy and its inverse

Independent Bernoullis can produce streaks that look suspicious. Conversely, "regression to the mean" is a real statistical effect, not a causal one. When you see a pattern in random data, ask: would I see this often by chance alone? That is what hypothesis testing answers, and what every randomized algorithm's analysis must rule out.

Probability is the bridge between the deterministic algorithms of Chapter 2 and the randomized data structures we will meet starting in Chapter 9. Every claim of the form "hash table lookup is $O(1)$" or "skip list height is $O(\log n)$" or "quicksort runs in $O(n \log n)$" carries an unspoken clause: in expectation, with high probability, over the algorithm's random choices. Understanding what those clauses mean — and what they do not promise — is the difference between a system that performs well in benchmarks and a system that performs well in production.