Phase 8 - Lesson 8.1

Markov Chains

Memoryless processes on discrete state spaces: transition matrices, the Chapman-Kolmogorov equations, classification of states, and convergence to a stationary distribution.

⏱ 55 min● Advanced🔗 Prereqs: 7.3

↖ Phase 8 hub

Builds on: 7.3 gave conditional probability and independence.
Leads to: The Markov property generalizes to Brownian motion (8.3) and diffusion pricing models.

Learning Objectives

Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.

State the Markov property and encode a chain by its transition matrix.
Compute multi-step transition probabilities via Chapman-Kolmogorov.
Classify states as recurrent/transient and periodic/aperiodic.
Solve for a stationary distribution and state when the chain converges to it.

Key Vocabulary

Markov property: \(\Prob(X_{n+1}=j\mid X_n=i,\text{past})=\Prob(X_{n+1}=j\mid X_n=i)\): the future depends on the past only through the present.

Transition matrix: \(P=(p_{ij})\) with \(p_{ij}=\Prob(X_{n+1}=j\mid X_n=i)\); rows are probability vectors (stochastic matrix).

Chapman-Kolmogorov: \(P^{(m+n)}=P^{(m)}P^{(n)}\); \(n\)-step probabilities are matrix powers \(P^n\).

Stationary distribution: A row vector \(\pi\ge0\), \(\sum\pi_i=1\), with \(\pi P=\pi\); invariant under one step.

Recurrent / transient: A state is recurrent if the chain returns to it with probability 1, else transient.

Irreducible / aperiodic: Irreducible: every state reaches every other; aperiodic: gcd of return times is 1.

Intuition & Motivation

Intuition

A Markov chain forgets. To predict tomorrow you need only today’s state, not the entire history - the current state is a sufficient statistic for the future. That single assumption compresses a process into a matrix \(P\) of one-step probabilities, and everything else is linear algebra: \(n\)-step behaviour is \(P^n\), and the long-run frequencies are the left eigenvector \(\pi\) with eigenvalue 1. When the chain is irreducible and aperiodic, memory of the start washes out and the distribution converges to \(\pi\) regardless of where it began - the discrete ancestor of every equilibrium and mixing result.

Chains, matrices, and Chapman-Kolmogorov

Definition - Markov chain

A sequence \((X_n)\) on a countable state space \(S\) is a Markov chain if for all states and times

\[\Prob(X_{n+1}=j\mid X_n=i,X_{n-1},\dots)=\Prob(X_{n+1}=j\mid X_n=i)=p_{ij}.\] (8.1)

The matrix \(P=(p_{ij})\) has non-negative entries and rows summing to 1.

Theorem - Chapman-Kolmogorov

The \(n\)-step transition probabilities are the entries of the matrix power: \(\Prob(X_{n}=j\mid X_0=i)=(P^n)_{ij}\), and \(P^{(m+n)}=P^{(m)}P^{(n)}\).

If \(\mu_0\) is the initial distribution (a row vector), then the distribution at time \(n\) is \(\mu_n=\mu_0 P^n\). Markov modeling reduces prediction to matrix multiplication.

Classification and long-run behaviour

States are recurrent (return probability 1) or transient (positive escape probability). A chain is irreducible if all states communicate, and aperiodic if the gcd of possible return times is 1. These properties determine convergence.

Theorem - Existence and convergence to stationarity

An irreducible chain on a finite state space has a unique stationary distribution \(\pi\) solving \(\pi P=\pi\), \(\sum_i\pi_i=1\). If in addition it is aperiodic, then \(\lim_{n\to\infty}(P^n)_{ij}=\pi_j\) for all \(i\): the chain forgets its start. By the ergodic theorem, \(\pi_j\) is also the long-run fraction of time spent in \(j\).

A useful shortcut: if \(\pi\) satisfies detailed balance \(\pi_i p_{ij}=\pi_j p_{ji}\) (reversibility), it is automatically stationary. This is the basis of MCMC samplers.

Worked Example - A two-state weather chain

States \(\{\text{Sun},\text{Rain}\}\) with \(P=\begin{pmatrix}0.9&0.1\\0.5&0.5\end{pmatrix}\): sunny days persist, rain clears fast.

Solve \(\pi P=\pi\): \(\pi_S=0.9\pi_S+0.5\pi_R\) and \(\pi_S+\pi_R=1\).

From the first equation \(0.1\pi_S=0.5\pi_R\Rightarrow \pi_S=5\pi_R\). With normalization \(6\pi_R=1\), so \(\pi_R=1/6,\ \pi_S=5/6\).

Long run: about \(83.3\%\) sunny days, independent of today’s weather - the chain is irreducible and aperiodic, so \(P^n\) rows converge to \((5/6,1/6)\).

Check via detailed balance: \(\pi_S p_{SR}=\tfrac56\cdot0.1=\tfrac{1}{12}\) and \(\pi_R p_{RS}=\tfrac16\cdot0.5=\tfrac{1}{12}\) - equal, confirming stationarity.

Interactive: simulate a chain and recover its stationary distribution

Common Mistakes to Avoid

Confusing the stationary equation \(\pi P=\pi\) (left eigenvector) with \(P\pi=\pi\); \(\pi\) multiplies \(P\) on the left as a row vector.
Expecting convergence for a periodic chain - a chain that alternates deterministically has a stationary \(\pi\) but \(P^n\) does not converge.
Assuming every stationary distribution is unique; uniqueness needs irreducibility.
Reading rows and columns of \(P\) backwards - row \(i\) holds the out-probabilities from state \(i\).

Quant Practitioner Tips

To find \(\pi\), solve \(\pi(P-I)=0\) with \(\sum\pi_i=1\), or take the left eigenvector of \(P\) for eigenvalue 1.
Detailed balance is the fastest stationarity check and the design principle behind Metropolis-Hastings.
The second-largest eigenvalue modulus controls the mixing rate: closer to 1 means slower convergence.

Practice this in the Euler Lab

Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.

Warm-up:
#84 Monopoly Odds (12%, tier B)

Applied:
#315 Digital Root Clocks (18%, tier B) #978 Random Walk Skewness (25%, tier B) #280 Ant and Seeds (40%, tier C)

Challenge:
#227 The Chase (49%, tier C) #959 Asymmetric Random Walk (50%, tier C)

10 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.

Knowledge Check

Q1 Medium

The stationary distribution \(\pi\) of a chain with transition matrix \(P\) satisfies:

\(P\pi=\pi\)

\(\pi P=\pi\) with \(\sum_i\pi_i=1\)

\(\pi P=0\)

\(P^2=P\)

Q2 Medium

For an irreducible, aperiodic finite chain, \(\lim_{n\to\infty}(P^n)_{ij}\) equals:

0 for all j

\(\pi_j\), independent of the start i

\(p_{ij}\)

1 for j=i

Q3 Hard

Which property guarantees the n-step matrix \(P^n\) actually converges (not just that \(\pi\) exists)?

Recurrence alone

Aperiodicity (together with irreducibility)

A symmetric \(P\)

Having two states

Practical Exercise

A share of a stock is modeled as a chain on \(\{\text{Down},\text{Flat},\text{Up}\}\) with rows \((0.5,0.3,0.2),(0.2,0.6,0.2),(0.2,0.3,0.5)\). (a) Is it irreducible and aperiodic? (b) Set up the equations for \(\pi\). (c) By symmetry guess and verify \(\pi\).

▶ Show full solution

(a) Every state reaches every other in one step (all entries positive), so it is irreducible; positive diagonal entries make it aperiodic.

(b) \(\pi P=\pi\) gives: \(\pi_D=0.5\pi_D+0.2\pi_F+0.2\pi_U\); \(\pi_F=0.3\pi_D+0.6\pi_F+0.3\pi_U\); \(\pi_U=0.2\pi_D+0.2\pi_F+0.5\pi_U\); plus \(\pi_D+\pi_F+\pi_U=1\).

(c) The matrix is symmetric under swapping Down and Up, so guess \(\pi_D=\pi_U\). The middle equation becomes \(0.4\pi_F=0.3\pi_D+0.3\pi_U=0.6\pi_D\Rightarrow\pi_F=1.5\pi_D\). Normalizing \(\pi_D+1.5\pi_D+\pi_D=1\Rightarrow\pi_D=\pi_U=2/7,\ \pi_F=3/7\). Substituting back verifies all equations.

After the reveal, answer for yourself: Would the stationary distribution change if you started the chain from a certainty of Up?

Lesson Summary

A Markov chain is a memoryless process encoded by a stochastic transition matrix \(P\); Chapman-Kolmogorov makes multi-step prediction the matrix power \(P^n\). States classify as recurrent/transient and periodic/aperiodic, and an irreducible aperiodic finite chain converges to a unique stationary distribution \(\pi P=\pi\) that also gives the long-run time fractions.

Formula Sheet Additions

Stationarity

\[\pi P=\pi,\ \textstyle\sum_i\pi_i=1\]

Long-run distribution as a left eigenvector.

Detailed balance

\[\pi_i p_{ij}=\pi_j p_{ji}\Rightarrow \pi\text{ stationary}\]

Reversibility, the basis of MCMC.

Error Log Checklist

Did I solve \(\pi P=\pi\) (left) rather than \(P\pi=\pi\)?
Did I check aperiodicity before claiming \(P^n\) converges?
Did I read rows of \(P\) as out-probabilities?

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers

Q: State the Markov property in words.
A: Given the present state, the future is conditionally independent of the past: the present is a sufficient statistic.

Q: How do you compute \(n\)-step transition probabilities?
A: Take the matrix power: \((P^n)_{ij}\), by Chapman-Kolmogorov.

Q: What two conditions guarantee convergence to a unique stationary \(\pi\)?
A: Irreducibility (all states communicate) and aperiodicity (gcd of return times is 1), on a finite state space.

Flashcards

Click to flip. These feed the site-wide spaced-repetition queue.

Stationary distribution

Row vector \(\pi\) with \(\pi P=\pi\), \(\sum\pi_i=1\); the long-run and time-average distribution.

Chapman-Kolmogorov

\(n\)-step probabilities are entries of \(P^n\).

Completion Checklist

I can explain the core ideas in my own words
I worked the derivations/examples by hand
I completed the interactive workbench(es)
I passed the knowledge check

Confidence / mastery rating

Personal notes

Source References

This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.

Probability: Theory and Examples (Rick Durrett, 5th ed.) current - Ch. 5 - Ch. 5: Markov chains, recurrence, stationary distributions, convergence.
Brownian Motion and Stochastic Calculus (Karatzas & Shreve, 2nd ed., GTM 113) foundational - Ch. 2 - Markov property as the discrete precursor to diffusions.

← 7.7 Next: 8.2 →