Advanced32 min

Markov Chains

Transition matrices, Chapman–Kolmogorov, classification of states, and stationary distributions.

Assumes you know

Markov Chains

Intuition first

A Markov chain is a system that moves between states, where the next state depends only on the current one — not on how you got there. Today's weather determines tomorrow's probabilities; last week's weather adds nothing once today is known.

That restriction is the Markov property, and it is what makes the model tractable. Instead of tracking a whole history, you need a single matrix of transition probabilities.

Two questions matter. Short-term: where will the system be in $k$ steps? That is matrix powers. Long-term: does it settle into a stable pattern of state occupancies? That is a stationary distribution, and it turns out to be an eigenvector problem — which is why this lesson requires linear algebra.

Markov chains sit directly beneath hidden Markov models, PageRank, MCMC sampling, and the MDPs of reinforcement learning. This is the last lesson in the probability module and the bridge to all four.

The Markov property

\Prob(X_{t+1} = j \mid X_t = i, X_{t-1}, \dots, X_0) = \Prob(X_{t+1} = j \mid X_t = i)

The current state is a sufficient summary of the past.

Notation used in this lesson
Symbol	Meaning	Read aloud
Xₜ	State at time t	X sub t
P	Transition matrix, with Pᵢⱼ = P(i → j)	P
π	State distribution, a row vector	pi
π*	Stationary distribution	pi star
Pᵏ	k-step transition matrix	P to the k

The transition matrix

P_{ij} = \Prob(X_{t+1} = j \mid X_t = i)

Each row is a probability distribution over destinations, so every row sums to 1. A matrix with this property is called row-stochastic.

Multi-step transitions

\Prob(X_{t+k} = j \mid X_t = i) = \big(P^k\big)_{ij}

The Chapman–Kolmogorov equationsAdvanced

Two steps, from $i$ to $j$ , must pass through some intermediate state $m$ . Summing over all possibilities — the law of total probability:

\Prob(X_{t+2} = j \mid X_t = i) = \sum_m \Prob(X_{t+1} = m \mid X_t = i)\,\Prob(X_{t+2} = j \mid X_{t+1} = m)

The second factor dropped the conditioning on $X_t$ by the Markov property. The right-hand side is

\sum_m P_{im}P_{mj} = \big(P^2\big)_{ij}

which is precisely the definition of matrix multiplication. Induction extends it:

P^{(m+n)} = P^{(m)}P^{(n)}

So the whole temporal structure of the chain is encoded in powers of one matrix, and questions about the future become linear algebra. This is why eigendecomposition is the natural tool.

If the state distribution at time $t$ is the row vector $\pi_t$ , then

\pi_{t+k} = \pi_t P^k

Stationary distributions

A distribution $\pi^*$ is stationary if applying the chain leaves it unchanged:

\pi^* P = \pi^*, \qquad \sum_i \pi^*_i = 1

Solved problem 1 · Weather chain, computed fully

Weather is Sunny or Rainy. If sunny today, tomorrow is sunny with probability 0.8. If rainy today, tomorrow is rainy with probability 0.6.

(a) Write $P$ . (b) Given sunny today, find the distribution in two days. (c) Find the stationary distribution. (d) Verify it.

Step 1 — part (a): build the matrix

Order the states (Sunny, Rainy). Sunny → sunny is 0.8, so sunny → rainy is 0.2. Rainy → rainy is 0.6, so rainy → sunny is 0.4.

P = \begin{pmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{pmatrix}

Row sums: $0.8 + 0.2 = 1$ and $0.4 + 0.6 = 1$ ✓

Step 2 — part (b): one step

Start with $\pi_0 = (1, 0)$ — sunny with certainty.

\pi_1 = \pi_0 P = (1, 0)\begin{pmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{pmatrix} = (0.8,\; 0.2)

Step 3 — two steps

\pi_2 = \pi_1 P = (0.8, 0.2)\begin{pmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{pmatrix}

First component:

0.8(0.8) + 0.2(0.4) = 0.64 + 0.08 = 0.72

Second component:

0.8(0.2) + 0.2(0.6) = 0.16 + 0.12 = 0.28

\pi_2 = (0.72,\; 0.28)

Step 4 — part (c): solve for the stationary distribution

Write $\pi^* = (s, r)$ with $s + r = 1$ . The condition $\pi^* P = \pi^*$ gives two equations; use the first:

0.8s + 0.4r = s

Substitute $r = 1 - s$ :

0.8s + 0.4(1 - s) = s

0.8s + 0.4 - 0.4s = s

0.4s + 0.4 = s

0.4 = 0.6s \quad\Longrightarrow\quad s = \frac{0.4}{0.6} = \frac{2}{3}

\pi^* = \left(\tfrac{2}{3},\; \tfrac{1}{3}\right) \approx (0.6667,\; 0.3333)

Step 5 — part (d): verify

\pi^* P = \left(\tfrac23, \tfrac13\right)\begin{pmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{pmatrix}

First component:

\tfrac23(0.8) + \tfrac13(0.4) = \tfrac{1.6}{3} + \tfrac{0.4}{3} = \tfrac{2.0}{3} = \tfrac23 \;\checkmark

Second component:

\tfrac23(0.2) + \tfrac13(0.6) = \tfrac{0.4}{3} + \tfrac{0.6}{3} = \tfrac{1.0}{3} = \tfrac13 \;\checkmark

Step 6 — watch the convergence

\pi_0 = (1.0000,\, 0.0000)

\pi_1 = (0.8000,\, 0.2000)

\pi_2 = (0.7200,\, 0.2800)

\pi_3 = (0.6880,\, 0.3120)

\pi_4 = (0.6752,\, 0.3248)

\pi_\infty = (0.6667,\, 0.3333)

Converging geometrically. The rate is governed by the second-largest eigenvalue, here $\lambda_2 = 0.4$ , so the error shrinks by a factor of 0.4 each step — visible in the sequence, where the gap from $2/3$ goes $0.1333, 0.0533, 0.0213, 0.0085$ .

Answer

$P = \begin{pmatrix} 0.8 & 0.2 \\ 0.4 & 0.6\end{pmatrix}$ ; after two days $(0.72, 0.28)$ ; stationary $\pi^* = (2/3, 1/3)$ . In the long run it is sunny two days in three regardless of today's weather.

Classification of states

Term	Meaning
Accessible	$j$ reachable from $i$ in some number of steps
Communicating	$i$ and $j$ each accessible from the other
Irreducible	All states communicate — one class
Recurrent	Return is certain
Transient	Return has probability less than 1
Absorbing	$P_{ii} = 1$ — once entered, never left
Period	gcd of return times; aperiodic if the period is 1

Where this leads

Hidden Markov models add unobserved states emitting observations — the Viterbi and forward–backward algorithms operate on exactly this machinery.
PageRank is the stationary distribution of a random surfer on the web graph, computed by power iteration, which is nothing but repeated multiplication by $P$ .
MCMC reverses the problem: given a target $\pi$ , construct a $P$ whose stationary distribution is $\pi$ , then run it.
MDPs add actions and rewards to a Markov chain, which is the entire foundation of reinforcement learning.

python

import numpy as np

P = np.array([[0.8, 0.2],
              [0.4, 0.6]])

# Verify row-stochasticity.
assert np.allclose(P.sum(axis=1), 1.0)

# Forward iteration from a sunny start.
pi = np.array([1.0, 0.0])
print("step  P(sunny)  P(rainy)   error from 2/3")
for t in range(6):
    print(f"{t:4d}  {pi[0]:8.4f}  {pi[1]:8.4f}   {abs(pi[0] - 2/3):.6f}")
    pi = pi @ P

# Stationary distribution as the left eigenvector for eigenvalue 1.
vals, vecs = np.linalg.eig(P.T)          # transpose for LEFT eigenvectors
i = np.argmin(np.abs(vals - 1.0))
stat = np.real(vecs[:, i]); stat /= stat.sum()
print(f"\nstationary (eigenvector) {stat}")
print(f"theory                   [{2/3:.6f} {1/3:.6f}]")

# Convergence rate is set by the second-largest eigenvalue modulus.
print(f"eigenvalues {np.sort(np.abs(vals))[::-1]}  -> rate {np.sort(np.abs(vals))[::-1][1]:.2f}")

# A periodic chain: stationary distribution exists but is never reached.
Q = np.array([[0.0, 1.0], [1.0, 0.0]])
p = np.array([1.0, 0.0])
print("\nperiodic chain, never converges:")
for t in range(4):
    print(f"  step {t}: {p}")
    p = p @ Q

Exercise 1

A machine is Working or Broken. Working → broken with probability 0.1; broken → working with probability 0.5. What fraction of time is it working in the long run?

Show solution

P = \begin{pmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \end{pmatrix}

Let $\pi^* = (w, b)$ with $w + b = 1$ . The stationarity condition on the first component:

0.9w + 0.5b = w

Substitute $b = 1 - w$ :

0.9w + 0.5 - 0.5w = w \quad\Longrightarrow\quad 0.4w + 0.5 = w \quad\Longrightarrow\quad 0.5 = 0.6w

w = \frac{0.5}{0.6} = \frac{5}{6} \approx 0.8333

Working about 83.3% of the time.

A useful cross-check: for a two-state chain the stationary probability of state 1 is $\frac{P_{21}}{P_{12} + P_{21}} = \frac{0.5}{0.1 + 0.5} = \frac{5}{6}$ ✓. The chain spends time in each state in inverse proportion to how readily it leaves.

Exercise 2

Explain why a chain with two absorbing states has no unique stationary distribution.

Show solution

An absorbing state $i$ has $P_{ii} = 1$ , so once entered the chain never leaves.

With two absorbing states $a$ and $b$ , both $\pi = (\dots, 1 \text{ at } a, \dots)$ and $\pi = (\dots, 1 \text{ at } b, \dots)$ satisfy $\pi P = \pi$ — each is stationary, since a chain sitting in an absorbing state stays there.

Worse, any mixture is also stationary:

\pi = \alpha \delta_a + (1-\alpha)\delta_b, \qquad 0 \leq \alpha \leq 1

gives an infinite family of stationary distributions.

The structural reason is reducibility. The convergence theorem requires irreducibility — every state reachable from every other. Here $a$ cannot be reached from $b$ or vice versa, so the state space splits into separate communicating classes and the chain has no single long-run behaviour. Which absorbing state you end up in depends on where you started.

The interesting question for such chains is therefore not "what is the stationary distribution" but "what is the probability of absorption into each state, given the start" — the absorption probability, computed by solving a linear system over the transient states. Gambler's ruin is the classic example, and the same structure appears in MDPs with terminal states.

That completes the core of the probability module. Next in the curriculum: Statistics and Inference, which uses everything here to reason from samples back to populations.