🔁 Markov chains

A Markov chain is a process that forgets its past: where it goes next depends only on where it is now. That one assumption turns hard questions about long random processes into small systems of linear equations.

The Markov property

A Markov chain is a sequence of random variables $X_0, X_1, X_2,\dots$ taking values in a state space $S$, such that the future depends on the past only through the present:

$$P(X_{t+1}=j \mid X_t=i,\ X_{t-1}=i_{t-1},\dots,X_0=i_0) \;=\; P(X_{t+1}=j\mid X_t=i).$$

Picture a frog hopping between lily pads. When it decides where to jump, it looks only at the pad it is sitting on. It does not remember how it got there. If you know the current pad, the whole history is irrelevant.

Examples: a board game like Snakes & Ladders (your next square depends only on your current square and the die), your bankroll in a betting game, a random walk on a graph, or the weather in a toy model ("sunny today → 80% sunny tomorrow").

Make the state big enough. Many puzzles become Markov once the state remembers a little more. For "expected flips until two heads in a row", the useful state is the current run of heads: 0, 1, or "done". For "expected flips until HTH", it's the longest suffix that matches a prefix of HTH. Choosing the right state is usually the whole trick.

You draw cards one at a time from a shuffled deck without replacement. Is "the value of the card just drawn" a Markov chain?

Yes: the next card only depends on the current card
No: which cards are still in the deck depends on the whole history
Yes, because the deck is shuffled uniformly

The probability that the next card is an ace depends on how many aces have already appeared, not just on the last card. To make it Markov, the state would need to be the set of cards remaining.

The transition matrix

For a finite state space $\{1,\dots,n\}$, the whole chain is described by an $n\times n$ transition matrix:

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

Row $i$ is "where can I go from $i$, and with what probability". So every row is a probability distribution: entries are $\ge 0$ and each row sums to 1. (Columns need not sum to anything in particular.)

If $\pi_t$ is the row vector of probabilities of being in each state at time $t$, then one step of the chain is one matrix multiplication:

$$\pi_{t+1}=\pi_t P \qquad\Longrightarrow\qquad \pi_t=\pi_0 P^t.$$

Why? (law of total probability)

To be at $j$ at time $t+1$, you were at some state $i$ at time $t$ and then jumped $i\to j$:

$$P(X_{t+1}=j)=\sum_i P(X_t=i)\,P(X_{t+1}=j\mid X_t=i)=\sum_i (\pi_t)_i\,P_{ij}=(\pi_tP)_j.$$

That sum is exactly "row vector times column $j$ of $P$".

Worked example. Weather: sunny (S) stays sunny with probability 0.8, rainy (R) stays rainy with probability 0.6.

$$P=\begin{pmatrix}0.8 & 0.2\\ 0.4 & 0.6\end{pmatrix},\qquad \pi_0=(1,\,0)\ \text{(sunny today)}$$ $$\begin{aligned}\pi_1&=\pi_0P=(0.8,\ 0.2)\\ \pi_2&=\pi_1P=(0.8\cdot0.8+0.2\cdot0.4,\ \ 0.8\cdot 0.2+0.2\cdot 0.6)=(0.72,\ 0.28)\end{aligned}$$

Stationary distribution

A stationary distribution is a distribution that one step of the chain leaves unchanged:

$$\pi=\pi P,\qquad \sum_i\pi_i=1,\ \ \pi_i\ge 0.$$

If you start the chain with $X_0\sim\pi$, then $X_1\sim\pi$, $X_2\sim\pi$, and so on forever. Individual states keep changing, but the distribution is in balance: the probability flowing into each state equals the probability flowing out.

The headline theorem: for a chain that is

finite (finitely many states),
irreducible (every state can reach every other state), and
aperiodic (it does not cycle with a fixed period, e.g. a self-loop anywhere is enough when irreducible),

there is a unique stationary distribution, and $\pi_t\to\pi$ no matter where you start. Moreover, the long-run fraction of time spent in state $i$ equals $\pi_i$.

The original notes said this holds "under mild conditions". Those conditions are exactly: finite + irreducible + aperiodic. Irreducibility gives uniqueness, aperiodicity gives convergence of $\pi_t$. (Without aperiodicity the time-averages still converge to $\pi$; $\pi_t$ itself may oscillate.)

How to compute π

$\pi=\pi P$ is a linear system, but it is rank-deficient: one equation is redundant. Drop any one of them and replace it with the normalization $\sum_i\pi_i=1$.

Two-state formula. If $P=\begin{pmatrix}1-a & a\\ b & 1-b\end{pmatrix}$ then balancing flow between the two states, $\pi_1 a=\pi_2 b$, gives

$$\pi=\Big(\frac{b}{a+b},\ \frac{a}{a+b}\Big).$$

For the weather example, $a=0.2,\ b=0.4$, so $\pi=(2/3,\ 1/3)$: in the long run it is sunny two days out of three.

Random walk on a graph: if at each step you move to a uniformly random neighbor, then $\pi_i=\dfrac{\deg(i)}{2|E|}$. No equations needed. Busy intersections get visited more. On a regular graph (all degrees equal, e.g. a cycle) this is uniform: $\pi_i=1/n$.

Proof of the degree formula

Check $\pi P=\pi$: $(\pi P)_j=\sum_{i\sim j}\frac{\deg i}{2|E|}\cdot\frac1{\deg i}=\frac{\deg j}{2|E|}=\pi_j$. ✓ (Each neighbor $i$ of $j$ sends exactly $1/(2|E|)$ of probability to $j$.)

Expected return time

Start at state $i$. How long, on average, until you come back to $i$?

$$\E[\text{return time to } i]=\frac{1}{\pi_i}.$$

If you spend a fraction $\pi_i$ of all time steps at $i$, say $\pi_i=1/5$, then visits to $i$ happen about once every 5 steps on average. So the gap between consecutive visits is $1/\pi_i$. Rare states take long to come back to.

Proof sketch (renewal argument)

Run the chain for a long time $T$ and let $V_T$ be the number of visits to $i$. Visits split the timeline into return-time "cycles" $R_1, R_2,\dots$ that are i.i.d. by the Markov property (each time you're at $i$, the future starts fresh). So $T\approx R_1+\dots+R_{V_T}\approx V_T\,\E[R]$. Divide by $T$: $1\approx \frac{V_T}{T}\,\E[R]\to \pi_i\,\E[R]$. Hence $\E[R]=1/\pi_i$. (This is Kac's lemma; it needs the chain to be irreducible and finite.)

A knight starts in a corner of an empty chessboard and makes uniformly random legal moves. What is the expected number of moves until it returns to that corner? (The degrees of all 64 squares sum to 336.)

This is a random walk on the "knight graph", so $\pi_i=\deg(i)/\sum\deg=2/336$. A corner has degree 2. Return time is $1/\pi=336/2=168$.

Absorption: hitting times and probabilities

An absorbing state is one you never leave ($P_{AA}=1$): "game over", "reached $N$ dollars", "saw HH". Two questions come up constantly:

How long until we get absorbed? Let $h_i$ be the expected time to absorption starting from state $i$.
Where do we end up? Let $q_i$ be the probability of being absorbed at a particular target $A$ starting from $i$.

Both are solved by first-step analysis: condition on the first move, then use the Markov property to say "from there, it's the same problem starting from the new state".

Expected time

$h_i=1+\sum_j P_{ij}\,h_j$
with $h_A=0$ at absorbing states

Absorption probability

$q_i=\sum_j P_{ij}\,q_j$
with $q_A=1$, and $q_B=0$ at other absorbing $B$

The "$1+$" counts the step you just took. There is no "$1+$" in the probability equation because no time is being counted, only where you end up.

Recipe

Write one equation per non-absorbing state, plus the boundary conditions.
Small chain: just solve the linear system.
Chain with structure (states $0,1,\dots,N$): guess a closed form, then verify it satisfies the equations and fit constants to the boundary conditions. To guess: compute small cases by hand, and think about the shape. E.g. $h_i$ must vanish at both ends and be largest in the middle → try a parabola.

Worked example: symmetric walk between two walls

Walk on $\{0,1,\dots,N\}$, stepping $\pm1$ with probability $\tfrac12$ each, absorbed at $0$ and $N$. This is gambler's ruin with a fair coin.

$$h_i=1+\tfrac12h_{i-1}+\tfrac12h_{i+1},\quad h_0=h_N=0 \qquad\Longrightarrow\qquad h_i=i(N-i).$$ $$q_i=\tfrac12q_{i-1}+\tfrac12q_{i+1},\quad q_0=0,\ q_N=1 \qquad\Longrightarrow\qquad q_i=\frac iN.$$

Verify $h_i=i(N-i)$ (the guess-and-check way)

Boundary: $h_0=0\cdot N=0$ and $h_N=N\cdot 0=0$. ✓ Interior: plug in.

$$1+\tfrac12(i-1)(N-i+1)+\tfrac12(i+1)(N-i-1)=1+\tfrac12\big[2i(N-i)-2\big]=i(N-i).\ ✓$$

How you'd guess it: rearranging gives $h_{i+1}-2h_i+h_{i-1}=-2$. A constant second difference means $h$ is a quadratic in $i$, and a quadratic vanishing at $0$ and $N$ is $c\,i(N-i)$; plugging in gives $c=1$.

For $q$: $q_{i+1}-q_i=q_i-q_{i-1}$, so all consecutive differences are equal, $q$ is linear, and the boundary conditions force $q_i=i/N$.

Using first-step analysis with states "0 heads in a row", "1 head in a row", "HH (absorbed)", what is the expected number of fair coin flips until you see two heads in a row?

$h_0=1+\tfrac12h_1+\tfrac12h_0$ and $h_1=1+\tfrac12\cdot 0+\tfrac12h_0$. Substituting: $h_0=2+h_1=2+1+\tfrac12h_0\Rightarrow h_0=6$.

Symmetry tricks

Collapse equivalent states

If several states "look the same" relative to the question, give them one shared unknown. On a cycle of $n$ nodes, the expected time to hit a target only depends on your distance $d$ to it, not on which node you're at. Reparameterize by distance: $d$ goes up or down by 1 with probability $\tfrac12$, and you stop at $d=0$ or $d=n$ (going all the way around). That's the walk-between-walls example again, so

$$h_d=d\,(n-d).$$

Instead of $n$ unknowns you reuse a solved problem.

Stationary-distribution shortcut for hitting times

On a graph where every node and every edge look the same (cycles, complete graphs, hypercubes), the expected hitting time between adjacent vertices is

$$h_{\text{adjacent}}=n-1.$$

Why (two ways to count the return time)

The graph is regular, so $\pi$ is uniform: $\pi_v=1/n$, and the expected return time to $v$ is $1/\pi_v=n$.
From $v$, the walk takes 1 step to a random neighbor $u$, then needs $h(u\to v)$ more steps to come back: $$\E[\text{return to }v]=1+\frac1d\sum_{u\sim v}h(u\to v).$$ By symmetry all $d$ neighbors have the same $h(u\to v)=h$, so this is $1+h$.

Setting $n=1+h$ gives $h=n-1$.

The shortcut needs real symmetry: the graph must be regular (so $\pi$ is uniform) and every edge must be equivalent (edge-/arc-transitive), so that all neighbors have the same hitting time. On a star it fails: from the center to a given leaf takes $2n-3$ steps on average, while from a leaf to the center takes 1. What does always hold, for any connected graph, is the averaged version:

$$\frac1{\deg v}\sum_{u\sim v}h(u\to v)=\frac{2|E|}{\deg v}-1.$$

A random walk on a 12-hour clock face starts at 12 and moves one hour clockwise or counter-clockwise with equal probability. What is the expected number of steps to reach 6?

By symmetry only the distance matters, and 6 is at distance $d=6$ on a cycle of $n=12$. So $h_d=d(n-d)=6\cdot 6=36$.

Cheat sheet

Question	Tool
Distribution after $t$ steps	$\pi_t=\pi_0P^t$
Long-run fraction of time in $i$	solve $\pi=\pi P,\ \sum\pi_i=1$ (or $\deg(i)/2\|E\|$ for graph walks)
Expected return time to $i$	$1/\pi_i$
Expected time to absorption	$h_i=1+\sum_jP_{ij}h_j$, $h_A=0$
Probability of absorbing at $A$	$q_i=\sum_jP_{ij}q_j$, $q_A=1$, $q_B=0$
Symmetric walk on $0..N$	$h_i=i(N-i)$, $q_i=i/N$
Adjacent hitting time on a symmetric graph	$n-1$