Two barriers and a fair game

A walk on a line, one step at a time, each direction equally likely — with the single change that it stops when it reaches either end. One end is ruin; the other is the whole of the money on the table.

Everything about this game is settled by the straight line on the right. A player who starts with $k$ of a total of $N$ is ruined with probability $1 - k/N$, and reaches the top with probability $k/N$. Nothing else about the game matters: not how long it takes, not how the stakes are sized, not what happens in the middle.

The recurrence, which is two lines #

Write $p_k$ for the chance of eventual ruin starting from $k$. After one round the player has $k+1$ or $k-1$, each with probability a half, so

$$p_k = \tfrac12 p_{k-1} + \tfrac12 p_{k+1},$$

with $p_0 = 1$ and $p_N = 0$. That equation says each value is the average of its neighbours, which forces the sequence to be an arithmetic progression — a straight line, and the only straight line through those two endpoints is

$$p_k = 1 - \frac{k}{N}.$$

The condition each value is the average of its neighbours is worth naming, because it recurs everywhere: it is discrete harmonicity, and it is the reason so many probability problems have answers that are linear, or that solve Laplace’s equation, or that can be computed by relaxation. A fair walk’s hitting probabilities are harmonic functions of the starting point, always.

The generator behind the figure does not use the formula. It solves for the $p_k$ and then checks that each is the average of its neighbours, and refuses to draw if any is not — so the straight line under the picture has been verified against the recurrence it claims to satisfy rather than asserted from it.

The small player against the large one #

The consequence that matters is not the formula but its asymmetry.

A player with a tenth of the money on the table is ruined nine times out of ten in a perfectly fair game. Against an opponent with unlimited resources, the ruin probability is the limit of $1 - k/N$ as $N$ grows without bound, which is $1$: ruin is certain.

That is the sharpest statement in the subject and it needs care in reading. It does not say the small player loses on average — the game is fair, and the expected gain is exactly zero at every moment. It says that the only two ways for the game to end are ruin and the opponent’s ruin, and if the opponent cannot be ruined, only one exit exists. The fairness is preserved by the size of the win in the tiny probability of surviving indefinitely.

This is the mathematics behind a piece of standard advice that sounds like superstition: against a much richer opponent in a fair game, the only sound strategy is to play few, large rounds rather than many, small ones. Fewer rounds means fewer chances for the barrier to be hit, and the ruin probability with stakes of size $s$ depends on $k/s$ and $N/s$ — so raising the stakes shrinks the effective distance to both barriers equally and makes the game more nearly a single coin toss, which is the fairest deal a small player can get.

When the table is unlimited #

Removing the upper barrier removes the only way the game can end well, and the arithmetic notices.

With one barrier at zero and nothing above, the ruin probability is $\lim_{N \to \infty} (1 - k/N) = 1$. Every fair game against an unlimited opponent ends in ruin, from any starting stake, with certainty.

The mechanism is the recurrence of the unbounded walk. A fair walk returns to every level it has ever visited, infinitely often, given enough time — so it returns to zero, and zero is where the game stops. Wealth does not protect the player; it only postpones the visit.

What fairness buys instead is the time. The expected duration from stake $k$ against an unlimited opponent is $\lim k(N-k) = \infty$: the game lasts forever on average while ending with probability one, which is the same infinite-mean-with-certain-outcome pairing the first-return time has. A player with a large stake is not safer, only slower to lose, and the slowness has no bound.

What a small edge does #

Fairness is doing a great deal of work in the straight line, and removing it changes the answer’s character rather than its value.

With a win probability $p \ne \tfrac12$ and $r = (1-p)/p$, the recurrence has solution

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

which is exponential rather than linear. Exponentials are unforgiving. At $p = 0.48$ on a table of $100$, a player starting with half is ruined with probability $0.98$; at $p=0.5$ it is exactly $0.5$. A two-percent shift in each round has turned an even contest into a near-certainty, because the small edge is compounded over every one of the hundreds of rounds the game takes.

The general shape is that a fair game is decided by the ratio of the stakes and an unfair one is decided by the edge, with the crossover at a stake ratio of about $1/|2p-1|$. Below that the barrier matters more; above it the drift does.

How long it lasts #

The second question has an answer as clean as the first, and a shape that surprises people who have absorbed the first one.

Let $d_k$ be the expected number of rounds from stake $k$. Conditioning on the first round gives

$$d_k = 1 + \tfrac12 d_{k-1} + \tfrac12 d_{k+1}, \qquad d_0 = d_N = 0,$$

whose solution is

$$d_k = k(N-k).$$

The product of the two stakes. A player with $1$ against $99$ lasts $99$ rounds on average; a player with $50$ against $50$ lasts $2{,}500$. The game between equals takes twenty-five times as long as the lopsided one, and the longest possible game is the most even one.

That formula also carries a warning about averages. The distribution of the duration is very skewed: most fair games between equals end well before $2{,}500$ rounds, and a few run enormously long, and it is the few that carry the mean. Reporting $k(N-k)$ as how long a game takes is the usual mistake of quoting a mean for a heavy-tailed quantity, and it is the same mistake as saying a walk returns to its start after an average number of steps when the average is infinite.

Why the answer is a martingale in disguise #

There is a second derivation, and it explains the linearity rather than computing it.

The player’s stake in a fair game is a martingale: whatever has happened so far, the expected stake after the next round equals the stake now. The optional stopping theorem says that under mild conditions the expected value at a stopping time equals the value at the start — so if the game ends at $0$ or at $N$,

$$k = 0 \cdot \Pr[\text{ruin}] + N \cdot \Pr[\text{win}] \quad\Longrightarrow\quad \Pr[\text{win}] = \frac{k}{N}.$$

One line, no recurrence, and it makes the linearity obvious: the answer is linear because expectation is linear and the stake is conserved on average.

The duration falls out of the same machinery applied to a second martingale, $S_t^2 - t$, whose conservation gives $k(N-k)$ immediately.

What the martingale argument does not do is survive the biased case as easily — there the conserved quantity is $r^{S_t}$ rather than $S_t$, which has to be found rather than noticed. It is a good example of a proof technique that is dramatically shorter when it applies and offers no help finding out whether it does.

Where the reflection principle gives up #

The fold that answers the one-barrier questions can be applied here too, and it is instructive to watch it fail as a method while remaining correct as an identity.

Reflect a path at its first touch of the lower barrier and it becomes a path from the mirrored start — but that mirrored path may now cross the upper barrier, which the original was not allowed to do, so the correspondence over-counts. Correcting it means reflecting again in the upper barrier, which over-corrects, and again. What comes out is an infinite alternating sum of binomial coefficients, one term per bounce between the two mirrors, exactly analogous to the images in a pair of facing mirrors.

That series is correct and converges, and nobody uses it. The recurrence gives $1 - k/N$ in three lines.

The lesson is about tool selection rather than about walks. A method that turns a constrained count into an unconstrained one works beautifully with one constraint and degrades combinatorially with two, while a method that conditions on the first step is indifferent to how many barriers there are. Neither is better; they fail in different places, and knowing where is most of what fluency means.

The problem that started the subject #

Gambler’s ruin is one of the oldest questions in probability and it arrived with the subject rather than after it.

Pascal and Fermat corresponded in 1654 about a related question — how to divide the stakes of an interrupted game — and Pascal posed a version of the ruin problem to Fermat the same year. Christiaan Huygens included it in 1657 as the fifth and last problem of De ratiociniis in ludo aleae, the first printed treatise on probability, and stated it in the form still used: two players with twelve counters each and dice deciding the transfer, asked for the odds.

Huygens’ problem was solved by Jacob Bernoulli, by Montmort, by de Moivre, and by Nicolaus Bernoulli — four solutions to a single problem within seventy years, which is a fair measure of how central it was. De Moivre’s 1712 treatment introduced the ratio $r = q/p$ and produced the exponential formula, and the technique he used is the one still taught.

Two things about that history are worth carrying. The first is that the problem was posed about a game and answered about a process, and the answer turned out to be the useful thing: the same recurrence governs the extinction of a population, the failure of an inventory, the absorption of a particle at a boundary, and the exit of a diffusing quantity from an interval.

The second is what it did to the idea of fairness. Before this problem, a fair game was one with equal odds each round. After it, the fact that an equal-odds game between unequal purses has a nearly certain outcome had to be absorbed, and the word fair had to be split into two — fair per round, and fair over the game — which are different properties and are routinely confused to this day.

What it costs to model a real game this way #

Three assumptions are doing quiet work, and each is wrong about some real situation the model gets applied to.

The stake is a whole number of unit bets. A player who can vary the stake is playing a different game, and the difference is not small: bold play — betting the maximum that could be needed at every step — is provably optimal against an unfavourable game, and it beats unit betting by a wide margin. The straight line above is the answer for a player who has already given up the only decision worth making.

The rounds are independent and the odds never move. Card games with memory violate this, which is the whole of card counting; so does any game where the opponent adapts. The recurrence needs the walk to be Markov — that what happens next depends only on the current stake — and that property is exactly what a chain with memory lacks.

Ruin is absorbing. In practice a ruined player borrows, or leaves and returns, and a business at zero raises capital. Making the lower barrier reflecting rather than absorbing changes the question completely: the walk then has no ending, and the interesting quantity becomes the long-run fraction of time spent near the bottom rather than the probability of arriving there.

None of these makes the model useless. They locate what it is a model of: a fixed-stake, memoryless game with a hard floor, which is a good description of some situations and a poor one of most, and the honest use of the formula requires knowing which.

What the picture cannot show #

The left panel of each figure draws three games, and three games say nothing about a probability. They are there to show what absorption looks like — a path that stops rather than continuing — and the quantitative claim lives entirely in the right panel, which is computed rather than sampled.

There is also no way to draw the certainty of ruin against an infinite opponent, which is the essay’s strongest statement. It is a limit of the linear formula as $N$ grows, and every drawable game has a finite $N$ with a genuine chance of survival. The figure at $N = 20$ shows a ruin probability of $0.85$, the figure at $N=100$ would show $0.97$, and no figure shows $1$.

Nor does anything here show the duration’s distribution, only its mean. A picture of the mean is the most misleading kind of summary for a quantity this skewed, and the honest form of the statement is in the prose rather than in the picture.

The ladder from here #

Below: the unbounded walk, the fold that counts constrained paths and the time a fair game spends one-sided. Above and sideways: absorbing Markov chains, of which this is the smallest interesting instance, and where the same conditioning argument runs on a general state space; the harmonic functions the ruin probabilities turn out to be, which is where walks meet potential theory; and the diffusion limit, where the recurrence becomes a differential equation and $k(N-k)$ becomes the same parabola with continuous coordinates.

A conserved quantity, and what it forces #

The lasting point is that both answers came from conservation.

The stake is conserved in expectation, so the ruin probability is forced to be linear before any calculation is done. The square of the stake, minus the time, is conserved in expectation, so the duration is forced to be the product of the two distances. Neither result was computed from the structure of the game; both were read off a quantity that does not change.

That is the same move as an invariant that decides whether a puzzle can be solved and an alternating sum that survives every deformation. The question what does this process leave alone is worth asking before the question what does this process do, because the first has short answers and the second usually does not.