The chain that stops

The first rung’s chains all had a long run: run them far enough and the starting point stopped mattering. Put a state in that cannot be left and that whole question evaporates, because the walk does not run long — it ends.

A state that cannot be left is called absorbing, and a chain in which every state can reach an absorbing one is an absorbing chain. The questions that replace where does it settle are how long does it take and where does it stop, and both have exact answers.

Splitting the matrix #

Order the states with the transient ones first and the absorbing ones last, and the transition matrix falls into blocks. The transient-to-transient block is called $Q$; the transient-to-absorbing block is $R$; the absorbing states have a row that is all zeros except a one on the diagonal.

Everything reduces to $Q$. The chance of being in transient state $j$ after $k$ steps, having started at transient $i$, is the $(i,j)$ entry of $Q^k$ — because a walk staying transient for $k$ steps is a path through transient states only.

Since every transient state can reach absorption, those entries go to zero: the walk eventually leaves. So $I - Q$ is invertible, its inverse is $N = I + Q + Q^2 + \cdots$, and $N$ is called the fundamental matrix.

$N_{ij}$ is the expected number of visits to $j$ starting from $i$, which is the sum over $k$ of the chance of being at $j$ after $k$ steps. That reading is why the matrix is worth naming.

The two answers #

Expected time to absorption is the row sum of $N$: starting at $i$, the total number of steps is the total number of visits to transient states, and the expectation of a sum is the sum of expectations however dependent the terms.

Absorption probabilities are $B = NR$: to be absorbed at $a$ starting from $i$, visit some transient $j$ and then step to $a$, and summing over $j$ and over the number of visits gives the product.

Both can be had without inverting anything, by solving the systems they satisfy. Expected time $t$ satisfies $t = 1 + Qt$ — take one step, then expect $t$ again from wherever it lands. Absorption probability $b$ satisfies $b = R_{\cdot a} + Qb$, the same argument.

The figure solves both by elimination and then substitutes the answers back into those equations, which is a different computation from the one that produced them. A number computed one way and checked another is the standing rule here, and it is worth the extra line every time.

The gambler, worked out #

The chain drawn is the smallest interesting absorbing chain: a total between $0$ and $N$, going up with chance $p$ and down otherwise, stopping at either end.

At even odds the answers are famous and clean. Starting from $k$, the expected number of steps is $k(N-k)$, and the chance of reaching the top is $k/N$. For $N = 5$ and $k = 2$ that is $2 \times 3 = 6$ steps and a probability of $0.4$, which is what the figure prints.

Both come out of the linear systems immediately. At even odds $t_k = 1 + \tfrac12 t_{k-1} + \tfrac12 t_{k+1}$, so the second difference of $t$ is $-2$, and a sequence with constant second difference $-2$ vanishing at both ends is $k(N-k)$. The probability satisfies $b_k = \tfrac12 b_{k-1} + \tfrac12 b_{k+1}$, so $b$ is linear, and linear with $b_0 = 0$, $b_N = 1$ is $k/N$.

The chance of winning is the share of the money already held, which is the sentence people remember, and it holds only at even odds.

Away from even odds #

With $p \neq \tfrac12$ the answers change shape entirely, and the change is instructive.

Writing $r = (1-p)/p$, the chance of reaching the top from $k$ is

$$b_k = \frac{1 - r^k}{1 - r^N},$$

which is a ratio of geometric sums rather than a linear function. The figure checks it against the solve at every starting total.

The consequence is dramatic at large $N$. At $p = 0.49$, starting from the middle of a game to $20$, the chance of reaching the top is $0.4013$ — barely below a half. Starting from the middle of a game to $100$ it is $0.1192$, and at $p = 0.45$ over the same hundred it is under a thousandth.

Small biases compound, and the compounding is in the exponent. The ratio $r$ is raised to the number of steps, so a one per cent disadvantage is invisible over twenty steps and decisive over a hundred. That is the mathematical content of a familiar practical fact, and having the formula rather than the slogan is what makes the crossover computable rather than felt.

The expected length, and its shape #

The lengths deserve their own look, because they behave differently from the probabilities and the difference is the more surprising half.

At even odds the expected length from $k$ is $k(N-k)$ — a parabola, largest in the middle, zero at both ends. Over five totals it is $4, 6, 6, 4$ from the four starts, and the figure prints exactly those. Over a hundred totals, starting from the middle, it is $2{,}500$ steps.

The growth is quadratic in $N$, which is worth pausing on. Doubling the size of the game quadruples the expected number of steps, even though the walk’s typical displacement after $t$ steps grows like $\sqrt{t}$ — and those two facts are the same fact, since reaching a distance $N/2$ takes about $(N/2)^2$ steps. A walk’s displacement growing like the square root of time is where the quadratic comes from.

Away from even odds the expected length grows only linearly in $N$, because the drift carries the walk to one end rather than letting it wander. So the fair game is the slow one: a biased game ends sooner, and the more biased it is the sooner it ends.

The fairest game is the longest, which is a genuinely counterintuitive consequence and follows in one line from the second-difference equation.

Why there is no stationary distribution to find #

It is worth being explicit about what has been given up, since the first rung’s whole subject was the long run.

An absorbing chain does have stationary distributions — any distribution supported on the absorbing states is one, since nothing moves. But there are as many as there are absorbing states, and the chain does not converge to a single one: where it ends depends on where it began, which is exactly the reducible chain’s failure in a sharper form.

So the first rung’s theorem does not apply and its conclusion is false. The chain remembers its starting point forever, in the sense that the distribution over final states is a function of it.

What replaces the theorem is that the transient part decays. Every eigenvalue of $Q$ has size strictly under one, so $Q^k \to 0$, and that is the statement that absorption is certain. The rate of decay is the largest such eigenvalue, and the expected time is what the fundamental matrix computes from it.

The coupon collector, seen as an absorbing chain #

The site already has an absorbing chain and does not call it one, which is worth pointing out because the reframing makes the computation immediate.

Collecting coupons is a chain whose states are how many distinct kinds have been seen. From state $j$ with $n$ kinds in total, the chance of moving to $j+1$ is $(n-j)/n$ and of staying put is $j/n$. State $n$ is absorbing.

The expected time to absorption from $0$ is then the row sum of the fundamental matrix, and because the chain only ever moves forward the matrix is triangular and the sum collapses: the expected wait in state $j$ is $n/(n-j)$, and adding those over $j$ gives $n$ times the harmonic number.

The famous $n \log n$ is a row sum of a fundamental matrix, and seeing it that way explains why the answer is a harmonic sum rather than something else: each state is visited a geometrically distributed number of times, and the expectations add.

The same matrix, three questions #

It is worth collecting what the fundamental matrix answers, because the list is longer than the two headline quantities and they all come from one inversion.

$N_{ij}$ is the expected number of visits to $j$ from $i$. Summing over $j$ gives the expected time to absorption. Multiplying by $R$ gives the absorption probabilities. And the variance of the absorption time comes from $N$ too, by a formula involving $N(2N_{\mathrm{dg}} - I) - N_{\mathrm{sq}}$ where the subscripts pick out the diagonal and the entrywise square.

So one matrix inversion answers how long, where, and how variable — and each answer is exact. That is a good return on a single computation, and it is why the matrix is given a name rather than being written out as a series each time.

The pattern is familiar from linear algebra generally: an inverse is worth computing when several questions share it, and here three do. Where only one answer is wanted, solving the corresponding system directly is cheaper and is what the figure does.

What the simulation is for #

The figure runs four thousand seeded games and reports the mean length and the share of wins beside the computed values.

The simulation decides nothing. The expected length is an exact rational number, produced by solving a linear system, and a run of four thousand games gives an estimate whose error is of the size that four thousand samples give. The generator asserts that the simulated mean lands within twelve per cent of the exact answer and the simulated win share within a twentieth — which is a check that the model being simulated is the model being solved, not a check on the arithmetic.

A simulation beside an exact answer is a test of the transcription, and that is the only thing it can honestly be. If the two disagreed, the fault would be that the simulated walk is not the chain the matrix describes.

That distinction matters because the reverse arrangement — simulating first and quoting the average as the answer — is common and is what this collection avoids everywhere. The exact answer exists here, so the exact answer is the answer.

A single drawn walk is worth having beside the table for one reason: it shows that the quantity being averaged is a whole trajectory rather than a number. The expected length is an average over all the walks that could have happened, and every one of them is a path of this kind that stops when it touches an end.

Hitting times more generally #

Absorption is a special case of a question that makes sense on any chain: how long until the walk first reaches a given state.

Make the target absorbing by deleting its outgoing edges, and the expected hitting time from anywhere is the absorbing chain’s expected time to absorption. So every hitting-time question is an absorbing-chain question, and the fundamental matrix answers all of them.

That is the machinery the next rungs need, and it is worth noting that it produces exact expected times, which is a different kind of quantity from the bounds on how long a chain takes to become well mixed. Those bounds are a subject of their own with its own literature, and nothing here computes one: everything on this page is an exact solve of a finite linear system.

The distinction is worth keeping straight. An expected hitting time is a rational number determined by the matrix; a mixing bound is an inequality about how fast a distribution approaches another, and only the first is what a fundamental matrix produces.

Every finite chain decomposes this way #

One structural fact makes absorbing chains more than a special case: every finite chain is built out of them.

Take any finite chain and group the states into communicating classes — sets in which every state reaches every other. Some classes cannot be left once entered; call those the closed classes. Every other state is transient, and the walk eventually enters some closed class and stays.

Collapsing each closed class to a single point turns the chain into an absorbing one, and its fundamental matrix answers which class the walk ends in and how long it takes to get there. Then inside each closed class the first rung’s theory applies and gives the long-run shares.

So the general finite chain is an absorbing chain feeding into several irreducible ones, and the two rungs so far cover between them everything a finite chain does. That decomposition is the reason the theory of finite chains is complete in a way most theories are not.

Where it fails, and what it needs #

Every state must reach an absorbing one. Otherwise there is a set of transient-looking states the walk can circle forever, $I - Q$ is singular, and the expected times are infinite. The figure’s solve asserts non-singularity at every elimination step.

The expected time can be finite while the variance is not. For chains with heavier structure the mean exists and higher moments do not, and a simulation then behaves badly in a way its sample mean hides. That does not happen here, since the state space is finite, and it is the standard trap one step further out.

And absorption certain is not absorption soon. The gambler’s game ends with probability one and its expected length grows like $k(N-k)$, so at $N = 1000$ starting from the middle the expected length is a quarter of a million steps. Certainty and speed are different claims.

What the pictures cannot show #

The linear system is not drawn. The chain diagram shows the rule; the table shows the answers; the elimination that gets from one to the other is arithmetic in the generator and has no picture.

The simulation is a number, not a picture. Four thousand games are summarised as two figures in the caption, which is all a run of that size is worth.

And the extreme cases are outside the drawing. A game over a thousand totals has the same structure and a picture of a thousand circles is not a picture. Every claim here about large $N$ comes from the formulas rather than from the drawn instance.

Where the ladder goes next #

The next rung goes back to chains with a long run and asks a sharper question about them: not what the shares are, but when they can be read off the diagram without solving anything. A chain that runs the same backwards has shares proportional to the weights on its edges, and the condition for that is strictly stronger than being stationary.

Sideways: two barriers and a fair game is the same gambler’s problem approached as a random walk, and the coupon collector is the absorbing chain this rung reframed.

What is worth carrying away #

When a limit does not exist, the useful move is to find the question whose answer is exact.

An absorbing chain has no limiting distribution, and asking for one produces either a wrong answer or a family of them. Asking instead how long and where produces two numbers that solve linear systems, with no limits, no convergence and no approximation anywhere.

Exact beats asymptotic when exact is available, and on a finite chain it usually is. The infinite state spaces where it stops being available are where the last rung of this ladder goes.

There is a second habit worth taking from the same place. Every quantity on this page was defined by a first-step decomposition: take one step, then ask the same question from wherever the step landed. That turns a question about an unbounded future into a finite system of equations, and it works whenever the process forgets its past — which is what being a Markov chain means. The technique is older and wider than the matrices, and it is the thing to reach for first.