Markov chains: states, transitions and hitting times

PROB · Chapter 422 min readAsked at Jane Street, SIG, Citadel, Optiver

Assumes Random walks and gambler’s ruin.

After this lesson you should be able to

  • Choose a state that contains everything needed to predict the next step.
  • Read a transition diagram as a matrix and use its powers for multi-step probabilities.
  • Solve absorption probabilities and expected hitting times by first-step equations.
  • Explain why stationary probabilities differ from the chance of hitting a boundary.

A Markov chain is a way of turning a story into states and arrows. The arrows carry the one-step probabilities. Once the state is sufficient, questions about tomorrow, eventual victory and time to finish become different equations on the same diagram. The main interview skill is drawing the right diagram before calculating.

Definition 4.19

What counts as a state?

Markov state, Pij=Pr⁡(Xt+1=j∣Xt=i)P_{ij}=\Pr(X_{t+1}=j\mid X_t=i) — The present state must retain all information relevant to the next move. A dragon’s current head count is sufficient if each swing has the same rules. For a coin pattern such as HTH, the last flip alone is insufficient: you must remember how much of the target pattern is already matched.

State means the smallest useful memory. A state is not necessarily the last observation. In weather, today’s condition is enough. In a pattern game, today’s flip is not: the sequence HT and the sequence TT both end in T, but only HT can finish HTH on the next head. Good state design keeps that distinction and discards everything else.

80%20%50%50%ClearStorm
Figure 4.20 · A two-state chain you can read aloud. An arrow says what happens next, given where you are now. The two arrows leaving Clear total one, as do the arrows leaving Storm. Self-loops are genuine transitions: a day passes even when the weather does not change.

Equation 4.21

Turn arrows into a matrix

Rows are today’s state and columns are tomorrow’s, in the order Clear, Storm. Matrix multiplication sums over the possible intermediate states. Every row of a transition matrix sums to one.

P=(0.80.20.50.5),(P2)ij=∑kPikPkjP=\begin{pmatrix}0.8&0.2\\0.5&0.5\end{pmatrix},\qquad (P^2)_{ij}=\sum_k P_{ik}P_{kj}

Example 4.22

Two days: enumerate the routes

It is clear today. What is the chance it is clear in two days? Give the two routes that contribute.

Show the worked solutionHide the worked solution

Worked solution

  1. Formula
    Pr⁡(C2∣C0)=Pr⁡(C→C→C)+Pr⁡(C→S→C)\Pr(C_2\mid C_0)=\Pr(C\to C\to C)+\Pr(C\to S\to C)
  2. Substitute
    (0.8)(0.8)+(0.2)(0.5)(0.8)(0.8)+(0.2)(0.5)
  3. Solve
    0.64+0.10=0.740.64+0.10=0.74
  4. Answer
    0.740.74

Sanity check. The answer lies between 0.8, the immediate chance of staying clear, and the long-run clear share of about 0.714. Both routes matter.

The rest of this lesson is in Premium

You have read the opening. 10 more sections follow, including 2 worked examples and 2 quick checks.

Start the free 7-day trialSign in

Nothing is charged for 7 days, and you can cancel before then. Or read Arithmetic that survives a clock in full, free.