Probability and statistics

Stochastic processes and Markov chains

Sequences of random states evolving over time, where Markov chains depend only on the current state.

IntuitionIf tomorrow only cares about today, how far can you predict the future?

Picture a frog hopping between lily pads on a pond, or a board-game piece moving square by square, or tomorrow's weather switching between sunny and rainy. In each case there is a state (which pad, which square, which weather) that changes at each tick of a clock, and the change is not fixed in advance — it is random. A stochastic process is simply a family of random variables $X_n \in S$ indexed by time $n=0,1,2,\dots$ , one random state for every moment. The frog's hop, and a huge number of real systems — gene mutations, customers arriving at a queue, prices ticking on an exchange, a web surfer clicking links — are all stochastic processes in this sense. A Markov chain is the special, enormously useful case where the frog is forgetful: the probability of the next hop depends only on the lily pad it is currently sitting on, never on the winding path that got it there.

A directed state diagram: each node is a state and each labeled arrow is a transition probability. Cycle through the highlighted node to see how, from any current state, the arrows out of it are the only thing that decides where the chain goes next — nothing further back in the path matters.

UndergraduateThe Markov property, transition matrices, and stationary distributions

Definition: Markov chain

Let $S$ be a countable set of states and let $X_n \in S$ for $n=0,1,2,\dots$ be a stochastic process taking values in $S$ . The process is a Markov chain if it has the Markov property: $P(X_{n+1}\mid X_n,\dots,X_0)=P(X_{n+1}\mid X_n)$ for every choice of states and every $n$ . In words, the whole past $X_0,\dots,X_{n-1}$ gives no extra information about $X_{n+1}$ once $X_n$ is known — the present state is a sufficient summary of the entire history.

P(X_{n+1}\mid X_n,\dots,X_0)=P(X_{n+1}\mid X_n)

When the state space is finite (or countable) and the chain is time-homogeneous, all this randomness is captured by a single transition matrix $P$ with entries $P_{ij}=P(X_{n+1}=j\mid X_n=i)$ — the probability of jumping to state $j$ given the chain is currently at $i$ . Because from any state the chain must go somewhere, every row of $P$ is a probability distribution: it is non-negative and sums to one, $\sum_{j\in S} P_{ij}=1$ . A matrix with this row-sum-one property is called row-stochastic. Multiplying $n$ -step and $m$ -step transitions composes exactly as matrix multiplication, the Chapman–Kolmogorov equation $P^{(n+m)}=P^{(n)}P^{(m)}$ , so the probability of being in each state after $n$ steps starting from a distribution $\mu_0$ is simply $\mu_0 P^n$ .

P_{ij}=P(X_{n+1}=j\mid X_n=i)

A probability distribution $\pi$ on $S$ is stationary if it is a fixed point of this dynamics: $\pi P=\pi$ together with $\sum_{i\in S}\pi_i=1$ and $\pi_i\ge0$ . Once the chain's distribution equals $\pi$ at one time step, it equals $\pi$ at every later time step — the population of frogs on each pad stops changing in aggregate, even though each individual frog keeps hopping randomly. Finding $\pi$ reduces to solving a linear system, which is exactly what the fundamental theorem below turns into a guarantee of existence, uniqueness, and convergence.

\pi P=\pi

Key properties that classify a Markov chain
Property	Definition	Consequence
Irreducible	Every state can reach every other state with positive probability	The chain has (at most) one stationary distribution
Aperiodic	The greatest common divisor of possible return times to a state is 1	Powers $P^n$ converge entrywise, not just on average
Recurrent	Starting from state $i$ , the chain returns to $i$ with probability 1	On a finite irreducible chain this always holds automatically

Theorem: Fundamental theorem of finite Markov chains

If a Markov chain on a finite state space $S$ is irreducible and aperiodic, then there exists a unique stationary distribution $\pi$ with $\pi P=\pi$ , $\pi_i>0$ for every state, and $\lim_{n\to\infty}P^n=\mathbf 1\,\pi$ — every row of $P^n$ converges to $\pi$ as $n\to\infty$ , regardless of the starting distribution.

Why is it true?

This is the reason Markov chains are useful at all: it says the long-run behavior of a randomly evolving system settles into a single predictable pattern that forgets its starting point, and it tells us exactly what that pattern is (the unique fixed point of the transition dynamics).

Proof

Existence and uniqueness. Since $P$ is row-stochastic, the all-ones vector is a right eigenvector with eigenvalue 1, so 1 is also an eigenvalue of $P$ (a matrix and its transpose share eigenvalues), and there is a corresponding left eigenvector $\pi$ with $\pi P=\pi$ . Irreducibility means $P$ is the transition matrix of a strongly connected graph, so the Perron–Frobenius theorem applies: the eigenvalue 1 is simple (multiplicity one) and its eigenvector can be chosen strictly positive, giving uniqueness after normalizing so entries sum to 1.

Convergence. Aperiodicity plus irreducibility means all other eigenvalues $\lambda$ of $P$ satisfy $|\lambda|<1$ (this is the part periodicity would break: a periodic chain has extra eigenvalues exactly on the unit circle, such as $-1$ , which never die out). Writing an arbitrary starting distribution $\mu_0$ in the eigenbasis of $P$ , the component along $\pi$ (eigenvalue 1) survives unchanged forever, while every other component is multiplied by $\lambda^n$ at step $n$ and shrinks geometrically to zero.

Combining the two steps, $\mu_0 P^n$ converges to the eigenvalue-1 component alone, which is exactly $\pi$ , and since this holds for every starting distribution $\mu_0$ (including each point mass, i.e. each row of the identity), every row of $P^n$ converges to $\pi$ as claimed.

Theorem: PageRank as the stationary distribution of a random surfer

Let $J$ be the $N\times N$ all-ones matrix ( $N$ = number of web pages) and let $P$ be the row-stochastic link matrix (page $i$ links equally to each page it points to; pages with no outlink are sent uniformly to all pages). For any damping factor $d\in(0,1)$ , the Google matrix $G=dP+(1-d)\tfrac1N J$ is the transition matrix of an irreducible, aperiodic Markov chain, so by the fundamental theorem above it has a unique stationary distribution $\pi$ with $\pi=\pi\Big(dP+(1-d)\tfrac1N J\Big)$ — this $\pi$ is exactly the PageRank vector, and the power-iteration algorithm $\pi_{k+1}=\pi_k G$ converges to it from any starting guess.

Why is it true?

This turns the vague idea "important pages are linked to by other important pages" into a well-posed fixed-point problem with a guaranteed unique solution, and it explains why simply repeating "spread rank along links" (power iteration) is guaranteed to work rather than oscillate or diverge.

Proof

Irreducibility. Because $1-d>0$ , every entry of $G$ is strictly positive ( $G_{ij}\ge(1-d)/N>0$ ), so from any page there is a positive-probability direct jump to any other page in one step — the underlying graph is trivially strongly connected, hence $G$ is irreducible.

Aperiodicity. A chain where every state can go directly to every state (including itself, since $G_{ii}>0$ too) has return times of every length $1,2,3,\dots$ available, whose greatest common divisor is 1; so $G$ is aperiodic.

Existence, uniqueness, convergence. $G$ is row-stochastic by construction (a convex combination $dP+(1-d)\tfrac1N J$ of two row-stochastic matrices $P$ and $J/N$ is row-stochastic), and it is irreducible and aperiodic as just shown, so the fundamental theorem of finite Markov chains applies directly: a unique stationary $\pi$ exists with $\pi=\pi\Big(dP+(1-d)\tfrac1N J\Big)$ , and $G^n$ converges entrywise to a matrix with every row equal to $\pi$ .

Power iteration. Since $\pi_k=\pi_0G^k$ for any starting distribution $\pi_0$ , and every row of $G^k$ converges to $\pi$ as $k\to\infty$ , the weighted average $\pi_0G^k$ converges to $\pi$ as well — this is precisely why repeatedly applying $\pi_{k+1}=\pi_k G$ from an arbitrary starting rank (commonly the uniform distribution) converges to the true PageRank vector.

UndergraduateReal-World Applications and Worked Examples

Markov chains model an enormous range of systems where "forgetting the past given the present" is a reasonable approximation. Google's original PageRank algorithm ranks web pages by the stationary distribution of a random surfer who clicks links (proved above). In biology, DNA sequences and protein folding pathways are modeled as Markov chains over nucleotides or conformations. In finance and operations research, queueing systems (customers waiting at a checkout) and inventory levels are tracked as Markov chains to compute long-run waiting times and stock-out probabilities. In speech recognition and natural-language processing, hidden Markov models chain together phonemes or part-of-speech tags. And in computer science, MCMC (Markov chain Monte Carlo) algorithms build a Markov chain whose stationary distribution is a hard-to-sample target distribution, then simulate it to draw approximate samples.

Example: Stationary weather distribution

A simplified weather model has two states, Sunny and Rainy, with transition matrix $P=\begin{pmatrix}0.9&0.1\\0.5&0.5\end{pmatrix}$ (row 1 = from Sunny, row 2 = from Rainy; so from Sunny it stays Sunny with probability $0.9$ and becomes Rainy with probability $0.1$ ). Find the stationary distribution $\pi=(\pi_1,\pi_2)$ .

Solution

The stationary equations are $\pi P=\pi$ , i.e. $0.9\pi_1+0.5\pi_2=\pi_1$ and $0.1\pi_1+0.5\pi_2=\pi_2$ , together with $\pi_1+\pi_2=1$ .

The first equation simplifies to $0.5\pi_2=0.1\pi_1$ , i.e. $\pi_2=0.2\pi_1$ (the second equation gives the same relation, as it must since the rows of $\pi P-\pi$ are dependent).

Substituting into the normalization: $\pi_1+0.2\pi_1=1$ , so $1.2\pi_1=1$ and $\pi_1=5/6$ , $\pi_2=1/6$ .

So $\pi=(5/6,\,1/6)$ — in the long run this weather chain is Sunny $5/6$ of the time. This matches intuition: state 1 (Sunny) is much "stickier" (probability $0.9$ of staying) than state 2 (Rainy, probability $0.5$ of staying), so the chain spends most of its time in the sticky state.

Example: PageRank of a three-page web

A tiny web has three pages $A,B,C$ : page $A$ links equally to $B$ and $C$ , page $B$ links only to $C$ , and page $C$ links only back to $A$ : $P(A\to B)=P(A\to C)=\tfrac12,\quad P(B\to C)=1,\quad P(C\to A)=1$ . Model a random surfer's clicks as a Markov chain on $\{A,B,C\}$ and find the PageRank vector $\pi$ .

Solution

First check the chain is irreducible and aperiodic: every page can reach every other page (via $A\to B\to C\to A$ ), and there are cycles of length 2 ( $A\to C\to A$ ) and length 3 ( $A\to B\to C\to A$ ), whose gcd is 1, so the fundamental theorem guarantees a unique stationary $\pi$ .

Write the balance equations column by column: $\pi_A$ only receives flow from $C$ , $\pi_B$ only from $A$ , and $\pi_C$ from both $A$ and $B$ : $\pi_A=\pi_C,\quad \pi_B=\tfrac12\pi_A,\quad \pi_C=\tfrac12\pi_A+\pi_B$ .

The first two equations give $\pi_A=\pi_C$ and $\pi_B=\tfrac12\pi_A$ directly; substituting into the normalization $\pi_A+\pi_B+\pi_C=1$ gives $\pi_A+\tfrac12\pi_A+\pi_A=1$ , i.e. $\tfrac52\pi_A=1$ .

Solving, $\pi_A=2/5$ , hence $\pi=(\pi_A,\pi_B,\pi_C)=(2/5,\,1/5,\,2/5)$ . Page $A$ and page $C$ tie for the highest rank because each receives a link from a page that itself only has one outlink to send all its weight through — exactly the kind of "vote concentration" PageRank is designed to reward.

Research frontier as of 2026

Markov chains remain a live research area far beyond their classical use. Markov chain Monte Carlo (MCMC) is the computational backbone of Bayesian statistics and statistical physics, and a central open problem is bounding mixing times — how many steps a chain needs before it is close to its stationary distribution — for chains arising from realistic high-dimensional models; spectral gap and coupling techniques give sharp answers for some chains (card shuffling, random walks on groups) but remain difficult for many chains used in practice, such as those sampling from complex Bayesian posteriors or Ising-model-like distributions near a phase transition. Markov Decision Processes, which add controllable actions to a Markov chain, underlie modern reinforcement learning; understanding the sample complexity and convergence guarantees of RL algorithms operating on enormous or continuous state spaces is an active area connecting probability theory, optimization, and machine learning. On the applied side, more refined random-surfer and diffusion models continue to be developed for ranking and recommendation systems well beyond the original PageRank formulation.

The Markov property says that, given the present state $X_n$ , the next state $X_{n+1}$ is:

A 3-state chain has transition matrix rows that must each:

For the transition matrix $P=\begin{pmatrix}0.9&0.1\\0.5&0.5\end{pmatrix}$ , which vector $\pi$ satisfies $\pi P=\pi$ and $\sum_{i\in S}\pi_i=1$ ?

In Google's original PageRank, the damping factor $d<1$ (mixing in a uniform $1/N$ jump to every page) is essential mainly because it guarantees the Google matrix is:

References

David A. Levin, Yuval Peres, Elizabeth L. Wilmer (2017). Markov Chains and Mixing Times
Sergey Brin, Lawrence Page (1998). The Anatomy of a Large-Scale Hypertextual Web Search Engine
James R. Norris (1997). Markov Chains