Markov Chains & Absorbing States

Hard4–5 hrsMarkov ChainAbsorptionStationary DistributionHitting Time

Overview

Markov chains are the Swiss Army knife of quant probability. They make any 'sequential process with states' tractable. The secret: instead of thinking about the full trajectory, you only need the CURRENT state — the future is independent of the past given the present. This memoryless property lets you write simple linear equations for expected hitting times and absorption probabilities.

How to Recognize

→'How long until the process reaches state X?'
→A system moves between discrete states based on probabilities
→Expected time to ruin, expected time to win, probability of reaching a goal

Step-by-Step Approach

1.Define the states clearly — what information do you need to carry?
2.Write E[steps from state i] = 1 + Σⱼ Pᵢⱼ·E[steps from state j] (absorbing states: 0)
3.Write P(reach goal from state i) = Σⱼ Pᵢⱼ·P(reach goal from state j)
4.Solve the resulting system of linear equations
5.Stationary distribution: solve πP = π (or by detailed balance for reversible chains)

Key Formulas

01Hitting time:

t_i = 1 + \sum_{j \notin A} P_{ij} t_j

(

A

= absorbing states)

02Absorption probability:

h_i = \sum_j P_{ij} h_j

with

h_{\text{absorb}}=1

03Stationary:

\pi = \pi P

\sum_i \pi_i = 1

04Detailed balance:

\pi_i P_{ij} = \pi_j P_{ji}

(reversible chains)

Worked Examples

0Quick Example

Expected flips to see HH: States S (start), H (one head), HH (done). E_S = 1 + ½E_H + ½E_S, E_H = 1 + ½·0 + ½E_S. Solve: E_S = 6.

Problem

Flip a fair coin repeatedly. What is the expected number of flips to first see two consecutive heads (HH)?

Solution

States: S₀ = start (or just saw tails), S₁ = just saw one head, S₂ = HH (absorbing, done).

From S₀: flip → H (prob ½, go to S₁) or T (prob ½, stay in S₀). Cost = 1 flip.

From S₁: flip → H (prob ½, go to S₂ = done!) or T (prob ½, go back to S₀). Cost = 1 flip.

Equations: E₀ = 1 + ½E₁ + ½E₀ → E₀/2 = 1 + ½E₁ → E₀ = 2 + E₁.

E₁ = 1 + ½·0 + ½E₀ = 1 + E₀/2. Substitute: E₀ = 2 + 1 + E₀/2 → E₀/2 = 3 → E₀ = 6.

Answer

$E[\text{flips to HH}] = 6$ . Key insight: after a tail, you reset completely. After a head, you only need one more. The asymmetry creates the 6-step result.

Common Mistakes

!
Forgetting to handle absorbing states correctly in the equations — they have value 0 in expected time equations and value 1 (or 0) in probability equations.
!
Setting up the wrong states. The state must capture everything relevant to the future — missing information makes the Markov property fail.
!
Solving the system incorrectly. For hitting time problems, always substitute back to verify your answer satisfies all equations.
!
Confusing hitting time (expected steps) with absorption probability. These require separate equation systems.

Practice Problems

Click "Show Answer" to reveal

Expected flips to see HTH (heads-tails-heads)? Set up the Markov chain states.

Hint: States: (empty), (H), (HT), (HTH=done). The tricky part: after failing, what state do you return to?

A frog starts on lily pad 3 on a row of 5 lily pads (1,2,3,4,5). It jumps left or right uniformly. Pads 1 and 5 are exits. What is P(exit at pad 5)?

Hint: Fair random walk: P(reach 5 | start 3) = ?

A lazy professor grades by randomly marking each question pass (P=0.7) or fail (P=0.3), independently. There are 10 questions. What is the stationary distribution not relevant here — but what is P(at least 7 pass)?

Hint: Each question is independent Bernoulli(0.7). Use binomial.

Back to Study Plan

Inclusion-Exclusion Direct EV Calculation