What does a Markov chain's stationary distribution tell you about a random surfer's long-run page visits?

## Definition A distribution `pi` over the states of a chain with transition matrix `P` is **stationary** when applying one step of the chain leaves it unchanged: ``` pi = pi P i.e. pi_j = sum over i of pi_i * P[i][j] for every j ``` together with the constraints that keep it a distribution: `pi_j >= 0` and `sum of pi_j = 1`. Read the equation as a balance condition: the probability mass flowing *into* state `j` in one step equals the mass sitting *in* `j`. Nothing is being created or drained anywhere, so the picture is in equilibrium even though individual walkers keep moving. ## Solving for it Rewrite `pi = pi P` as `pi (P - I) = 0`. Because every row of `P` sums to 1, the columns of `P - I` are linearly dependent, so this system never has full rank — the solutions form a line through the origin, and any scalar multiple of a solution is also a solution. That is why the normalisation is not optional: you discard one of the redundant equations and replace it with `sum of pi = 1` to pick the single probability vector on that line. Worked two-state example — a weather chain on `[sunny, rainy]` with ``` P = [ 0.8 0.2 ] [ 0.4 0.6 ] ``` The sunny balance equation is `pi_s = 0.8 pi_s + 0.4 pi_r`. Substituting `pi_r = 1 - pi_s` gives `pi_s = 0.4 pi_s + 0.4`, hence `0.6 pi_s = 0.4` and `pi_s = 2/3`, `pi_r = 1/3`. Check with the other equation: `pi_r = 0.2 pi_s + 0.6 pi_r` gives `0.4 pi_r = 0.2 pi_s`, so `pi_r = pi_s / 2`, which holds. Two-thirds of days are sunny in the long run regardless of today's weather. ## What it means for a random surfer Model web navigation as a chain: each page is a state, and from a page the surfer picks one of its outgoing links uniformly at random. Then `pi_j` is the **long-run fraction of steps spent on page `j`**. This is the ergodic reading of stationarity, and it is the one that makes the vector useful as a ranking: a page inherits importance from the pages that link to it, weighted by how often those pages are themselves visited. A page with one inbound link from a heavily-trafficked hub can outrank a page with fifty links from obscure corners. Two companion facts worth having ready: - **Expected return time.** For an irreducible chain, the mean number of steps to come back to page `j` after leaving it is `1 / pi_j`. A page holding 5% of the long-run traffic is revisited on average every 20 steps. - **Invariance.** If the surfer's starting page is drawn from `pi` itself, then the distribution over pages is `pi` at every subsequent step. Stationarity is a property of the *distribution*, not of any individual walk — the surfer keeps moving. ## Existence and uniqueness For a **finite** chain, a stationary distribution always exists. It is **unique** when the chain is irreducible — every state reachable from every other. Uniqueness is not the same as convergence: an irreducible chain can be periodic, in which case `pi` still exists and still equals the long-run fraction of time in each state, but the step-by-step distribution never settles onto it. If the chain is reducible, with two or more closed groups of states that cannot reach each other, each group carries its own stationary distribution and every mixture of them is stationary too — so 'the' stationary distribution is not well defined, and where you start decides the answer. ## A useful shortcut: reversibility If you can find a distribution satisfying **detailed balance**, `pi_i P[i][j] = pi_j P[j][i]` for every pair of states, then that `pi` is automatically stationary — sum both sides over `i` and the global balance equation drops out. This pairwise condition is often far easier to verify than solving the full system, and it holds for many symmetric or random-walk-style chains. It is sufficient, not necessary: plenty of chains have a stationary distribution without being reversible. ## Interview traps Three wrong answers recur. First, that `pi` depends on the starting state — for an irreducible chain it does not. Second, that stationary means uniform — a stationary distribution is generally far from uniform, and it is uniform only in special cases such as a chain whose columns also sum to 1. Third, forgetting the normalisation and reporting an unnormalised solution vector as if it were a distribution.