Topic 7 of 7

Markov chains

Step 22 · Probability theory topics

Model a process that jumps between states with fixed probabilities, work out where it is likely to be after several steps, and find its long-run stationary distribution.

Transition matrices

A Markov chain moves between states, and the chance of the next state depends only on the current state, not on the history. Collect the chances in a transition matrix P: the entry in row i, column j is the chance of moving from state i to state j. Each row adds to 1.

Example: Weather

A sunny day is followed by sun with probability 0.8, and a rainy day by rain with probability 0.6. Write the transition matrix, with sunny first.

Row sunny: 0.8 to sunny, 0.2 to rainy.
Row rainy: 0.4 to sunny, 0.6 to rainy.

Answer $\begin{pmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{pmatrix}$

Multi-step probabilities

If the chain's distribution now is the row vector π, after one step it is πP, and after n steps πPⁿ. The entry in row i, column j of Pⁿ is the chance of going from i to j in n steps.

Example: Two days ahead

Today is sunny. What is the chance of rain in two days?

Sun, then rain: 0.8 × 0.2 = 0.16.
Rain, then rain: 0.2 × 0.6 = 0.12.
Add the two routes.

Answer0.28

Example: Starting from a mix

Today is sunny with probability 0.5. What is the chance that tomorrow is sunny?

0.5 × 0.8 + 0.5 × 0.4.

Answer0.6

Stationary distributions

A stationary distribution π satisfies πP = π: if the chain starts there, it stays there. For many chains, wherever they start, the distribution after many steps approaches π, which is the long-run share of time spent in each state.

Example: Long-run weather

Find the stationary distribution of the weather chain.

πP = π with π = (s, r): s = 0.8s + 0.4r, so 0.2s = 0.4r and s = 2r.
s + r = 1 gives r = 1/3.

AnswerSunny on 2/3 of days, rainy on 1/3

Starting on a sunny day, the chance of sun falls 1, 0.8, 0.72, 0.688, … toward its long-run value, 2/3.

Example: Absorbing states

A player with $1 bets $1 at a time on fair coin flips, stopping at $0 or $3. What is the chance of reaching $3?

Let pₖ be the chance of reaching $3 from $k: p₀ = 0, p₃ = 1, and each pₖ is the average of its neighbors.
So the pₖ rise in a straight line: pₖ = k/3.

Answer1/3

Try it yourself

Work each one on paper first, then open the answer to check.

Each row of a transition matrix adds to what?
Show answer
1
With P = $\begin{pmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{pmatrix}$ , if today is rainy, what is the chance tomorrow is sunny?
Show answer
0.4
Today is rainy. What is the chance it is rainy in two days?
Show answer
0.44
Find the stationary distribution of $\begin{pmatrix} 0.5 & 0.5 \\ 0.5 & 0.5 \end{pmatrix}$ .
Show answer
(0.5, 0.5)
A chain's stationary distribution is (0.25, 0.75). In the long run, what fraction of steps are spent in state 2?
Show answer
0.75
In the betting example, what is the chance of reaching $3 starting with $2?
Show answer
$\frac{2}{3}$