Markov Chains: The Future Depends Only on Now

A process that forgets its own history

Most sequences of events depend on their whole past. A Markov chain is the special, tractable case where they don't: the probability of the next state depends only on the current state, never on how the process arrived there. Formally, a sequence of random variables X₀, X₁, X₂, … over a state space S has the Markov property when

P(X_(n+1)=j | X_n=i, X_(n-1)=i_(n-1), ..., X_0=i_0) = P(X_(n+1)=j | X_n=i)

// everything the past could tell you about the future
// is already summarised by the current state i

This single "memoryless" assumption is what makes an enormous range of real systems mathematically tractable — weather sequences, board games, chemical reactions, web browsing, and the sampling algorithms that power modern Bayesian statistics.

The transition matrix

All the one-step probabilities are collected into a transition matrix P, where entry P[i][j] is the probability of moving from state i to state j, and every row sums to 1. A two-state weather toy example makes the idea concrete:

states: {Sunny, Rainy}
P = | 0.8  0.2 |     // row "Sunny": stay sunny 80%, turn rainy 20%
    | 0.4  0.6 |     // row "Rainy": turn sunny 40%, stay rainy 60%

distribution after n steps:  π_n = π_0 · P^n

States can be classified by their long-run behaviour: recurrent states are guaranteed to be revisited infinitely often, transient states may never be seen again after some point, and absorbing states — once entered — are never left (P[i][i] = 1). A chain is irreducible if every state can reach every other state, and aperiodic if it isn't locked into visiting states on a fixed cycle length. Both properties together guarantee something powerful: a unique long-run distribution.

Stationary distributions and how fast they're reached

A distribution π* is stationary if applying one more transition leaves it unchanged: π* = π* · P. The Perron-Frobenius theorem guarantees that an irreducible, aperiodic stochastic matrix has a unique such π*, reachable from any starting distribution. For the weather example, solving the balance equations gives π*[Sunny] = 0.4/(0.2+0.4) = 2/3 and π*[Rainy] = 1/3 — regardless of whether the chain started on a sunny or rainy day.

For larger state spaces, solving the balance equations by hand is impractical, so the standard tool is power iteration: start from any distribution and repeatedly multiply by P until it stops changing. How quickly it stops changing is the chain's mixing time, governed by the spectral gap — the distance between the largest eigenvalue (always 1) and the second-largest. A chain with near-absorbing states or bottleneck transitions mixes slowly; a well-connected chain mixes fast.

PageRank: a random surfer as a Markov chain

Google's original PageRank algorithm is a Markov chain in disguise: imagine a "random surfer" who, from any web page, clicks a uniformly random outgoing link. The web's link graph defines a transition matrix, and each page's rank is simply its probability mass in the chain's stationary distribution — pages that many well-connected pages link to accumulate more of that probability. Two practical fixes make the model work on the real web: dangling pages with no outgoing links redistribute their probability uniformly rather than trapping the surfer, and a damping factor d (typically 0.85) has the surfer occasionally teleport to a uniformly random page instead of clicking a link:

G = d · P + (1 − d)/n · 1·1ᵀ        // the "Google matrix"
PageRank = stationary distribution of G

// G is irreducible & aperiodic no matter what the link graph looks like,
// so ~50-100 rounds of power iteration reliably converge on real web scale

Random walks and the gambler's ruin

The simplest Markov chain of all is a 1D random walk: move +1 with probability p, −1 with probability q = 1 − p. When p = q = 0.5 the walk is recurrent — it returns to its starting point with probability 1 — but as soon as p ≠ q it drifts off to +∞ or −∞ and becomes transient. This is the mathematics behind gambler's ruin: a player with £k plays repeatedly against a casino with effectively infinite funds, winning £1 with probability p, until reaching a target £N or going bankrupt. The ruin probability has a closed form, and it degrades sharply the moment p drops even slightly below 0.5 — precisely why every casino game is engineered with p < 0.5. A remarkable related fact, Pólya's theorem, says a symmetric random walk is recurrent in one and two dimensions but transient in three or more: the proverbial drunk always finds their way home, the drunk bird flying in 3D generally does not.

How the simulation here uses it

The simulation on this site lets you edit a small transition matrix directly and watch probability mass flow between states step by step, converging visually toward the stationary distribution predicted by the theory above. Because the chain redraws every transition on-screen, you can watch mixing time happen rather than just compute it: a well-connected graph settles in a handful of steps, while a graph with a narrow bottleneck between two clusters of states visibly takes far longer to equalise — the spectral gap made tangible.

Frequently asked questions

Try it live

Everything above runs in your browser — open Markov Chains and edit the transition probabilities to watch the distribution converge. Nothing is installed, nothing is uploaded, the whole model lives in one tab.