Where the shares have nowhere to go

The first rung’s theorem had two conditions and both were about the diagram: every state reachable from every other, and no length of walk forced. On finitely many states those two are enough. On infinitely many they are not, and what goes wrong is worth the whole rung.

Take the whole numbers $0, 1, 2, \ldots$ and a walk that steps up with probability $p$ and down with $1-p$, bouncing at zero. It can reach every state from every other and it is not periodic, at every $p$. And three completely different things happen.

The weights, and why they are geometric #

Detailed balance decides the shape immediately, which is the previous rung but one doing useful work.

The chain moves only between neighbours, so its graph is a path, which has no cycles, so the chain is reversible. Balance across the edge between $i$ and $i+1$ reads $\pi_i p = \pi_{i+1}(1-p)$, giving

$$\pi_{i+1} = \pi_i \cdot \frac{p}{1-p}.$$

Write $r = p/(1-p)$. Then the weights are $1, r, r^2, r^3, \ldots$, and the whole question is whether that geometric series converges.

A stationary distribution exists exactly when the weights can be normalised, which needs $\sum r^i$ finite, which needs $r < 1$, which needs $p < \tfrac12$. Below a half the chain has shares; at a half or above it does not.

Three regimes #

Below a half. The weights sum to $1/(1-r)$ and the shares are $\pi_i = (1-r)r^i$ — a geometric distribution. The chain is positive recurrent: it returns to every state with certainty and in finite expected time, which is $1/\pi_i$ by the previous rung’s identity. Everything from the finite theory applies.

Above a half. The weights climb and there is nothing to normalise. Worse, the walk leaves: starting from $1$, the probability of ever reaching $0$ is exactly $(1-p)/p < 1$, so with positive probability the walk never comes back. The chain is transient, and the figure computes that probability and checks it against the equation defining it.

Exactly a half. The weights are all one and their sum diverges, so there is no stationary distribution — and yet the walk returns to every state with probability one. The chain is null recurrent: certain to come back, with infinite expected time to do so.

That middle case is the one finiteness was hiding.

Certain but not soon #

Returns with probability one and returns in finite expected time are the same statement on a finite chain and different statements here, and the difference deserves its own paragraph.

On a finite irreducible chain every state is visited infinitely often, and the expected gap between visits is $1/\pi_i$, which is finite because $\pi_i$ is positive. There is no room for a gap to have infinite expectation.

At $p = \tfrac12$ on the whole numbers, the walk starting at $1$ hits $0$ with probability one — this is the classical result about the fair walk on a line — and the expected time to do so is infinite. The reason is that the distribution of the return time has a heavy tail: the chance of taking more than $n$ steps decays like $1/\sqrt{n}$, and a tail that heavy has no mean.

Probability one and infinite expectation are compatible, which is the single most useful thing to take from this rung. An event can be certain and still have an average waiting time that does not exist.

The escape probability, derived #

The transient case’s number is worth deriving, because it is the one quantity here that is not simply a series test.

Let $h_i$ be the probability of ever reaching $0$ starting from $i$. Conditioning on the first step gives $h_i = p\,h_{i+1} + (1-p)h_{i-1}$ for $i \geq 1$, with $h_0 = 1$. That is a linear recurrence with characteristic equation $p x^2 - x + (1-p) = 0$, whose roots are $1$ and $(1-p)/p$.

So $h_i = A + B\left(\frac{1-p}{p}\right)^i$. The condition $h_0 = 1$ gives $A + B = 1$, and the requirement that $h$ be a probability — between nought and one — forces $A = 0$ when $p > \tfrac12$, since otherwise the second term vanishes as $i$ grows and $h$ tends to $A$, and any $A > 0$ would make $h$ exceed one somewhere below.

That leaves $h_i = ((1-p)/p)^i$, and in particular $h_1 = (1-p)/p$. At $p = 0.62$ that is $0.38/0.62 = 0.613$, so the walk escapes from $1$ with probability $0.387$ — which is the figure’s number, computed by the generator from the recurrence rather than from the formula.

The escape probability is the minimal non-negative solution of the recurrence, and that phrase is doing the work: the recurrence has a whole family of solutions and only one of them is a probability. Picking the right one is where the argument’s content is, and it is the step most treatments skip.

Where the walk’s own ladder meets this one #

The site already has the critical case in another language, and the two accounts are worth putting side by side.

A walk that comes home is about the simple symmetric walk on the integer lattice, and its headline is Polya’s theorem: the walk returns with certainty in one and two dimensions and not in three. That is the same distinction as recurrence against transience, and the dimensional threshold is the same kind of critical point as $p = \tfrac12$ here.

What the walk essay does not say, because it is not what that ladder is about, is that the one-dimensional walk is null recurrent. It comes home certainly and the expected time is infinite, so there is no stationary distribution on the integers and no share to compute.

Two ladders, two critical points, one phenomenon. Here the parameter is the step-up chance and the critical value is a half; there it is the dimension and the critical value is between two and three. In both cases the interesting behaviour is exactly at the boundary, and in both cases the boundary case is the one that is certain and slow.

What the finite theory was using #

Looking back, it is worth naming what finiteness supplied, since it was never stated as a hypothesis.

A finite irreducible chain has a stationary distribution because the transition matrix has $1$ as an eigenvalue with a positive eigenvector, which is Perron–Frobenius, and Perron–Frobenius is a theorem about finite matrices. There is no infinite version that holds without extra conditions.

Equivalently: the shares must sum to one, and on finitely many states a positive vector can always be scaled to do so. On infinitely many it cannot, and the whole difference is that a positive sequence need not have a finite sum.

So finite was doing exactly one thing, and it was doing it silently. The condition that replaces it is that the weights be summable, and that is a condition on the numbers rather than on the diagram — which is why no amount of staring at the graph reveals which regime a chain is in.

Why the critical case has a heavy tail #

The null recurrent case’s infinite expectation is worth explaining rather than asserting, since it is the least intuitive claim on the page.

For the fair walk, the probability that a return to $0$ takes exactly $2n$ steps is a Catalan-type quantity that behaves like $n^{-3/2}$ for large $n$. So the probability of taking more than $n$ steps behaves like $n^{-1/2}$, and the expected time is a sum of terms behaving like $n \cdot n^{-3/2} = n^{-1/2}$, which diverges.

The reason the tail is that heavy has a picture. A walk that has wandered out to distance $d$ takes about $d^2$ steps to come back, by the square-root law of displacement, and the probability of wandering to distance $d$ before returning is about $1/d$. So the contribution to the expectation from excursions reaching $d$ is about $d^2 \times 1/d = d$, which grows without bound as $d$ does.

The expectation is infinite because the rare long excursions are long enough to matter more than they are rare. That is the general shape of a heavy tail, and the fair walk is the cleanest example of it in the collection.

The practical consequence is that a simulation of the fair walk’s return time produces sample means that grow with the length of the simulation and never settle. A reader who runs it and averages will get a number, and the number is a property of the run.

Detecting the regime from the graph #

That said, there is a criterion, and it is worth having because it generalises past this family.

For a birth-and-death chain with step-up chances $p_i$ varying by state, define the products $\rho_k = \prod_{i<k} p_i/(1-p_{i+1})$. Then the chain is transient exactly when $\sum 1/\rho_k$ converges, recurrent otherwise, and positive recurrent exactly when $\sum \rho_k$ converges as well.

Two convergent-series questions, and between them they settle all three regimes. For the constant-$p$ chain both series are geometric and the answers come out as above.

The interesting cases are the ones where $p_i$ approaches a half. Taking $p_i = \tfrac12 - c/i$ gives a chain that is positive recurrent for $c > \tfrac14$ and null recurrent below it — so a vanishing drift can still be enough to produce a stationary distribution, and the threshold is at a particular constant. The critical behaviour is not a knife edge at $p = \tfrac12$ but a whole family of borderline cases, and which side a given one falls on is a question about the rate at which the drift vanishes.

What the three regimes look like from inside #

A reader watching a long run would see three quite different things, and it is worth saying what they are.

Positive recurrent: the walk stays near zero, wandering up occasionally and coming back, with the fraction of time at each state settling on the geometric shares. A histogram of the visited states converges.

Null recurrent: the walk wanders further and further, returning to every state infinitely often but spending an ever-larger fraction of its time at ever-larger states. A histogram over the first $n$ steps spreads out as $n$ grows and never converges — every state’s share tends to zero.

Transient: the walk goes up and stays up. Every state is visited finitely many times, so a histogram over the first $n$ steps has its mass drift off to the right and away.

The middle case is the one that is hardest to recognise from data, because the histogram keeps changing shape and there is no way to tell from a finite run whether it will settle. That is a genuine practical difficulty and not merely a theoretical curiosity.

Narrowing the spread is worth doing once, because it shows the classification is not a matter of degree. A chain at $p = 0.499$ is positive recurrent and one at $p = 0.5$ is not, and no amount of looking at either picture reveals which side of the line it sits on. The regime is decided by a strict inequality, and strict inequalities are invisible in drawings.

The stationary distribution that is not a limit #

One more subtlety, since the positive recurrent case is not quite as tidy as it looks.

Even below a half, the stationary distribution is a limit of the chain’s distributions only if the chain is aperiodic — and the bouncing walk as defined here is aperiodic because it can stay at zero. A walk that must move at every step, up or down, has period two, and its distribution oscillates forever between the even and odd states.

Its time averages still converge, by the previous rung’s theorem, and the geometric shares are still the answer to that question. So even in the good regime the two theorems come apart, and the one that survives periodicity is the one about a single trajectory.

That is worth carrying because the periodic version is the more natural model. A walk that stays put is a modelling convenience introduced to make the theorems easier, and it is worth knowing which theorems it was introduced for.

The same trichotomy, elsewhere #

The three-way split is not a peculiarity of this family, and it is worth naming a few places it recurs, because recognising it saves rederiving it.

A branching process — each individual has a random number of children, independently, which is the same first-step decomposition applied to a family tree — dies out with probability one when the mean number of children is at most one, and survives with positive probability above one. The critical case, mean exactly one, dies out with certainty and has infinite expected time to do so. Same three regimes, same critical value, same heavy tail at the boundary.

A queue with arrivals and departures is stable when the arrival rate is below the service rate, unstable above, and at exactly equal rates the queue length returns to zero with certainty while its expected excursion is infinite. That is this chain with different names on the states.

The moment a random graph joins up has the same structure again: below the threshold the components are small, above it one is enormous, and at the threshold the largest component is of an intermediate size that is neither.

The pattern is that a critical point behaves like neither of the phases it separates, and the recurring signature is a quantity that is finite on one side, infinite on the other, and infinite-with-certainty at the boundary.

Recognising that shape is worth something practical. A model with a tunable parameter and two obviously different behaviours almost always has a third at the boundary, and the boundary case is usually the one the modelling actually lands on — because a system that has been tuned by anything at all tends to be tuned to its own critical point. The three panels of the hero are the smallest complete picture of that, and the middle one is the one worth staring at.

What the pictures cannot show #

Infinitely many states, twenty-six drawn. Every panel shows the first twenty-six weights, and the question in every case is what the remaining infinitely many do. The generator sums two hundred and sixty terms and asserts the outcome; the picture shows the beginning of a sequence.

Each panel is scaled to its own tallest bar. On one scale the transient case’s weights climb past ten thousand and the other two are flat lines along the axis. Scaling separately makes the shapes readable and means the heights are not comparable between panels, which the caption says.

And the walk is not drawn at all. Recurrence, null recurrence and transience are statements about trajectories, and the figure shows weights. The connection between them is the balance equation, which is algebra.

Where the ladder goes next #

This closes the ladder. It began with a rule that forgets where it came from and a theorem with two conditions; it ends with the same two conditions holding and the theorem failing, because a third assumption was hiding in the word finite.

What is left unwritten belongs to other anchors. Chains in continuous time, where the waiting in each state is exponential rather than one step, are a different object with the same skeleton. Chains whose state space is continuous rather than countable need a different notion of irreducibility altogether. Sideways: the walk that comes home is the same critical phenomenon indexed by dimension, and the time spent and the share held is the theorem that survives all three regimes in the form of a statement about time averages.

What is worth carrying away #

A hypothesis nobody states is the one that fails first.

Every theorem on the first four rungs said finite chain and none of them said what finiteness was for. It was for exactly one thing: guaranteeing that a positive solution of the balance equations can be normalised. Remove it and the equations still have positive solutions, and the solutions sometimes cannot be scaled into a distribution.

So the useful question about a theorem is which of its hypotheses is doing work and which is scenery. Here irreducibility and aperiodicity are named and turn out to be insufficient, while finiteness is unnamed and turns out to be the substance — and the replacement for it is a condition on a series rather than on a picture.