Guides / Probability

Markov chains: multiply row vectors by P, solve πP = π, and get absorption from (I − Q)⁻¹

A Markov chain moves between states at random, and where it goes next depends only on where it is now. Everything about it is stored in one matrix P of transition probabilities, and the standard questions are matrix computations: the distribution a few steps from now, the long-run share of time in each state, how quickly the chain forgets where it started, and how long until it is absorbed. Most wrong answers come from multiplying on the wrong side of P, or from using the right formula for a different question.

Why it works

If the chain is in state i with probability π_i today, then the chance of being in j tomorrow is the total over every i of π_iP_ij: being in i, then moving to j. That sum is the j-th entry of the row vector πP, so one step is one multiplication from the left, and n steps are π₀Pⁿ. A stationary distribution is one that this multiplication leaves alone, which makes it a left eigenvector of P for the eigenvalue 1. Writing P in terms of its eigenvalues, the part of π_n that is not π is multiplied by λ₂, λ₃, … at every step, so the slowest of them, the second-largest in size, sets how fast the chain forgets its start.

For absorbing chains, (Qⁿ)_ij is the chance of being in transient state j after n steps from i. Adding over all n counts the expected visits to j, and the geometric series I + Q + Q² + … adds up to (I − Q)⁻¹, just as 1 + q + q² + … = 1/(1 − q). Each visit to a transient state is one step, so the total of row i of N is the expected number of steps before absorption. Multiplying by R adds up, over the last transient state visited, the chance of then jumping to each absorbing state.

Example 1: the distribution after two steps

A machine is either working (W) or broken (B) at the start of each day. A working machine is still working the next day with probability 0.8; a broken one is repaired by the next day with probability 0.6. It is working today. Find the probability that it is working two days from now.

1. P = 0.80.20.60.4States in the order W, B. Row i is tomorrow's distribution given today is i, so each row sums to 1.
2. π₀ = (1, 0)Certain to be working: a row vector.
3. π₁ = π₀P = (0.8, 0.2)A one-hot row vector times P picks out a row of P.
4. π₂ = π₁PThis mixes the rows of P with weights π₁: 0.8 (0.8, 0.2) + 0.2 (0.6, 0.4).
5. π₂ = (0.76, 0.24)It is working two days from now with probability 0.76. The entries add to 1, as every distribution must. The same number is the (W, W) entry of P².

Example 2: the stationary distribution of a three-state chain

A shared bike moves between stations A, B and C each hour with

P = 0.80.200.10.70.20.200.8.

Find the long-run share of hours it spends at each station, and the mean time between visits to A.

1. π_B = 0.2π_A + 0.7π_BπP = π, read down column B: the bike reaches B from A or by staying at B.
2. π_C = 0.2π_B + 0.8π_CColumn C. The equation for column A is then automatic: one of the K equations is always redundant.
3. π_B = (2/3)π_A, π_C = π_BFrom 0.3π_B = 0.2π_A and 0.2π_C = 0.2π_B.
4. π_A(1 + 2/3 + 2/3) = 1The entries must add to 1; this replaces the redundant equation.
5. π = (3/7, 2/7, 2/7)The bike is at A about 43% of the time, and visits to A are 1/π_A = 7/3 hours apart on average. Check column A: 0.8 · 3/7 + 0.1 · 2/7 + 0.2 · 2/7 = 3/7.

Example 3: how fast the chain forgets where it started

For the machine of Example 1, find the long-run probability that it is working, and how far the distribution after n days is from it, starting from a working machine.

1. 0.2π_W = 0.6π_BWith two states, the flow from W to B must balance the flow back.
2. π = (0.75, 0.25)π_W = 3π_B and the two add to 1.
3. λ₁ = 1, λ₂ = 1.2 − 1 = 0.2Every row sums to 1, so 1 is an eigenvalue; the eigenvalues add to the trace, 0.8 + 0.4 = 1.2.
4. gap_n = 0.25 · 0.2ⁿThe gap is Pr(W after n days) − 0.75. It starts at 1 − 0.75, and each day multiplies it by λ₂.
5. gaps 0.25, 0.05, 0.01, 0.002After two days the gap is 0.76 − 0.75 = 0.01, matching Example 1. A second eigenvalue near 1 in size would mean a chain that takes a long time to mix.

Example 4: absorption with the fundamental matrix

A two-year program has states Year 1 and Year 2, and ends in Graduated or Dropped out. Each year a Year 1 student repeats with probability 0.1, moves up with 0.8 and drops out with 0.1. A Year 2 student repeats with 0.1, graduates with 0.8 and drops out with 0.1. For a new student, find the expected number of years enrolled and the probability of graduating.

1. Q = 0.10.800.1Rows and columns are Year 1, Year 2: the moves between the transient states.
2. R = 00.10.80.1The columns are Graduated, Dropped out. Each row of Q and R together sums to 1.
3. I − Q = 0.9−0.800.9Subtract from the identity entry by entry.
4. N = 10/980/81010/9A triangular 2 × 2: the diagonal entries invert to 1/0.9, and the corner is 0.8/0.81. Check that (I − Q)N = I.
5. N₁₁ + N₁₂ = 170/81 ≈ 2.10Expected years in Year 1 plus expected years in Year 2: 10/9 + 80/81.
6. N₁₂ · 0.8 = 64/81 ≈ 0.790The probability of graduating, the first entry of NR: only Year 2 leads to graduation. Check: a student eventually leaves Year 1 upward with probability 0.8/0.9 = 8/9, and then leaves Year 2 by graduating with probability 8/9 again.

Common mistakes, and the exact line they happen on

1. Multiplying P by a column vector

Tomorrow's distribution in Example 1.

1. π₀ = (1, 0)Right so far.
2. P (1, 0)^T = (0.8, 0.6)^TThis is the mistake. The entries add to 1.4, so this is not a distribution. It is the first column of P: the chance of working tomorrow from each state today. With rows indexed by today, the distribution multiplies from the left, π₀P = (0.8, 0.2).

2. Reading π off the right eigenvector

The stationary distribution in Example 2, found with software.

1. P has the eigenvalue 1Right so far: every matrix whose rows sum to 1 does.
2. π = (1/3, 1/3, 1/3)This is the mistake. This normalizes the solution of Pv = v, which is the all-ones vector (1, 1, 1) for every chain. The stationary distribution solves πP = π, an eigenvector of P^T. Check: (1/3, 1/3, 1/3)P = (11/30, 3/10, 1/3), not uniform. The right answer is (3/7, 2/7, 2/7).

3. Using the return time as the time to get there

The machine of Example 1, starting from a working day: how long until it first breaks?

1. π_B = 0.25Right so far: Example 3.
2. h_W→B = 1/π_B = 4 daysThis is the mistake. The mean time h_W→B from W to the first breakdown is not 1/π_B, which is the mean time from B back to B. From W, each day breaks the machine with probability 0.2, so the wait is 1/0.2 = 5 days. The return time averages a quick repeat with that wait: 1 + 0.6 · 5 = 4.

Practice

1. Find the stationary distribution of P = 0.70.30.40.6.

   Show answer

   0.3π₁ = 0.4π₂, so π = (4/7, 3/7).

2. For the same chain, find the probability of being in state 2 two steps after state 1, and the second eigenvalue.

   Show answer

   0.7 · 0.3 + 0.3 · 0.6 = 0.39, and λ₂ = 1.3 − 1 = 0.3.

3. For the same chain, what is the mean time between visits to state 1?

   Show answer

   1/π₁ = 7/4 steps.

4. A walker on 0, 1, 2, 3 steps left or right with probability 1/2 each and stops at 0 or 3. Starting at 1, find the probability of reaching 3 and the expected number of steps.

   Show answer

   N = (I − Q)⁻¹ has first row (4/3, 2/3). The chance of reaching 3 is (2/3) · (1/2) = 1/3, and the expected number of steps is 4/3 + 2/3 = 2.

5. Every column of a transition matrix P on K states also sums to 1. What is its stationary distribution?

   Show answer

   The uniform one, π_i = 1/K: entry j of (1/K, …, 1/K)P is the column sum divided by K, which is 1/K.