The time spent and the share held

The first rung’s theorem is about a distribution: start anywhere, run the chain, and the probability of being in each state converges. That is a statement about an ensemble of walks, and it says nothing about any one of them.

This rung is about one walk. Run it long enough and the fraction of its time spent in each state converges to that state’s share — the time average equals the space average, which is what ergodic means and is the reason a chain can be used to measure anything.

What the two averages are #

Fix a state $j$ and a walk $X_0, X_1, X_2, \ldots$.

The space average is $\pi_j$: the long-run probability of being at $j$, computed by solving $\pi P = \pi$ or by iterating the matrix. It is a property of the chain.

The time average is the limit of $\frac{1}{n}\#\{k < n : X_k = j\}$: the fraction of the first $n$ steps the walk actually spent at $j$. It is a property of the walk, and it is a random quantity — different walks give different counts.

The theorem says the second converges to the first with probability one, for every starting state and every irreducible chain. A single trajectory sees the whole distribution, and no repetition of the experiment is needed.

Why one walk is enough #

The mechanism is worth having, because it explains the theorem rather than merely asserting it.

Break the walk into excursions: the stretch from the first visit to $j$ until the second, then from the second to the third, and so on. Because the chain forgets its past at each visit to $j$, those excursions are independent and identically distributed — the walk starts afresh from $j$ every time.

So the number of steps in the $m$-th excursion is a sequence of independent draws from one distribution, and the law of large numbers applies: the average excursion length converges to its expectation, which is the expected return time $R_j$.

After $m$ excursions the walk has taken about $mR_j$ steps and visited $j$ exactly $m$ times, so the fraction of time at $j$ is about $m/(mR_j) = 1/R_j$. And the same argument for every state, with the fractions summing to one, forces $1/R_j = \pi_j$.

The ergodic theorem for chains is the law of large numbers applied to excursions, and the only chain-specific ingredient is that returning to a state restarts the process.

The identity, and what it is good for #

The relation that falls out is worth stating on its own:

$$R_j = \frac{1}{\pi_j},$$

the expected number of steps to return to a state is one over its long-run share.

That is a remarkably clean statement and it is exactly computable. The figure solves the hitting-time system for each state — which is the absorbing-chain machinery of the previous rung, applied with the target made absorbing — and checks the answer against $1/\pi_j$ to nine decimal places.

The usefulness is that the two sides are hard in different circumstances. On a big graph the shares are easy when the chain is reversible, since they are degrees; the return times are not obviously anything. The identity hands them over.

The knight on a chessboard returns to a corner in exactly $168$ moves on average, because its share there is $2/336$. Computing that expected time directly would mean solving sixty-four equations; through the identity it is one division.

What the run is doing in the figure #

The bars pair the measured fraction against the computed share, and the point of the pairing is that the first is not evidence for the second.

The shares are exact: they solve a linear system, and the solve is checked against the eigenvector condition. The return times are exact: they solve another linear system, and are checked against the reciprocal identity. Neither number comes from the run.

What the run supplies is a demonstration that the theorem’s subject is a trajectory. A reader who has only seen the first rung’s iterated matrices has seen distributions converge and might reasonably think the shares are a statement about many walks. Sixty thousand steps of one walk landing on the same numbers is the demonstration that they are not.

The generator asserts agreement to within two hundredths on the shares and eight per cent on the return times, which are the tolerances a run of that length earns. A tolerance that a run cannot meet is a broken check, and one it meets trivially checks nothing — these are set where a genuinely wrong transcription would fail.

Doing the smallest case by hand #

The two-state chain is small enough to verify completely, and doing so makes the identity concrete.

Take the chain that moves from $A$ to $B$ with probability $0.4$ and stays otherwise, and from $B$ to $A$ with probability $0.2$. The stationary distribution solves $\pi_A \times 0.4 = \pi_B \times 0.2$, so $\pi_B = 2\pi_A$, giving $\pi_A = 1/3$ and $\pi_B = 2/3$.

Now the return times directly. Starting at $A$, each step returns to $A$ with probability $0.6$ and goes to $B$ with $0.4$; from $B$ the walk comes back to $A$ after a geometrically distributed wait with mean $1/0.2 = 5$. So the expected return to $A$ is $0.6 \times 1 + 0.4 \times (1 + 5) = 0.6 + 2.4 = 3$.

And $1/\pi_A = 3$. The same computation at $B$ gives $0.8 \times 1 + 0.2\times(1 + 2.5) = 0.8 + 0.7 = 1.5$, and $1/\pi_B = 1.5$.

Both sides computed independently, both landing on the same number. That is what the figure does for a three-state chain by solving rather than by hand, and the hand version is worth having once because it shows there is no circularity: the return time was computed from the transition probabilities without ever mentioning $\pi$.

What the theorem does not say #

Three qualifications, and each is a place where a reader might take more than is offered.

It says nothing about how long. The convergence is guaranteed and its speed is not addressed here at all: how many steps a particular chain needs before its time averages are close is a quantitative question with its own literature, and nothing on this page bears on it. Everything here is a limit or an exact solve.

It needs irreducibility. A chain that cannot reach every state from every other has time averages that depend on where it started, which is the same failure the first rung’s reducible chain has.

It does not need aperiodicity. This is the one place the two conditions come apart. A periodic chain — the three-cycle, say — has no limiting distribution, since the probability at each state oscillates forever. But its time averages converge perfectly well, because a third of the steps are spent at each state wherever the walk began in the cycle.

Periodicity, and the split it reveals #

That last point deserves more, because it separates two things the first rung treated as one.

The first rung’s theorem needs both irreducibility and aperiodicity, and its conclusion is that the distribution converges. The theorem here needs only irreducibility, and its conclusion is that time averages converge.

So aperiodicity is a condition about distributions, not about long-run behaviour. A periodic chain is perfectly well behaved in the long run — it visits each state its correct share of the time — and what it fails to do is forget where in the cycle it started.

The distinction matters wherever a chain is being run to measure something. If the quantity of interest is an average over a long run, periodicity is harmless. If it is where the walk is now, periodicity is fatal. The two conditions guard different questions, and conflating them makes aperiodicity look like a technicality when it is a real hypothesis for a real theorem.

Where the theorem’s name comes from #

The word ergodic arrived from statistical mechanics and its history explains why the theorem is stated the way it is.

Boltzmann needed to justify replacing an average over a system’s possible states by an average over one system’s history — because an experiment measures one gas over time and the theory computes an average over configurations. He hypothesised that a single trajectory eventually visits every state, which is where the name comes from, and the hypothesis in that strong form is false for essentially every real system.

What is true, and what the twentieth century established, is the weaker statement here: the time average of a function along one trajectory equals its space average, without the trajectory needing to visit everything. Birkhoff proved the general version in 1931 and von Neumann proved a version in a different sense the year before.

For finite Markov chains the theorem is much easier than the general case, because the excursion argument is available and the law of large numbers does the work. The general ergodic theorem needs no independence anywhere, which is why it is hard; the chain case manufactures independence by cutting at returns, and that is the whole difference.

The name has stuck to a family of theorems that all say the same thing about different objects, and the family is one of the more useful pieces of vocabulary in the subject: an ergodic system is one about which a single long observation is enough.

Averaging a function rather than counting visits #

The theorem generalises immediately and the general form is the one that gets used.

Let $f$ be any function on the states. Then the running average $\frac1n\sum_{k<n} f(X_k)$ converges to $\sum_j \pi_j f(j)$ — the expectation of $f$ under the stationary distribution.

Counting visits to $j$ is the special case where $f$ is the indicator of $j$, and the general case follows by linearity from the special one. So a chain can estimate the average of any function over its stationary distribution by running once and averaging.

That is exactly what makes constructed chains useful. Build a chain whose stationary distribution is the one wanted — which detailed balance makes constructible — run it, and average the function along the way. The ergodic theorem is the guarantee that the running average converges to the right thing, and everything else about the method is a question of how long to run.

Return times sum to something fixed #

One more identity, less famous and worth knowing, because it is a check on any computation of return times.

Since $\sum_j \pi_j = 1$ and $\pi_j = 1/R_j$, the return times satisfy $\sum_j 1/R_j = 1$. So the reciprocals of the expected return times add to one, over the states of any irreducible finite chain.

For the three-state chain in the figure the return times are $3.583$, $2.867$ and $2.687$, and their reciprocals are the three shares $0.2791$, $0.3488$ and $0.3721$ — which add to one because they are a distribution. The generator checks each reciprocal against its share to nine places, so the sum is a consequence rather than a separate claim.

A state visited rarely has a long return time and a state visited often a short one, and the trade is exact. There is no chain in which every state is rare, which sounds obvious and is worth having as an equation: making one return time longer makes another shorter, and the constraint is on the reciprocals rather than on the times themselves.

What a long run costs, and what it does not buy #

The theorem guarantees convergence and says nothing about error, and it is worth being clear about which of those a longer run addresses.

The error in a time average over $n$ steps behaves like $C/\sqrt{n}$, with the constant depending on the chain — the same square-root law that governs the wobble around any average, with a constant inflated by the correlation between successive steps. So four times the run halves the error, exactly as for independent samples, and the only difference is the constant.

That constant is where all the chain-specific difficulty lives, and it is a quantity this collection does not compute. What it depends on is how quickly the chain decorrelates, which is a question about the spectrum, and answering it belongs to a subject with its own methods and its own name.

What is worth carrying is the shape. Convergence is qualitative and free; the rate is quantitative and expensive. The ergodic theorem hands over the first and is silent about the second, and a practitioner reading it as a guarantee about a run of a particular length has read more than it says.

The figure’s sixty thousand steps land the shares within about a hundredth of the true values, which is what a run of that length against this constant produces. Nothing in the theorem predicted the hundredth.

Two states, three answers, one number #

A last observation that is easy to state and easy to get wrong, since it looks like a paradox and is not.

The identity says a state’s expected return time is one over its share. It says nothing about the expected time to reach that state from elsewhere, which is a different quantity and is generally larger — sometimes much larger.

On the three-state chain in the figure, the expected return to $A$ is $3.583$; the expected time to reach $A$ starting from $C$ is a different number, solved by the absorbing-chain system with $A$ made absorbing. The return time averages over where the first step lands, weighted by the chain’s own transition probabilities; the hitting time from $C$ fixes the start.

Return time is a weighted average of one-plus-hitting-times, and the weights are the state’s own outgoing probabilities. That is the relation between the two, and it is why the return time can be short while some hitting time is long: the walk usually comes back the easy way.

The mistake worth avoiding is reading $1/\pi_j$ as how long until the walk first reaches $j$. It is how long until the walk sees $j$ again having just been there, which is a question with a different answer.

What the pictures cannot show #

The run is one run. Sixty thousand steps of one seeded walk produce the numbers in the bars, and a different seed produces slightly different ones. The theorem is about the limit, and no finite run reaches it.

The excursion argument is not drawn. The proof breaks the walk at its visits to a state and applies the law of large numbers to the pieces; the figure shows only the totals, and the independence that makes the argument work is a property of the chain rather than of the counts.

And the exact answers dominate the picture without appearing in it. Both columns of the table are solutions of linear systems, and what a reader sees is four decimal places. The elimination behind them is in the generator, checked twice.

Where the ladder goes next #

Everything on this rung assumed finitely many states, and the assumption was doing more work than it looks. On infinitely many states a chain can be irreducible and aperiodic and still have no stationary distribution at all, and the return times can be infinite while returns remain certain. The last rung is about the three things that can then happen.

Sideways: the law of large numbers is what the excursion argument applies, and the absorbing chain is where the hitting-time systems come from.

What is worth carrying away #

An average over an ensemble and an average over time are different quantities, and a theorem saying they agree is doing real work.

Nothing in the definition of a chain says that one long walk resembles the distribution its matrix converges to. It happens because a return to a state restarts the process, which makes the excursions independent, which lets the law of large numbers apply — three steps, none of them free.

Where the two averages agree, one experiment replaces many, and that equivalence is what every method built on running a chain is standing on. Where they do not agree — a chain that is not irreducible, or one on infinitely many states with nothing to settle into — running longer does not help, and knowing which case is which is the whole of the practical question.

The second habit worth taking is the reciprocal identity itself, as a template rather than as a fact about chains. A rate and a waiting time are reciprocal whenever the events are the returns of a process to a state, and the identity converts between them for free. It is the reason a quantity that is easy to compute one way — a degree, a share, a frequency — silently answers a question posed the other way, about how long something takes.