The Longest Streak

Question

Flip a fair coin 100 times. What is the expected length of the longest run of consecutive heads? Give the number to two decimals (it's computable exactly) and a mental-math route that gets close.

Accepted Answer

Exact. Let q_m = P(textno head-run of length ge m), computed by a DP whose state is (flips so far, current trailing streak, capped at m - 1). Then mathbbE[L] = sum_m ge 1left(1 - q_mright) = 5.99 quad (n = 100), with standard deviation approx 1.8. Calibration on a small case: for n = 4, direct enumeration of the 16 sequences gives frac2716 = 1.6875, matching the DP. Mental route. A run of ge m heads "starts" at a given flip with probability 2^-(m+1) (a tail, then m heads), so about n cdot 2^-(m+1) such runs are expected; the longest run sits where this count crosses 1, i.e. m approx log_2 n - 1 approx 5.6. The sharpened asymptotic is mathbbE[L_n] approx log_2 n - frac23 approx 6.64 - 0.67 = 5.98, essentially exact. Growth is logarithmic, 1,000 flips only push the answer to about 9.3, while the distribution stays tight, with sigma approx 1.8 roughly independent of n (Gumbel-type fluctuations). Long streaks are simultaneously inevitable and predictable. Trading relevance, the streak fallacy, quantified. "We won seven days in a row" sounds extraordinary; the baseline says a fair coin produces a 6-run in 100 trials in expectation, and P(L ge 7) approx 0.32, roughly one fair sequence in

The Longest Streak

Problem

Your answer

Hints

More Expected Value to train on