Indicator random variables, and the move that turns a hope about your input into a guarantee about your algorithm.
Chapter 5 closes Part I with the last analytical tool: probability. It does two distinct things that are easy to conflate. Probabilistic analysis assumes a distribution over inputs and computes an average-case running time — useful, but only as trustworthy as the assumption. Randomization puts the randomness inside the algorithm, so the guarantee holds for every input and depends only on the coin flips you control. The technical workhorse for both is the indicator random variable, a device so simple it looks like a triviality and so effective that it carries the analysis of quicksort, hashing, and much else.
You are hiring an office assistant through an agency. Each day the agency sends one candidate. Interviewing costs cᵢ and hiring costs cᵗ, with cᵗ ≫ cᵢ because hiring means paying the agency a fee and firing the current assistant. You are committed to always having the best candidate seen so far in the job, so you hire immediately whenever someone better walks in.
HIRE-ASSISTANT(n)
1 best = 0 // candidate 0 is a least-qualified dummy
2 for i = 1 to n
3 interview candidate i
4 if candidate i is better than candidate best
5 best = i
6 hire candidate iThe question is not the running time, which is obviously Θ(n). It is the hiring cost: how many times does line 6 execute?
If m candidates are hired, the total cost is O(cᵢn + cᵗm). The cᵢn term is fixed; m is what varies, and since cᵗ is large, m is what matters.
The worst case is easy: if candidates arrive in strictly increasing order of quality, every single one is better than all before, so every one is hired. Then m = n and the cost is O(cᵗn).
That bound is correct and nearly useless. It describes one very specific arrival order out of n! possibilities, and it tells you nothing about what will actually happen. Worst-case analysis was the right instinct in Chapter 2, where the worst case was reachable by an ordinary input like a reverse-sorted array. Here it requires the agency to conspire against you.
So make an assumption about the input and average over it.
For the hiring problem the natural assumption is that the candidates arrive in a uniform random order: all n! permutations of the ranking are equally likely. Equivalently, the ranks form a uniform random permutation of ⟨1, 2, …, n⟩.
Before analysing anything, the chapter introduces the tool. It is deceptively small.
A, the indicator random variable I{A} is defined as 1 if A occurs and 0 if it does not.And then the lemma that makes it useful:
Lemma 5.1
For an event A, let Xᵀ = I{A}. Then E[Xᵀ] = Pr{A}.
Proof: E[Xᵀ] = 1·Pr{A} + 0·Pr{not A} = Pr{A}.Stated that way it looks like nothing. Its power comes from combining it with linearity of expectation, which says E[X + Y] = E[X] + E[Y] whether or not X and Y are independent. That freedom from independence is the whole trick.
n separate questions of the form “what is the chance of this one event?”Let X be the number of candidates hired. Computing E[X] from its distribution would mean finding, for each m, the probability that exactly m hires happen — painful. Instead, decompose.
Let Xᵢ = I{candidate i is hired}. Then X = X₁ + X₂ + … + Xₙ.
Now the key question: what is Pr{candidate i is hired}? Candidate i is hired exactly when they are better than all of candidates 1 through i-1 — that is, when candidate i is the best of the first i. Since the order is uniformly random, each of the first i candidates is equally likely to be the best of that group. So the probability is 1/i.
E[Xᵢ] = Pr{candidate i is hired} = 1/i
E[X] = ∑ from i=1 to n of E[Xᵢ]
= ∑ from i=1 to n of 1/i
= Hₙ // the nth harmonic number
= ln n + O(1)n candidates are interviewed, only about ln n are hired on average. Expected hiring cost is O(cᵗ ln n) instead of the worst case O(cᵗ n) — an exponential improvement in the number of expensive operations.Notice what the indicator method sidestepped. The events “candidate i is hired” are not independent — whether candidate 5 was hired tells you something about the relative ordering that affects candidate 6. Linearity of expectation does not care. That is the entire reason this technique dominates the rest of the book.
n | Worst case hires | Expected hires ≈ ln n |
|---|---|---|
| 10 | 10 | 2.9 |
| 100 | 100 | 5.2 |
| 1,000 | 1,000 | 7.5 |
| 1,000,000 | 1,000,000 | 14.4 |
The analysis above rests on an assumption we cannot enforce: that the agency sends candidates in random order. Suppose it does not. Suppose it sends them in increasing order of quality on purpose, to maximise its fees.
n candidates first, then randomly permute the list before running the hiring procedure. Now the order really is uniformly random, because you made it so.RANDOMIZED-HIRE-ASSISTANT(n)
1 randomly permute the list of candidates
2 HIRE-ASSISTANT(n)An algorithm is randomized if its behaviour is determined not only by its input but also by values produced by a random-number generator. CLRS assumes a procedure RANDOM(a, b) returning an integer uniformly from {a, …, b}, with each call independent.
The distinction this creates is the most important idea in the chapter:
| Average-case running time | Expected running time | |
|---|---|---|
| Randomness comes from | The input distribution, which you assume | The algorithm’s own coin flips, which you control |
| Guarantee applies to | Inputs drawn from that distribution | Every input, without exception |
| Defeated by | An adversary who knows the distribution is wrong | Nothing — an adversary cannot see your coin flips |
| No bad inputs, only | — | bad runs, which are unlikely and not repeatable |
The last row is the practical payoff. For a randomized algorithm there is no such thing as a bad input. The same input run twice may take different times, and the probability of a slow run is small on every input. This is exactly why randomized quicksort in Chapter 7 is preferred to deterministic quicksort with a fixed pivot rule: the latter has real inputs that trigger Θ(n²), and an attacker who knows your pivot rule can construct them.
The randomization step has to be correct, or the whole argument collapses. CLRS gives two methods.
PERMUTE-BY-SORTING(A, n)
1 let P[1:n] be a new array
2 for i = 1 to n
3 P[i] = RANDOM(1, n³) // random priority
4 sort A, using P as sort keysCost Θ(n lg n). The range n³ is chosen so that all priorities are distinct with probability at least 1 - 1/n; ties would bias the result.
RANDOMIZE-IN-PLACE(A, n)
1 for i = 1 to n
2 swap A[i] with A[RANDOM(i, n)]Two lines, Θ(n) time, no extra space. This is the Fisher-Yates shuffle, and it is what every correct shuffle implementation does.
Correctness is proved with a loop invariant, and it is a good example of one:
ith iteration, for each possible (i-1)-permutation of the n elements, the subarray A[1:i-1] contains that particular (i-1)-permutation with probability (n-i+1)! / n!.At termination i = n+1, so A[1:n] contains any given n-permutation with probability (n-n)!/n! = 1/n! — a uniform random permutation, which is what was required.
RANDOM(1, n) instead of RANDOM(i, n) on line 2 gives an algorithm that looks fine, runs fine, and produces a biased distribution. It can generate nⁿ equally likely outcome sequences, but there are only n! permutations, and n! does not divide nⁿ for n > 2, so the permutations cannot come out equally likely. The bug is invisible without either the proof or a statistical test. This is a real bug that has shipped in real code.Section 5.4 works through four classic problems whose answers you should know by shape. The first: how many people must be in a room before two share a birthday, with probability above ½?
With k people and n = 365 days, the probability that all birthdays are distinct is
Pr{all distinct} = (1)(1 - 1/n)(1 - 2/n)…(1 - (k-1)/n)
≤ e-k(k-1)/2n // using 1 + x ≤ eˣThis drops below ½ when k(k-1) ≥ 2n ln 2, that is roughly k ≥ √(2n ln 2) ≈ 1.18√n. For n = 365 that gives k = 23.
The same conclusion comes out of the indicator method in one line. Let Xᵢⱼ = I{person i and person j share a birthday} for i < j. Each has expectation 1/n, and there are C(k,2) pairs, so the expected number of matching pairs is C(k,2)/n = k(k-1)/2n. Setting that to 1 gives k ≈ √(2n), which for 365 is about 28 — the right order, obtained with almost no work.
√n threshold is why hash collisions appear far sooner than intuition suggests: with n slots you expect a collision after about √n insertions, not n/2. It also sets the security level of hash functions — a 256-bit hash gives only 128 bits of collision resistance.Throw balls one at a time into b bins, each throw uniform and independent. Two standard questions:
| Question | Answer | Known as |
|---|---|---|
Expected balls in a given bin after n throws | n/b | Uniformity |
| Expected throws until some bin has 2 balls | Θ(√b) | Birthday paradox |
| Expected throws until every bin has at least 1 ball | b ln b + O(b) | Coupon collector |
The coupon collector derivation is a nice use of decomposition. Call it “stage i” when exactly i-1 bins are occupied. In that stage the chance a throw hits an empty bin is (b-i+1)/b, so the expected number of throws to finish the stage is b/(b-i+1). Summing over stages:
E[throws] = ∑ from i=1 to b of b/(b-i+1)
= b · ∑ from i=1 to b of 1/i
= b·Hᵇ = b ln b + O(b)The harmonic number appears again. It is worth noticing how often ln n shows up once you start summing 1/i.
Flip a fair coin n times. How long is the longest run of consecutive heads? The answer is Θ(lg n) — specifically, the expected longest streak is Θ(lg n), and the probability of a streak much longer than lg n falls off fast.
The intuition: a specific streak of length s starting at a given position has probability 1/2ˢ, and there are about n starting positions, so the expected count of length-s streaks is about n/2ˢ. That is around 1 when s = lg n, and drops sharply above it.
A variant with a genuinely surprising answer. Now you must decide immediately after each interview whether to hire, with no going back, and you want to hire the single best candidate overall. You interview once and commit once.
The strategy: reject the first k candidates outright, recording the best score among them. Then hire the first subsequent candidate who beats all of the first k. If nobody does, you are stuck with the last one.
ONLINE-MAXIMUM(k, n)
1 best-score = -∞
2 for i = 1 to k
3 if score(i) > best-score
4 best-score = score(i)
5 for i = k+1 to n
6 if score(i) > best-score
7 return i
8 return nThe analysis gives the probability of success as roughly (k/n)·ln(n/k). Maximising over k by differentiating gives k = n/e, and the resulting success probability is 1/e.
n/e ≈ 37% of candidates, then take the first one better than all of them. You hire the genuinely best candidate with probability at least 1/e ≈ 37% — and remarkably, this does not decay as n grows. With a million candidates and one irrevocable choice, you still win more than a third of the time.This is the classic secretary problem, and it is the chapter’s best advertisement for probabilistic thinking: an intuition-defying result, obtained with the same tools used everywhere else.
I{A} is 1 if A happens, else 0. Lemma 5.1: E[I{A}] = Pr{A}.i is hired with probability 1/i, so the expected number of hires is Hₙ = ln n + O(1), against a worst case of n.swap A[i] with A[RANDOM(i, n)]. Using RANDOM(1, n) instead is a real and invisible bias bug.√n), coupon collector (b ln b to fill every bin), streaks (longest run is Θ(lg n)), and the secretary problem (skip n/e, succeed with probability 1/e).Part I is finished. Part II opens with heapsort in Chapter 6, which introduces the heap — the first real data structure in the book and the basis of the priority queue. Chapter 7 then applies this chapter’s randomization directly: randomized quicksort has expected running time Θ(n lg n) on every input, proved with exactly the indicator-variable technique developed here.