From "what's the weather tomorrow?" to stationary distributions
Picture the weather as a game with a short memory. To guess tomorrow, you only need to know today — sunny or rainy. It doesn't matter that it poured all last week. "Only the present matters for the future" is the entire idea of a Markov chain, and that one rule (called the Markov property) is what makes these chains so easy to work with.
Each situation is a state — here just State 1 and State 2. The chance of hopping from one state to another is a fixed number, the transition probability $p_{ij}$ (chance of going from state $i$ to state $j$). If the chance of staying in State 1 is $p_{11}=0.7$, then the chance of leaving for State 2 is $1-0.7=0.3$. Stack all of these into a transition matrix $\mathbf{P}$ where every row adds to $1$ — because from any state you must land somewhere next step.
A worked number: start in State 1 with $p_{11}=0.7,\ p_{22}=0.6$. After one step the probability of being in State 1 is just $0.7$. After two steps it is $0.7\times0.7+0.3\times(1-0.6)=0.49+0.12=0.61$. Notice it is already drifting away from where it started — and it keeps drifting toward one settled value.
That settled value is the stationary distribution $\boldsymbol{\pi}$: the one row vector that doesn't change when you multiply by the matrix, $\boldsymbol{\pi}\mathbf{P}=\boldsymbol{\pi}$ with $\sum_i\pi_i=1$. For two states there is a tidy closed form, $\pi_1=\dfrac{1-p_{22}}{(1-p_{11})+(1-p_{22})}$. With our numbers $\pi_1=\dfrac{0.4}{0.3+0.4}=\dfrac{0.4}{0.7}\approx0.571$. How fast the chain reaches $\boldsymbol{\pi}$ is set by the second eigenvalue $\lambda_2=p_{11}+p_{22}-1$: the closer $|\lambda_2|$ is to $1$, the slower it mixes. The two sliders set $p_{11}$ and $p_{22}$, and those two numbers alone fix the whole matrix, the stationary $\boldsymbol{\pi}$, and the mixing speed.
Push both sliders high (near $0.95$) and open the Mixing Time tab — the decay curve crawls, because $|\lambda_2|$ sits near $1$. Make the chain symmetric ($p_{11}=p_{22}$) and check the Convergence tab: both starting states settle at a 50/50 split. Finally, set Steps near $2000$, run the chain, and compare the "Emp. freq(1)" card to $\pi_1$ — watching the long-run frequency match the stationary probability is the ergodic theorem in action.
Markov Chains — Andrei Markov, 1906
Markov property: $P(X_{t+1}=j\mid X_t=i,X_{t-1},\ldots)=P(X_{t+1}=j\mid X_t=i)=p_{ij}$
$$\boxed{\text{Stationary distribution: }\boldsymbol{\pi}\mathbf{P}=\boldsymbol{\pi},\quad\sum_i\pi_i=1}$$
2-state: $\pi_1=\dfrac{1-p_{22}}{(1-p_{11})+(1-p_{22})}$
For irreducible aperiodic chains: time averages converge to ensemble averages: $\frac{1}{T}\sum_{t=1}^T f(X_t)\to E_\pi[f]$ a.s. This justifies MCMC sampling.
Convergence rate governed by second eigenvalue $\lambda_2=p_{11}+p_{22}-1$. TV distance $\le |\lambda_2|^t/2$. Mixing time $\approx 1/(1-|\lambda_2|)=$ spectral gap inverse.
Assuming Markov chains always converge to stationary distribution.
Convergence requires: (1) Irreducibility — every state reachable from every other. (2) Aperiodicity — gcd of return times = 1. Absorbing states violate (1). Two-cycle chains violate (2). Also: not checking if empirical frequencies match stationary distribution after short runs — need sufficient mixing time first.
Take two states with $p_{11}=0.7$ and $p_{22}=0.6$. The transition matrix is $P=\begin{pmatrix}0.7&0.3\\0.4&0.6\end{pmatrix}$. Start in state 1 with certainty. After one step the distribution is (0.700, 0.300); after two steps it is (0.610, 0.390); after three it is (0.583, 0.417); after five it is (0.5725, 0.4275). It settles on the stationary distribution $\pi=(4/7,\,3/7)\approx(0.571,\,0.429)$, which you can check from $\pi_1=\frac{1-p_{22}}{(1-p_{11})+(1-p_{22})}=\frac{0.4}{0.7}$.
The gap to $\pi_1$ shrinks by the second eigenvalue $\lambda_2=p_{11}+p_{22}-1=0.3$ at every step: $0.4286\times0.3^t$ gives 0.129 after one step and 0.039 after two, matching the numbers above. Two more useful facts: the average stay in state 1 is $1/(1-p_{11})\approx3.33$ steps, and the expected return time to state 1 is $1/\pi_1=1.75$ steps.
Set both stay-probabilities to 0.95. The path now makes long runs and the Mixing Time tab decays slowly, because $\lambda_2=0.90$. Next set $p_{11}=0.6$ and $p_{22}=0.4$. Now $\lambda_2=0$: every step forgets the past and the chain behaves like independent coin flips with $\pi_1=0.6$. Finally run 2000 steps and compare the empirical frequency of state 1 (the purple card) with the stationary value in the green card.
1. With $p_{11}=0.7$ and $p_{22}=0.6$, find $P(X_2=2\mid X_0=1)$. 2. With $p_{11}=0.9$ and $p_{22}=0.5$, find $\pi_1$ and $\lambda_2$. 3. A chain that switches state with probability 1 at every step never converges to a limit. Which assumption fails?
Answers. 1. $0.7\cdot0.3+0.3\cdot0.6=0.39$. 2. $\pi_1=0.5/(0.1+0.5)=5/6\approx0.833$ and $\lambda_2=0.9+0.5-1=0.4$. 3. Aperiodicity fails: the chain returns to a state only at even times, and $\lambda_2=-1$.
Google's original PageRank is the stationary distribution of a random surfer. Markov chain Monte Carlo (Metropolis-Hastings, Gibbs sampling) builds a chain whose stationary distribution is the posterior you want to sample. Other uses include queueing models, text and speech models where the next symbol depends on the current one, and models of gene or sequence evolution. In all of them the questions are the same ones this page asks: where does the chain settle, and how quickly?