Markov Chains & Long-Run Behavior

Study Sheet

Markov Chains & Long-Run Behavior

Steady states, mixing, and absorbing states

Probability Meets Eigenvectors

Tip
Transition matrices and the eigenvalue 1

A Markov chain hops among states with fixed probabilities; its transition matrix MM has nonnegative entries and columns summing to 11.

That column condition forces λ=1\lambda = 1 to be an eigenvalue (the all-ones vector is a LEFT eigenvector), and its right eigenvector — normalized to sum to 11 — is the STEADY STATE: the distribution the chain settles into regardless of where it started. Finding it is one homogeneous solve: (M−I)v=0(M - I)\mathbf v = \mathbf 0. All other eigenvalues have ∣λ∣≤1|\lambda| \le 1, and the second-largest, ∣λ2∣|\lambda_2|, sets the MIXING RATE: the memory of the starting state decays like ∣λ2∣n|\lambda_2|^n.

Side note
PageRank is a steady state

Google's original algorithm models a random web surfer: from each page, follow a random link (with occasional random jumps). The importance of a page is its share of the STEADY-STATE distribution of that Markov chain — the λ=1\lambda = 1 eigenvector of a matrix with billions of rows, computed by simply iterating v↦Mv\mathbf v \mapsto M\mathbf v (the power method) until it stops changing. A trillion-dollar company, built on this chapter.

Tip
Absorbing chains and expected times

Some states trap you (absorbing); the natural question becomes "how long until absorption?" First-step analysis: from state ii, one step happens, then you are somewhere new — so Ei=1+∑jpijEjE_i = 1 + \sum_j p_{ij}E_j, a small LINEAR SYSTEM in the expected times.

A state that advances with probability pp and stalls otherwise contributes 1p\tfrac1p expected steps (the geometric distribution). Gambler's ruin, board-game durations, drug absorption, and queue lengths are all this one linear system with different numbers.

Try it
Try it: steady state and mixing in one go

For M=(0.90.20.10.8)M = \begin{pmatrix}0.9&0.2\\0.1&0.8\end{pmatrix}: (a) steady state: −0.1v1+0.2v2=0-0.1v_1 + 0.2v_2 = 0 gives v1:v2=2:1v_1 : v_2 = 2 : 1, so (23,13)\left(\tfrac23, \tfrac13\right); (b) mixing rate: trace 1.71.7 minus the known eigenvalue 11 leaves λ2=0.7\lambda_2 = 0.7 — deviations shrink 30%30\% per step, so after 1010 steps only (0.7)10≈3%(0.7)^{10} \approx 3\% of any initial imbalance survives. Verify (a) by one multiplication: M(2/31/3)=(2/31/3)M\binom{2/3}{1/3} = \binom{2/3}{1/3} ✓.

Proofs & Why It Matters

Tip
Proof: λ = 1 is always an eigenvalue

Let 1=(1,1,…,1)\mathbf 1 = (1, 1, \ldots, 1). Column sums equal 11 means 1TM=1T\mathbf 1^{\mathsf T}M = \mathbf 1^{\mathsf T} — so 11 is an eigenvalue of MTM^{\mathsf T}, and a matrix and its transpose share a characteristic polynomial, hence eigenvalues: 11 is an eigenvalue of MM too.

Moreover no eigenvalue can exceed 11 in magnitude: if Mv=λvM\mathbf v = \lambda\mathbf v, comparing the largest-magnitude entry of both sides shows ∣λ∣≤1|\lambda| \le 1 (each entry of MvM\mathbf v is a weighted average of entries of v\mathbf v). ■\blacksquare SIGNIFICANCE: existence of a steady state is thus STRUCTURAL — probability is conserved, so equilibrium is guaranteed; the only question is how fast you get there, which is ∣λ2∣|\lambda_2|'s job.

Side note
The bridge back

Markov chains tie the whole course together: the steady state is an eigenvector (eigenvalues topic), computing MnM^n is diagonalization (powers topic), the entries of MnM^n converge because ∣λ2∣<1|\lambda_2| < 1 (spectral thinking), and expected absorption times are a linear system (row reduction). One applied object exercising every tool in the box — which is exactly why it closes the course.

Going Deeper: Worked Problems

Example
Worked: a three-state weather chain, start to steady state

Sunny goes to sunny with probability 0.70.7, else rainy; rainy goes to rainy 0.50.5, sunny 0.30.3, cloudy 0.20.2; cloudy goes to sunny 0.40.4, cloudy 0.60.6. Find the long-run fraction of sunny days.

Step 1 — transition matrix (columns from-state, rows to-state): M=(0.70.30.40.30.5000.20.6)M = \begin{pmatrix}0.7&0.3&0.4\\0.3&0.5&0\\0&0.2&0.6\end{pmatrix}; each column sums to 11 ✓.

Step 2 — steady state solves Mv=vM\mathbf v = \mathbf v: from row 2, 0.3s+0.5r=r0.3s + 0.5r = r gives r=0.6sr = 0.6s; from row 3, 0.2r+0.6c=c0.2r + 0.6c = c gives c=0.5r=0.3sc = 0.5r = 0.3s.

Step 3 — normalize: s+0.6s+0.3s=1s + 0.6s + 0.3s = 1, so s=11.9=1019≈52.6%s = \dfrac{1}{1.9} = \dfrac{10}{19} \approx 52.6\% sunny, r=619r = \tfrac{6}{19}, c=319c = \tfrac{3}{19}.

Step 4 — verify row 1: 0.7⋅1019+0.3⋅619+0.4⋅319=7+1.8+1.219=10190.7\cdot\tfrac{10}{19} + 0.3\cdot\tfrac{6}{19} + 0.4\cdot\tfrac{3}{19} = \tfrac{7 + 1.8 + 1.2}{19} = \tfrac{10}{19} ✓. The forecast for a year from now needs no calendar — only this eigenvector.

Example
Worked: expected time to absorb, by first-step equations

A token starts at 00 and each second moves +1+1 with probability 23\tfrac23 or stays with probability 13\tfrac13; it stops on reaching 33. Expected time to stop?

Step 1 — let EkE_k be the expected remaining time from position kk, with E3=0E_3 = 0.

Step 2 — first-step analysis at each state: Ek=1+23Ek+1+13EkE_k = 1 + \tfrac23E_{k+1} + \tfrac13E_k, so 23Ek=1+23Ek+1\tfrac23E_k = 1 + \tfrac23E_{k+1}, i.e. Ek=32+Ek+1E_k = \tfrac32 + E_{k+1}.

Step 3 — unwind from the end: E2=1.5E_2 = 1.5, E1=3E_1 = 3, E0=4.5E_0 = 4.5.

Step 4 — interpret: each step forward takes 12/3=1.5\tfrac{1}{2/3} = 1.5 expected seconds (geometric distribution), and three steps are needed — linearity of expectation gives 4.54.5 directly, and the linear system confirms it.