Chapter XV · 28 min

Markov Chains

Tomorrow asks only about today

“The probability of the next letter depends only on the letter just written.”

So far a random variable has been a number attached to one experiment. A Markov chain is a sequence of those numbers — today’s weather, tomorrow’s, the day after — with a merciful rule: the future cares about the past only through the present. You do not need yesterday’s rain to predict tomorrow, once you know today.

That rule is the whole subject. The linear algebra is a way of writing it down: a row of today’s chances, a table of “from → to”, a multiplication that produces tomorrow. We will do the multiplication by hand. Eigenvectors can wait; two equations will do.

Only today

Write $X_0,X_1,X_2,\dots$ for the state at times $0,1,2,\dots$. The chain is Markov when

In English: given where you are, the next step forgets how you arrived. That is the same mood as the geometric and the exponential — memoryless — but now the “memory” that is discarded is the whole path, not just a waiting time.

The only matrices you need

A vector, here, is a row of numbers that add to one: today’s distribution over states. A matrix is a table. Each row of the table is “where I go tomorrow, given I am in this state today”. Those rows also add to one. Multiplying the row by the table is ordinary arithmetic: for each destination, add up “chance I am here × chance I step there”.

If today is 80% sun,

That is matrix multiplication. You just did it. The compact line is ${\pi }_{t+1}={\pi }_{t}P$. After two steps, ${\pi }_2={\pi }_0{P}^2$ — apply the table twice. No inverse, no determinant, no eigenvalue yet.

Where the crowd settles

Start at sun, or rain, or 80% sun. Apply the table again and again. For this weather, the row forgets its start and settles at one place:

Two unknowns, two honest equations. From the rain column (or sun — they are redundant once rows sum to one),

With ${\pi }_{\mathrm{rain}}=1-{\pi }_{\mathrm{sun}}$, you get $0.3{\pi }_{\mathrm{sun}}=0.5(1-{\pi }_{\mathrm{sun}})$, hence ${\pi }_{\mathrm{sun}}=5/8$, ${\pi }_{\mathrm{rain}}=3/8$. In the long run this climate is sunny five days in eight, whatever the first day was. That settled row is the stationary distribution.

• Not every chain settles. A deterministic flip-flop Sun→Rain→Sun never forgets the parity of the day.
• If you can eventually reach anywhere from anywhere, and you are not trapped in a forced cycle, one stationary row exists and the crowd finds it.
• Absorbing states — “the game ended” — keep you once you arrive. Then the long run is “which ending?”, not a blend of weather.