The Interview Book · Careers

11Probability II

“You roll a die until two sixes in a row appear. How many rolls on average?” The candidate who writes two states on the whiteboard (no six yet; one six) and one equation for each has the answer, 42, in two minutes; the one who starts summing over sequences is still at it when the interviewer moves on. The second probability chapter is about expectations and processes, and nearly every question in it yields to one of four ideas: linearity with indicators, equations on states, martingales and stopping, and a little geometry of the uniform and exponential laws.

11.1 Expectation by indicators

Definition 11.1 (Indicator decomposition)

The indicator decomposition of a count $N$ writes it as a sum of indicators, $N = \sum_i \mathbf 1_{A_i}$ , so that $\E[N] = \sum_i \P(A_i)$ by linearity, whether or not the events $A_i$ are independent.

The method’s power is that dependence does not matter for the mean. It matters for the variance, which needs the pairwise probabilities $\P(A_i \cap A_j)$ .

Example 11.2 (Fixed points, runs, records)

A random permutation of $n$ items has on average one fixed point: item $i$ is in place with probability $1/n$ , and there are $n$ items. A sequence of $n$ fair coin tosses has on average $1 + (n-1)/2$ runs: a new run starts at toss $i \ge 2$ with probability $\tfrac12$ . A sequence of $n$ independent draws from a continuous law has on average $H_n = 1 + \tfrac12 + \dots + \tfrac1n$ records, since draw $i$ is the largest so far with probability $1/i$ ; for ten draws, about 2.93.

Example 11.3 (Distinct values)

$n$ draws from $N$ equally likely values show on average $N\big(1 - (1 - 1/N)^n\big)$ distinct values: value $v$ is missed by all draws with probability $(1-1/N)^n$ . The same indicator gives the expected number of empty buckets in a hash table.

11.2 Recursions on states

A waiting time for a pattern, a first passage in a chain, or the value of a game with a few positions is found by first-step analysis (One Quant Book 4, chapter 8): condition on the first step, write one linear equation per state, and solve.

Method 11.4 (Setting up first-step equations)

Choose states that remember exactly what the future needs: for a pattern, the longest suffix of what has been seen that is a prefix of the pattern.
For each state, write $e_s = 1 + \sum_t P_{st}\, e_t$ (expected steps) or $h_s = \sum_t P_{st}\, h_t$ (a probability of absorption), with the absorbing states’ values fixed.
Solve, and check a limiting case.

Example 11.5 (Two sixes in a row)

With $e_0$ the expected further rolls with no six pending and $e_1$ with one: $e_0 = 1 + \tfrac16 e_1 + \tfrac56 e_0$ and $e_1 = 1 + \tfrac56 e_0$ , so $e_0 = 42$ (Figure 11.1). For coins the same method gives 6 tosses for HH and 4 for HT: patterns that overlap themselves take longer to appear.

Figure 11.1. The two-state chain for “two sixes in a row”. Each arrow is one roll; the expected number of rolls from “no six” to “done” is 42. Exact solution by sympy in iv_prob2.py.

Races between patterns are solved the same way, with two absorbing states. Penney’s game (1969) is the classic case: for three-toss coin patterns, some patterns beat others with probability two thirds or more, and the relation is not transitive.

11.3 Martingales and stopping

A fair game is a martingale (One Quant Book 4, chapter 1), and the optional stopping theorem says that a bounded stopping rule cannot change its expected value. Interview questions use it in two ways: to compute a probability in one line, and to spot a false claim that a stopping rule creates an edge.

Proposition 11.6 (Gambler’s ruin)

A walk moves $+1$ with probability $p$ and $-1$ with probability $q = 1 - p$ , starting at 0. The chance of reaching $+b$ before $-a$ is $a/(a+b)$ if $p = \tfrac12$ , and $\big(1 - (q/p)^a\big)/\big(1 - (q/p)^{a+b}\big)$ otherwise. For $p = \tfrac12$ the expected duration from $x$ between 0 and $n$ is $x(n - x)$ .

Proof. For $p = \tfrac12$ the position is a martingale; for $p \neq \tfrac12$ the process $(q/p)^{S_t}$ is; optional stopping at the exit time (bounded in expectation) gives the probabilities. For the duration, $S_t^2 - t$ is a martingale when $p = \tfrac12$ . ∎

Proposition 11.7 (Wald’s identity)

If $X_1, X_2, \dots$ are i.i.d. with finite mean and $N$ is a stopping time with $\E[N] < \infty$ (or a count independent of the $X_i$ ), then $\E\big[\sum_{i \le N} X_i\big] = \E[N]\,\E[X_1]$ . If $N$ is independent of the $X_i$ , the variance of the sum is $\E[N]\Var(X_1) + \Var(N)\E[X_1]^2$ .

A small edge compounds strongly in a ruin problem: with $p = 0.51$ and symmetric targets of ten units, the chance of winning is about 0.60, not 0.51 (Interview question 11.7).

11.4 Continuous problems and coupling

Two facts about uniform and exponential variables answer most continuous questions. $n$ independent uniform points on $[0,1]$ cut it into $n+1$ spacings that are exchangeable, each with mean $1/(n+1)$ , so the $k$ -th smallest has mean $k/(n+1)$ . Independent exponential clocks of rates $\lambda_1, \dots, \lambda_k$ ring first at an exponential time of rate $\sum \lambda_i$ , and clock $i$ rings first with probability $\lambda_i/\sum_j \lambda_j$ , independently of when.

Example 11.8 (The inspection paradox)

Five trades arrive at uniform times in an hour. The average gap between consecutive events (the ends of the hour included) is 10 minutes, but the gap that contains a moment chosen at random has expected length $2/7$ of an hour, about 17 minutes: longer gaps are more likely to be the ones you land in. Wait-time statistics measured from random moments overstate the typical gap.

Definition 11.9 (Coupling argument)

A coupling argument compares two random quantities by constructing them on one probability space, each with its correct law, so that an inequality between them holds outcome by outcome; the inequality then holds for their probabilities or expectations.

Example 11.10 (A better coin wins more often)

Draw $U_1, \dots, U_{10}$ uniform on $[0,1]$ and let toss $i$ be a success for coin $p$ if $U_i < p$ . With $p = 0.6$ and $p' = 0.5$ every success of the second coin is a success of the first, so “at least seven successes” for the second implies it for the first, and $\P(\ge 7 \mid 0.6) \ge \P(\ge 7 \mid 0.5)$ without computing either (they are 0.382 and 0.172). The same construction proves that the ruin probability of Proposition 11.6 falls as $p$ rises.

11.5 Worked answers

Example 11.11 (Adjacent pairs by indicators)

“Five buy and five sell orders are arranged in a uniformly random sequence. How many adjacent pairs have the same side, on average?” There are nine adjacent pairs. For any one of them, the chance that both positions hold the same side is $(5 \times 4 + 5 \times 4)/(10 \times 9) = 4/9$ , so by linearity the expected count is $9 \times 4/9 = 4$ . The pairs are not independent (a long run creates several same-side pairs at once) and the argument does not need them to be. Check: with one buy and one sell the formula gives $1 \times 0 = 0$ , and indeed the single pair always differs.

Example 11.12 (A recursion with a pattern)

“You roll a die and add the results until the total is at least 3. How many rolls, on average?” Let $e_k$ be the expected number of rolls needed to reach at least $k$ from zero, with $e_k = 0$ for $k \le 0$ . The first roll moves you by $j$ with probability $1/6$ : $e_k = 1 + \tfrac16\sum_{j=1}^6 e_{k-j}$ . Then $e_1 = 1$ , $e_2 = 1 + \tfrac16 = 7/6$ , and $e_3 = 1 + \tfrac16(7/6 + 1) = 49/36 \approx 1.36$ . A pattern appears, $e_k = (7/6)^{k-1}$ , and the candidate should say how far it goes: subtracting consecutive equations gives $e_k - e_{k-1} = (e_{k-1} - e_{k-7})/6$ , and $e_{k-7} = 0$ while $k \le 7$ , so the pattern holds up to $e_7 = (7/6)^6 \approx 2.52$ and breaks at $k = 8$ . For large $k$ the recursion settles at $e_k \approx k/3.5 + 10/21$ : one roll per 3.5 of total, the mean roll, plus a constant for the overshoot. Saying where a pattern must break is worth as much as finding it.

11.6 Question bank

Interview question 11.1 ★ trader, researcher • market maker

Twenty orders are put into a queue in a uniformly random order. On average, how many end up in their original position?

Solution

Solution of Interview question 11.1.

One. Order $i$ is in its original place with probability $\tfrac1{20}$ , and there are twenty orders; linearity does not care that the events are dependent. (The count is approximately Poisson with mean 1.)

What the interviewer is looking for: indicators and linearity, without enumerating permutations.

Interview question 11.2 ★ trader • market maker

How many rolls of a die on average until the first six? Until the second six (not necessarily consecutive)?

Solution

Solution of Interview question 11.2.

The first six takes a geometric number of rolls with mean 6. The second six needs another independent geometric wait, so 12 in all.

What the interviewer is looking for: the geometric mean and additivity of independent waits.

Interview question 11.3 ★ researcher, developer • any

A fair coin is tossed ten times. What is the expected number of runs (maximal blocks of equal faces)?

Solution

Solution of Interview question 11.3.

A run starts at toss 1 and at each toss $i \ge 2$ that differs from toss $i-1$ , which happens with probability $\tfrac12$ : $1 + 9 \times \tfrac12 = 5.5$ . Enumerating all 1 024 sequences gives the same.

What the interviewer is looking for: counting run starts with indicators.

Interview question 11.4 ★ trader, researcher • any

Two independent uniform numbers on $[0,1]$ : what are the expected values of the smaller and the larger?

Solution

Solution of Interview question 11.4.

The two points cut $[0,1]$ into three exchangeable pieces of mean $\tfrac13$ , so the smaller has mean $\tfrac13$ and the larger $\tfrac23$ .

What the interviewer is looking for: the spacings symmetry rather than an integral (which gives the same).

Interview question 11.5 ★ trader, developer • proprietary firm

Fills arrive at venue A as a Poisson process of rate 3 a minute and at venue B at rate 1 a minute, independently. What is the chance the next fill comes from A, and how long do you wait for it on average?

Solution

Solution of Interview question 11.5.

The first of two exponential clocks rings with probability proportional to its rate: $3/(3+1) = \tfrac34$ for A. The waiting time is exponential with rate 4 a minute: 15 seconds on average.

What the interviewer is looking for: the competing-exponentials rule and the rate of the minimum.

Interview question 11.6 ★★ trader • market maker

You roll a die until two consecutive rolls show the same face, whatever it is. How many rolls on average? Why is it so different from 42?

Solution

Solution of Interview question 11.6.

After the first roll, each roll matches the previous one with probability $\tfrac16$ , whatever it was, so the wait is $1 + 6 = 7$ . For two sixes in a row, each attempt needs the previous roll to be a six as well, which happens only a sixth of the time, and a failure on the second roll of an attempt sends you back to the start: the states carry more memory, and the wait is $6 + 36 = 42$ .

What the interviewer is looking for: recognising the one-state structure, and explaining the difference with the two-state chain.

Interview question 11.7 ★★ trader, risk • proprietary firm

Each bet wins one unit with probability 0.51 and loses one unit otherwise. You stop when you are ten units up or ten units down. What is the chance you stop up?

Solution

Solution of Interview question 11.7.

With $r = q/p = 49/51$ and $a = b = 10$ : $\big(1 - r^{10}\big)/\big(1 - r^{20}\big) = 1/(1 + r^{10}) \approx 1/(1 + 0.670) \approx 0.599$ . A one-point edge per bet becomes a ten-point edge over the game, because the game lasts about a hundred bets.

What the interviewer is looking for: the ruin formula with drift, and an intuition for why small edges compound.

Interview question 11.8 ★★ researcher, trader • any

A symmetric random walk starts at 3 and stops at 0 or 10. How many steps does it take on average?

Solution

Solution of Interview question 11.8.

$S_t^2 - t$ is a martingale; optional stopping at the exit gives $\E[\tau] = \E[S_\tau^2] - 9 = 100 \times \tfrac3{10} - 9 = 21$ , which is $x(n - x) = 3 \times 7$ . A simulation of 20 000 walks agrees.

What the interviewer is looking for: the quadratic martingale, or the first-step recursion, and the product formula.

Interview question 11.9 ★★ risk, trader • bank

A desk makes a Poisson number of trades a day with mean 40, independent of their P&L, each with mean 0.3 and variance 4 (thousands). Give the day’s expected P&L and its standard deviation.

Solution

Solution of Interview question 11.9.

Mean $40 \times 0.3 = 12$ . Variance $\E[N]\Var(X) + \Var(N)\E[X]^2 = 40 \times 4 + 40 \times 0.09 = 163.6$ (for a Poisson count $\Var(N) = \E[N]$ ), so a standard deviation of about 12.8 thousand. The day’s Sharpe ratio is about 0.94.

What the interviewer is looking for: Wald’s identity and the compound variance, with the Poisson simplification.

Interview question 11.10 ★★ developer, researcher • any

Twenty keys are hashed uniformly into 365 buckets. How many distinct buckets are used on average?

Solution

Solution of Interview question 11.10.

$365\big(1 - (364/365)^{20}\big) \approx 19.49$ : on average about half a collision among twenty keys, consistent with the birthday problem.

What the interviewer is looking for: indicators for each bucket being used.

Interview question 11.11 ★★★ trader, researcher • market maker

A fair coin is tossed until either HHT or HTH appears. Which is more likely to appear first, and with what probability? Which has the shorter expected waiting time on its own? Explain why the two answers point in different directions.

Solution

Solution of Interview question 11.11.

HHT comes first with probability $\tfrac23$ : once HH has appeared, HHT is certain before HTH (every T completes HHT), whereas an HT can be spoiled by a second T. On its own, HHT takes 8 tosses on average and HTH takes 10, since HTH overlaps itself (its final H starts a new attempt). Here both answers favour HHT; in general the race and the waiting time can disagree (THH beats HHT three times in four, with equal waits of 8), which is the lesson of Penney’s game: the waiting time is a property of one pattern, the race a property of the pair.

What the interviewer is looking for: first-step analysis for the race, the overlap argument for the waits, and not confusing the two.

Interview question 11.12 ★★★ trader, researcher • proprietary firm

You will receive five offers, one at a time, each an independent uniform number on $[0,1]$ . You must accept or reject each on the spot and you accept exactly one. What rule maximises the expected value accepted, and what is that value? What is the threshold for the first offer?

Solution

Solution of Interview question 11.12.

Backward induction: with one offer left its value is $V_1 = \tfrac12$ ; with $k$ left, accept an offer above $V_{k-1}$ , so $V_k = \E[\max(U, V_{k-1})] = (1 + V_{k-1}^2)/2$ . $V_2 = 0.625$ , $V_3 \approx 0.695$ , $V_4 \approx 0.742$ , $V_5 \approx 0.775$ . Accept the first offer if it exceeds 0.742, the second if above 0.695, the third if above 0.625, the fourth if above 0.5, and take the fifth.

What the interviewer is looking for: backward induction on continuation values with decreasing thresholds.

Interview question 11.13 ★★★ researcher, developer • systematic fund

Five orders arrive at independent uniform times in an hour. What is the expected arrival time of the second? A monitor checks at a uniformly random moment and measures the gap between the order before and the order after (or the hour’s ends). What is the expected length of the gap it sees, and why does it differ from the average gap?

Solution

Solution of Interview question 11.13.

The second arrival has mean $2/6$ of an hour, 20 minutes. The six gaps average 10 minutes, but the gap covering a random moment has expected length $\sum \E[S_i^2] = 6 \times \tfrac{2}{6 \times 7} = \tfrac27$ of an hour, about 17 minutes: a gap is sampled with probability proportional to its length. Monitoring that measures gaps from random moments overstates the typical gap by this length bias. A simulation of 200 000 hours gives 0.286.

What the interviewer is looking for: order-statistic means, and the length-biased sampling behind the inspection paradox.

Interview question 11.14 ★★★ researcher, risk • systematic fund

Prove without computing either probability that ten tosses of a coin with $p = 0.6$ give at least seven heads more often than ten tosses of a fair coin. Then compute both.

Solution

Solution of Interview question 11.14.

Couple the coins: use the same uniform $U_i$ for toss $i$ of both, with heads when $U_i < p$ . Every head of the fair coin ( $U_i < 0.5$ ) is a head of the biased coin ( $U_i < 0.6$ ), so on every outcome the biased coin has at least as many heads, and the event “at least seven” is at least as likely for it. The values are 0.382 and $176/1\,024 \approx 0.172$ .

What the interviewer is looking for: constructing a monotone coupling, then confirming by the binomial sums.

Sources and further reading

W. Penney, Journal of Recreational Mathematics, October 1969, 241 (Penney’s game).
A. Wald, “On cumulative sums of random variables”, Annals of Mathematical Statistics 15(3), 1944, 283–296.
T. Lindvall, Lectures on the Coupling Method, Wiley, 1992.
One Quant Book 4, chapters 1, 6 and 8 (martingales; Poisson processes; Markov chains and first-step analysis).

Terms defined in this chapter

See all 2333 terms in the glossary