Probabilistic Analysis & Randomized Algorithms

By the end of this lesson you will be able to trace the hireAssistant scan for the classic hiring problem and explain, using indicator random variables, why hiring in random order costs only Θ(ln n) expected hires instead of Θ(n) in the worst case; implement and PROVE correct two ways of generating a uniformly random permutation (permuteBySorting and the Fisher–Yates randomizeInPlace) and spot the classic biased-shuffle bug; and reason about the birthday paradox, balls-and-bins/coupon-collector, coin-flip streaks, and the on-line "secretary problem" with simple counting arguments.

This lesson assumes you already know what a random variable, expectation, linearity of expectation, and an indicator random variable are — those are built up carefully with dice, coins and Bayes' theorem in M02 · Counting & Probability. If any of those words are unfamiliar, read M02 first; this lesson goes deep on the algorithms and proofs that use them, rather than re-deriving the probability toolkit itself.

1. The hiring problem & hireAssistant

You're staffing a desk through an agency. Every candidate you interview costs a little money (c_i) whether or not you hire them. Every time you fire your current assistant and hire someone better, it costs a lot more (c_h ≫ c_i) — think agency fees, onboarding, and paying off the person you just let go. You interview candidates ONE AT A TIME, in whatever order they show up, and every time the new candidate is better than your current best, you hire them on the spot (you can never "go back" to someone you passed on). The question to answer: how many times do you expect to actually HIRE someone, out of n interviews?

The scan in Algoistan pseudocode (0-indexed, exactly like the Dart code below). Starting best at −∞ acts like an imaginary candidate who is worse than everyone, so the first real candidate always gets hired:

Total cost is O(c_in + c_hm), where m is however many times lines 5–6 actually fire. The c_in part is fixed — you always interview all n people. The interesting, variable part is m, the number of hires.

The worst case is exactly the "every candidate is better than the last" order (strictly increasing quality) — you hire all n times, giving the very worst possible cost O(c_hn). Nothing is wrong with the algorithm; the danger is entirely in what order the candidates happen to arrive in, which hireAssistant has zero control over.

Try any sequence of distinct quality scores yourself (higher number = better candidate):

Dart implementation. The Dart version is the pseudocode almost word for word, because both are 0-indexed: candidate i is quality[i]. The only translation is the starting value: best ← −∞ becomes a sentinel guaranteed worse than any real quality score:

Input size → what’s feasible. one pass, Θ(n) time and O(1) space: n = 10⁷ candidates is about 10⁷ steps (< 0.1 s). The count of hires is at most n, so storing every hire is O(n) memory — keep only the counter if memory matters.

hireAssistant always interviews all n candidates. How many times it HIRES depends entirely on the order candidates arrive in — anywhere from 1 (already-best-first) to n (worst-to-best order).

2. Probabilistic analysis vs. randomized algorithms

These sound similar but answer two genuinely different questions, and it pays to keep them separate:

Probabilistic analysis (average case): assume something about the input, e.g. "candidates arrive in a uniformly random order" — then compute the expected cost under that assumption. This is only meaningful if the assumption about the world is actually true. If some real hiring agency always sends candidates in increasing order of quality (to build suspense, say), the "average case" analysis is simply wrong for that agency.
Randomized algorithms (expected case): make NO assumption about the input order at all. Instead, the algorithm itself uses its own random choices (a call to randomInt(a, b), returning a uniform random integer in [a,b]) to guarantee good expected behavior no matter what order the input arrives in. No adversary, however clever, can force a bad case by choosing a bad input order — because the algorithm's own coin flips, not the input, decide what happens.

randomInt(a, b) in Dart — the closed range [a, b] has b − a + 1 values, so nextInt gets that count and the result is shifted up by a:

Same math (both give Θ(ln n) expected hires here), completely different guarantee. Probabilistic analysis trusts an assumption about the world; a randomized algorithm trusts its own dice. We compute the first in Section 3 (Rule 2) and the second in Section 4 (Rule 3).

3. Indicator random variables: why random order gives Θ(ln n) hires

An indicator random variable for an event A, written X_A, is 1 if A happens and 0 if it doesn't. Rule 1 (indicator expectation): E[X_A] = Pr{A} — its expectation is just the plain probability of the event, by definition (1·Pr{A} + 0·Pr{not A} = Pr{A}). The power comes from linearity of expectation (M02 §9): you can add up expectations of many indicators even if the underlying events are tangled together and NOT independent.

Assume candidates arrive in a uniformly random order (this is the "probabilistic analysis" assumption from Section 2). Define X_i = 1 if candidate i gets hired, else 0. Candidate i gets hired exactly when candidate i is the best of the first i candidates seen so far — and because the order is uniformly random, candidate i is equally likely to be the best, 2nd best, ..., or worst of those first i. So:

Rule 1 and the value of E[X_i], as code (the first i arrivals are the indices 0..i-1); the enumeration tries ALL n! orders:

By linearity of expectation, the expected total number of hires is:

The sum and the ln n bound, checked numerically:

Input size → what’s feasible. computing H_n is O(n); even n = 10⁶ gives only about 14.39 expected hires, which is why random order makes hireAssistant cheap at any realistic size.

H_n is the n-th harmonic number, which grows like ln n (see M02 §9–10 for the full derivation with the hat-check problem). This is Rule 2 (random-order hiring): assuming random arrival order, hireAssistant's expected hiring cost is O(c_h ln n) — a dramatic improvement over the worst case of O(c_hn) from Section 1.

This isn't just "close" — the claim is exact. For every one of the n! possible arrival orders, run hireAssistant and count the hires; average that count over all n! orders and you get precisely H_n, not merely "roughly". verify/c05.dart checks this by brute force for n = 1..6: it tries every single permutation, counts every single hire, and confirms the average equals H_n to floating-point precision.

The same "define an indicator per opportunity, sum with linearity" trick works for the hat-check problem, expected inversions in a random permutation, and dozens of other counting puzzles — it is the single most reusable technique in this chapter.

4. Randomizing the algorithm itself: randomizedHireAssistant

Section 3's Θ(ln n) guarantee only holds IF the input really does arrive in random order — an assumption. randomizedHireAssistant removes the assumption: first randomly permute the candidate list yourself (Sections 5–6 show two ways to do that correctly), THEN run the ordinary hireAssistant logic on your own shuffled copy.

Dart implementation (0-indexed; it reuses randomizeInPlace from §6 on a copy so the caller’s list is untouched):

Input size → what’s feasible. Θ(n) shuffle + Θ(n) scan = Θ(n) time, O(n) extra space for the copy; fine up to n ≈ 10⁷.

This is exactly Rule 3 (shuffle first): no matter what order candidates actually show up in — even a deliberately adversarial worst-case order — after you shuffle them yourself, the situation is mathematically identical to the random-order assumption of Section 3. Expected hiring cost is O(c_h ln n), guaranteed, for every possible input.

Rule 2 (Section 3) is an assumption about the world: "candidates happen to arrive randomly." Rule 3 is a property of your algorithm: "I randomize, so I don't care how they arrive." Confusing "average case" with "expected case" is one of the most common mix-ups in algorithm analysis interviews.

5. permuteBySorting

The simplest way to shuffle: give every element a random "raffle ticket" number, then sort by ticket number. Whoever drew the lowest ticket goes first, and so on.

Each element gets a random priority p[i] ← randomInt(1, n³) — we deliberately use a HUGE range (n³, not just n) so that two elements are very unlikely to draw the exact same priority (a union bound shows Pr{all distinct} ≥ 1 - 1/n; the interview bank walks through it). Then a comparison sort orders the array by priority: total cost is dominated by the sort, Θ(n lg n).

Rule 4 (sort-shuffle is uniform) (why this produces a uniform random permutation, assuming all priorities are distinct): for ANY specific target ordering you might want, the probability the sort produces exactly that ordering is Pr{P[i₁] is smallest} × Pr{P[i₂] is 2nd-smallest | ...} × ... = 1/n × 1/(n-1) × ... × 1/1 = 1/n! — via the chain rule of conditional probability. Since this works out to exactly 1/n! for EVERY one of the n! possible orderings, every ordering is equally likely: a uniform random permutation, by definition.

Rule 4’s counting argument, run for real on n = 3 with priorities in [1, 27] (n³ = 27): every ordering is produced by the same number of distinct-priority tuples.

What if the priority range is too small and priorities DO collide? Here the algorithm is asked to shuffle just 3 elements using a much smaller range than n³, so you can actually see collisions happen and how the tie gets broken by whichever comparison sort is used underneath:

A collision (two equal priorities) doesn't crash the algorithm — a stable-or-not sort just picks SOME order for the tied elements — but it DOES break the clean 1/n! proof above, because now some orderings become impossible or more likely than others depending on the sort's tie-breaking rule. That is exactly why we insist on a range as large as n³: it makes collisions so rare (probability O(1/n), Ex 5.3-5) that they essentially never bias real runs, without literally forbidding them.

The tie bound as code — the exact probability that all n priorities in [1, n³] are distinct, against the union bound used in the proof:

Try your own list of items — priorities use the full, safe n³ range:

Dart implementation. The pseudocode's p becomes a List<int> of length n, and "sort a by p" becomes sorting an index array by priority (so the same code works for a List<T> of any element type, not just integers) — everything else translates directly, since both are 0-indexed:

Input size → what’s feasible. Dart’s Random.nextInt only accepts a range up to 2³², so the n³ range works for n ≤ 1625; for n up to about 10⁵ in Θ(n lg n) ≈ 1.7·10⁶ comparisons it is fine, but at n = 10⁶ or above prefer randomizeInPlace (Θ(n)).

permuteBySorting: Θ(n lg n) time (dominated by the sort), needs Θ(n) extra space for the priorities array, produces an EXACTLY uniform permutation as long as priorities are distinct (near-certain with range n³).

6. randomizeInPlace (Fisher–Yates)

A faster shuffle that needs no extra array and no sorting at all: walk the array left to right, and at each position i, swap it with a uniformly random position chosen from the SHRINKING remaining suffix [i, n] — never from the whole array. This is the classic Fisher–Yates shuffle.

Only Θ(n) time, in place, no extra array needed — better than permuteBySorting's Θ(n lg n).

Rule 5 (loop invariant) (why the Fisher–Yates shuffle is uniform): before each iteration i, for each possible arrangement of i elements, the prefix a[0..i-1] holds exactly that arrangement with probability (n-i)!/n!.

Initialization (i=0): the prefix a[0..-1] is empty, and the "0-arrangement" of nothing happens with probability 1 — and indeed (n-0)!/n! = 1. Trivially true.
Maintenance: assume the invariant holds before iteration i. The swap picks one of n-i equally likely elements from the suffix a[i..n-1] to place at position i. Combining "which fixed i-arrangement was already in place" with "which of the n-i remaining elements landed at position i" and multiplying probabilities shows every (i+1)-arrangement of a[0..i] now occurs with probability exactly (n-i-1)!/n! — the same formula, one step forward.
Termination: at i = n, the formula gives (n-n)!/n! = 1/n! for the full array — EVERY permutation of all n elements is equally likely. QED.

Rule 5’s invariant as code: run the first i iterations under every possible choice sequence and count each prefix. Each i-permutation arises from exactly one sequence, so its probability is 1/(n(n−1)…(n−i+1)) = (n−i)!/n!:

The proof above is abstract — here it is made concrete for the smallest interesting case, n=3. There are exactly 3 × 2 × 1 = 6 possible sequences of random choices the algorithm can make, and the bijection argument says each one produces a DIFFERENT one of the 3! = 6 final orderings — a perfect one-to-one match, checked exhaustively (not sampled) in verify/c05.dart:

Try your own array and see the swap trace (each run reseeds the animation's random generator so replaying gives a different shuffle):

Dart implementation. The pseudocode loop for i from 0 to n − 1 with randomInt(i, n − 1) is the Dart loop for (i = 0; i < n; i++) with i + rng.nextInt(n - i): nextInt(n - i) returns one of exactly n - i equally likely offsets, and adding i maps them onto the positions i..n-1 — the n - i equally likely choices the proof needs:

Input size → what’s feasible. Θ(n) time, O(1) space: n = 10⁶ is 10⁶ swaps (< 0.05 s); n = 10⁷ still fits. In one line: randomInt(i, n − 1) is Dart i + nextInt(n - i).

Now the classic bug: swap position i with a random index from the WHOLE array [0, n-1] every time, instead of the shrinking suffix [i, n-1]:

The buggy shuffle and the exhaustive tally that exposes it (every choice sequence tried, no sampling):

This "obviously equivalent" variant is provably NOT uniform. For n=3 there are 3³ = 27 equally likely sequences of random choices, but only 3! = 6 possible final orderings — and 27 does not divide evenly by 6, so by the pigeonhole principle some orderings MUST come out more often than others. The exact split (checked by full enumeration in verify/c05.dart): three orderings occur 4/27 of the time, the other three occur 5/27 of the time. Always swap with the SHRINKING suffix [i, n-1], never the whole array — see also M02 §15 for the same bug from the counting-argument side.

randomizeInPlace: Θ(n) time, O(1) extra space, exactly uniform — strictly better than permuteBySorting on every axis except code simplicity. The ONE rule that makes it correct: the swap partner's range must SHRINK by one each iteration.

7. The birthday paradox

In a room of just 23 people, there's better than a 50% chance two of them share a birthday — a number that surprises almost everyone the first time they hear it. There are two ways to see why, and both matter for algorithm analysis: hashing n keys into a table is EXACTLY this same math, with "days" replaced by "hash-table slots."

Exact method: probability that k people all have DIFFERENT birthdays (out of n equally likely days), then take the complement:

The exact product and the 50% crossover search, as code:

Using 1+x ≤ e^x, we can bound B_k ≤ e^-k(k-1)/2n, and solving Pr{match} ≥ 1/2 gives k(k-1) ≥ 2n ln 2, i.e. k ≈ 1.18√n — 23 for Earth's 365-day year (checked exactly in verify/c05.dart), 31 for a hypothetical 669-"sol" Mars year.

The exponential bound and the indicator-variable estimate, as code:

Input size → what’s feasible. the incremental search needs about 1.18√n steps: n = 365 → 23 steps, n = 10¹² → about 1.2·10⁶ steps (still instant). Recomputing the product from scratch for every k would be quadratic in that, about 10¹² steps.

Approximate method via indicator variables (faster to derive, though slightly looser): let X_ij = 1 if people i and j share a birthday. E[X_ij] = 1/n. There are C(k,2) pairs, so by linearity, E[matching pairs] = C(k,2)/n. Setting this ≥ 1 gives k ≥ √(2n) + 1 ≈ 28 for n=365 — same Θ(√n) order of growth as the exact method, obtained without any product-of-fractions algebra at all.

Try your own "year length" (any positive number of equally likely days/slots) and watch the crossover point:

Birthday paradox: crossover happens at Θ(√n) people, not Θ(n) — this is precisely why hash tables start seeing collisions long before they're "full," and why a cryptographic hash needs an output about TWICE as many bits as the collision resistance you want (the "birthday attack": a b-bit hash is collision-searchable in about 2^b/2 tries).

8. Balls, bins & the coupon collector

Throwing n balls independently and uniformly at random into b bins is the exact same math as birthdays (bins = days) — and it's also exactly what happens when you hash n keys into a b-slot hash table. A related, harder question: if a cereal box gives you ONE random coupon (out of n distinct kinds) per box, how many boxes must you buy, on average, before you've collected EVERY kind at least once? This is the coupon collector's problem.

Split the process into stages: stage i starts right after your i-th distinct coupon and ends when you draw your (i+1)-th NEW one. While you already have i of the n kinds, each new box is "useful" with probability (n-i)/n — a geometric distribution, expectation n/(n-i). Summing all n stages:

Stage by stage, as code, and the simulation it predicts:

Input size → what’s feasible. the formula is O(n); a simulation costs about n·H_n tosses per trial, so n = 10⁵ bins is about 1.2·10⁶ tosses per trial.

Watch the simulation fill bins one at a time and compare the running total against the b·H_b prediction:

Two related quantities, both provable the exact same "define an indicator per bin" way: expected number of EMPTY bins after throwing n balls into n bins is ≈ n/e, and so is the expected number of bins with EXACTLY one ball — a nice, slightly counterintuitive fact (in the limit about 37% of bins are empty, 37% hold exactly one ball and the remaining 26% hold two or more).

The two “about n/e” facts, as code (exact expectations, with an exact check for 3 balls in 3 bins):

9. Streaks

Flip a fair coin n times. How long is the LONGEST unbroken run of heads you should expect to see? Most people badly underestimate this — with just 100 flips, a streak of 5+ heads in a row is common, not a sign anything is "rigged."

The two-sided argument: a union bound over all n possible starting positions shows a streak of length 2⌈lg n&rceil is unlikely to occur anywhere (probability ≤ 1/n), giving the upper bound E[L] = O(lg n). A separate argument partitions the n flips into independent blocks and shows some block is all-heads with decent probability, giving the matching lower bound E[L] = Ω(lg n). Together: E[L] = Θ(lg n).

The longest-run scan, and the exact tail probability that the Θ(lg n) argument bounds:

Input size → what’s feasible. the scan is O(n) time, O(1) space (n = 10⁷ flips is instant); the exact DP costs O(n·s) with s about 2 lg n, so n = 10⁵ is about 3.4·10⁶ steps.

A useful sharper tail bound from the same argument: Pr{streak ≥ r⌈lg n⌉} ≤ 1/n^r-1. For n = 1000: Pr{streak ≥ 20} ≤ 1/1000, and Pr{streak ≥ 30} ≤ 1/1,000,000 — the probability of an unusually long streak collapses exponentially fast as you ask for a slightly longer one, which is exactly the flavor of argument behind Chernoff-style tail bounds (M02 §16).

Longest head-streak in n fair coin flips is Θ(lg n) in expectation — the SAME asymptotic order as a balanced binary search tree's height, and for the same underlying reason: you're asking "how many times can a 50/50 event repeat before running out of room," and doubling n only adds one more expected repeat.

10. The on-line hiring problem (secretary problem)

A harder, more realistic variant of Section 1: you must accept or reject EACH candidate immediately, on the spot, with no going back — you can't "wait and see the rest, then pick your favorite." You get exactly one irrevocable shot. This is the famous secretary problem.

Strategy: interview (and reject, no matter how good) the first k candidates purely to learn what "good" looks like. After that, hire the very FIRST subsequent candidate who beats every one of those first k — if none ever does, you're stuck hiring whoever comes last.

The probability of success (hiring the single overall-best candidate) works out to:

The exact success probability and the lower bound, as code:

Where the formula comes from. Number the candidates 0..n−1 and let S_i be the event "we succeed AND the best candidate sits at index i". It needs two things: B_i, the best candidate really is at index i (probability 1/n), and O_i, nobody at indices k..i−1 was hired, which happens exactly when the best of the first i candidates (indices 0..i−1) is among the first k (probability k/i). The two events are independent, so Pr{S_i} = k/(n·i) for i ≥ k and 0 for i < k. Adding the disjoint events: Pr{S} = (k/n)·Σ_i=k..n−1 1/i, and bounding the sum by integrals gives (k/n)(ln n − ln k) ≤ Pr{S} ≤ (k/n)(ln(n−1) − ln(k−1)).

Maximizing the lower bound with calculus (set the derivative to zero) gives the striking result: choosing k = n/e succeeds with probability at least 1/e ≈ 36.8% — regardless of how large n is! Reject roughly the first 37% of candidates purely to calibrate, then take the next record-breaker.

Scanning every threshold finds the optimum (n = 100 gives k = 37, n/e = 36.8):

Compare the two useless extremes — reject nobody first (k=0, you'll almost always hire someone mediocre early and never look back) versus reject everyone except the last (k=n-1, you're gambling everything on the very last candidate being the best):

Try your own n and k and estimate the success rate over many random arrival orders (compared against the exact optimum k ≈ n/e):

Dart implementation. The two pseudocode loops, 0..k-1 (look only) then k..n-1 (hire the first record-breaker), are the Dart loops unchanged. The threshold k keeps the same meaning ("look at exactly the first k"):

Input size → what’s feasible. one pass, O(n) time, O(1) space, any n up to 10⁷; the success formula is O(n) per k, so scanning all thresholds is O(n²) — fine to n ≈ 10⁴, but just use k = round(n/e) beyond that.

Secretary problem optimal threshold: k = n/e ≈ 0.368n, giving success probability ≥ 1/e for every n — a rare case where one simple, memorable constant (1/e) is what this strategy guarantees for every n when candidates arrive in uniformly random order (the same assumption as Section 3; the lower bound is derived above, and it is a known result that for large n no strategy can beat about 1/e here).

Quiz

Interview questions

Cheat sheet

Topic	Key result	Notes
hireAssistant worst case	Θ(n) hires	candidates arrive in strictly increasing quality order
hireAssistant, random order	E[hires] = H_n = Θ(ln n)	probabilistic analysis — ASSUMES random input order
randomizedHireAssistant	E[hires] = O(ln n), ANY input	randomized algorithm — no assumption needed, algorithm shuffles itself
Indicator variable	E[X_A] = Pr{A}	turns "expected count" into "sum of probabilities" via linearity
permuteBySorting	Θ(n lg n) time, Θ(n) space, uniform	priority range n³ makes collisions ~O(1/n) likely
randomizeInPlace / Fisher–Yates	Θ(n) time, O(1) space, EXACTLY uniform	swap i with random j ∈ [i, n-1] — shrinking range is the whole trick
Naive whole-range shuffle	biased (n=3: 4/27 vs 5/27)	swapping from [0,n-1] every time — the classic interview bug
Birthday paradox	k ≈ 1.18√n for 50% collision	23 people / 365 days; same math as hash-table collisions
Coupon collector	E[draws] = n·H_n	collecting all n distinct kinds, balls-and-bins framing
Longest head-streak, n flips	E[L] = Θ(lg n)	union bound (upper) + block partition (lower)
On-line hiring / secretary problem	k = n/e ⇒ success ≥ 1/e	reject first ~37%, then hire the next record