Markov chains & order statistics: interview questions and key results
Hitting times, stationary states, branching, order statistics. The results to know for quant trading interviews, then a worked example of each of the 5 question types. Free, no sign-up.
Hitting times: write Estate = 1 + Σ P(next)·Enext for each state and solve; group symmetric states first.
Stationary distribution: balance the flows (πA·P(A→B) = πB·P(B→A) for two states); return time = 1/π.
Branching: extinction q solves q = G(q), the offspring generating function; take the smallest root in [0, 1].
k-th smallest of n uniforms has mean k/(n + 1).
Worked examples (5)
Try each one before opening the solution. In the app, every type generates fresh numbers each time.
Hitting time on a cycle
A token sits on corner 0 of a regular 5-sided polygon. Each second it moves to one of the two neighbouring corners, chosen at random. What is the expected number of seconds until it first reaches corner 4?
Answer and worked solution
Answer: 4
Unroll the polygon: reaching corner 4 means the walk first hits +4 or −1 (the same corner, reached from either side). A fair walk started between barriers 4 and 1 away takes on average the product of the distances to exit: 4 × 1 = 4.
Runs (waiting for k in a row)
You roll a fair 4-sided die (faces 1 to 4) until you roll a 4 three times in a row. What is the expected number of rolls?
Answer and worked solution
Answer: 84
Track the current run of 4s as a Markov chain. Let Ej be the expected rolls still needed with a run of j: Ej = 1 + (1/4)Ej+1 + (3/4)E0, with E3 = 0. Solving gives E0 = 4 + 4² + 4³ = 84. (The fair-coin version, two heads in a row, is 2 + 4 = 6.)
Two-state stationary distribution
If today is sunny, tomorrow is rainy with probability 0.1; if today is rainy, tomorrow is sunny with probability 0.2. In the long run, what fraction of days are rainy?
Answer and worked solution
Answer: 1/3 ≈ 0.33333
In the stationary distribution, the flow from sunny to rainy equals the flow back: πS·0.1 = πR·0.2. With πS + πR = 1, πR = 0.1/(0.1 + 0.2) = 0.33333.
Order statistics of uniforms
You draw 5 independent numbers, each uniform on [0, 1]. What is the expected value of the 4th smallest?
Answer and worked solution
Answer: 2/3 ≈ 0.66667
The 5 points split [0, 1] into 6 gaps, and by symmetry every gap has the same expected length, 1/6. The 4th smallest sits after 4 gaps: 4/6 = 0.66667.
Branching-process extinction
Each organism, independently, either dies (probability 0.1) or splits into two (probability 0.9). Starting from one organism, what is the probability that its line eventually dies out?
Answer and worked solution
Answer: 1/9 ≈ 0.11111
Let q be the extinction probability. Condition on the first step: q = 0.1 + 0.9·q² (both offspring lines must die out). The roots are q = 1 and q = 0.1/0.9. The mean number of offspring is 1.8 > 1, so extinction isn't certain and q is the smaller root: 0.11111.