Markov Chains and Expected Hitting Times

3 min read

You've already used Markov chains in this course — the flips-until-HH and ant-on-a-cube questions are Markov chains solved by hand. This lesson makes the machinery explicit, so any question with "states and transitions" becomes routine.

The setup

A Markov chain is a random process whose next state depends only on the current state — not the path taken to reach it:

$P(X_{t+1} = j \mid X_t = i, \text{history}) = P_{ij}$

The matrix $P$ (rows summing to 1) is the whole model. The memoryless property is the modeling choice: weather regimes, credit ratings, market volatility states, board-game positions — all standard chains.

First-step analysis: the universal solvent

Expected time to reach a target state? Condition on the first step:

$E_i = 1 + \sum_j P_{ij} E_j, \qquad E_{\text{target}} = 0$

One linear equation per state; solve the system. This is exactly what we did for HH (states: fresh, "one H") and the cube (states: distance 3/2/1/0). The general recipe:

Define states that capture all relevant memory (for pattern-matching questions: current progress toward the pattern).
Collapse symmetric states (8 cube corners → 4 distances) — the step that turns tedious into elegant.
Write first-step equations; solve.

The same template computes probabilities instead of times: $h_i = \sum_j P_{ij} h_j$ with boundary values 1 at the good absorbing state, 0 at the bad — gambler's ruin is this with two absorbing barriers.

Stationary distributions: where the chain settles

A distribution $\pi$ is stationary if $\pi P = \pi$ — running the chain one more step changes nothing. For well-behaved (irreducible, aperiodic) chains, the chain converges to $\pi$ from any start, and long-run time-in-state fractions equal $\pi$ .

Worked micro-example: weather is Sunny or Rainy; $P(S \to R) = 0.2$ , $P(R \to S) = 0.6$ . Balance: $\pi_S \cdot 0.2 = \pi_R \cdot 0.6$ (flow S→R equals flow R→S), so $\pi_S = 3\pi_R$ , giving $\pi = (0.75, 0.25)$ . The balance-of-flows shortcut solves most two- and three-state interview chains in seconds.

Two facts worth quoting: expected return time to state $i$ is $1/\pi_i$ (visit a state 25% of the time → return every 4 steps on average); and PageRank — the algorithm that built Google — is literally the stationary distribution of a random web surfer, the standard example that the idea scales.

Where chains meet markets

Regime models: volatility as a two-state chain (calm/stressed) reproduces clustering that iid models can't; the stationary distribution gives long-run time in each regime, hitting times give expected crisis frequency.
Credit migrations: rating agencies publish literal transition matrices; default is an absorbing state, and "expected time to default" is first-step analysis on it.
Order-book states, trend/chop classifiers, Markov-switching models — the vocabulary is everywhere in quant research.

The interview version

"A mouse is in corner room of a 2×2 grid of rooms; each minute it moves to a random adjacent room. Expected time to reach the diagonal room?" — Two state classes by symmetry (start/diagonal-adjacent), first-step equations, answer in four lines. Any such question: name the states, exploit symmetry, condition on one step. If you can also say "and if they asked for the long-run fraction of time in each room, I'd use the stationary distribution — uniform here, by symmetry," you've shown the whole toolkit unprompted.