An urn forgets its start only below one half

A walk that follows its own footsteps took Pólya’s urn — one red ball and one blue, draw one, return it with another of the same colour — and read the sequence of draws as a walk: up for red, down for blue. Every walk left along its own straight line, at a speed fixed by its first few steps, and the number of red draws after twenty draws was exactly equally likely to be any number from nought to twenty. The urn remembered its beginning for ever.

That urn is one corner of a much larger family, and the rest of the family behaves differently. A draw need not add only its own colour. It can add some balls of each: drawing red might add three red and one blue, drawing blue three blue and one red. It can add only the other colour, so that every red drawn makes blue likelier. Each such rule is a different urn, and each, drawn as a walk, is a different kind of walk. This essay follows five of them, from an urn that corrects itself to Pólya’s urn that reinforces itself completely. The question is which of them forget how they began and which never do. The answer turns on one number, and the change comes when that number passes one half.

A draw can add the other colour #

The five urns in the figure all start with one ball of each colour and all add the same number of balls at every draw, whatever colour comes out. The first adds one ball of the other colour: drawing red puts in a blue, drawing blue puts in a red. Bernard Friedman described urns of this kind in 1949, and this one is the extreme of his family — an urn that pushes back against whatever has just happened. If red has been drawn more often, the urn is fuller of blue, and the next draw leans towards blue. Its walk stays closer to the middle than a coin-tossing walk does.

The second and third urns add two red and one blue for a red draw, or three red and one blue, and symmetrically for blue. They reinforce, but not completely: some of every addition goes to the other side. The fourth adds seven of the drawn colour and one of the other, which is nearly Pólya’s rule. The fifth is Pólya’s urn itself, adding one of the drawn colour and none of the other.

The figure divides the five sharply. The first three panels look like ordinary random walks, the kind a walk that always comes home begins with: a tangle of paths crossing the middle line again and again, the spread across the panel growing slowly. The fourth and fifth look like the Pólya walks of the previous essay: a fan of lines, each leaving the start at its own angle and keeping it. Something about the rule decides which picture the urn produces, and it is not simply whether the urn reinforces, because the second and third urns reinforce and still behave like coins.

Two numbers decide every balanced urn #

An urn of this kind is described by four numbers. Drawing red adds $a$ red and $b$ blue; drawing blue adds $c$ red and $d$ blue. The urn is balanced when every draw adds the same total, $a + b = c + d$, so the number of balls in the urn after $t$ draws is known in advance and only the colours are random. All five urns here are balanced: Friedman’s and Pólya’s add one ball a draw, the others three, four and eight.

The four numbers form a two-by-two matrix, and the behaviour of the urn is governed by its two eigenvalues. For a balanced urn they are easy to find. One is the total added per draw, $a + b$, which only says how fast the urn fills. The other is $a - c$: how many more red balls a red draw adds than a blue draw does. It measures how much the urn’s composition responds to what was drawn. If $a - c$ is positive, drawing red makes red likelier; if it is negative, drawing red makes red less likely; if it is nought, the draws have no effect on the composition at all.

What matters is the ratio

$$\rho = \frac{a - c}{a + b},$$

the response as a share of the growth. For Friedman’s urn it is $-1$: a red draw adds nothing red, a blue draw adds one red, so $a - c = -1$, against a total of one. For the urns adding two and one, three and one, seven and one it is $\tfrac13$, $\tfrac12$ and $\tfrac34$. For Pólya’s urn it is $1$, the largest it can be. And an urn that adds one of each colour whatever is drawn has $\rho = 0$: its composition never moves from even, so its draws are independent tosses of a fair coin.

The same role for a second eigenvalue runs through the site’s essays on chains. In how long until it forgets, a Markov chain’s second eigenvalue sets how quickly it loses the memory of where it started: the closer that eigenvalue is to the first, the longer the memory. An urn is not a fixed chain — it grows, and its transition probabilities change at every draw — but the ratio $\rho$ does the same work. It says how much of a disturbance in the composition survives as the urn fills.

Below one half, the urn behaves like a coin #

The first figure is a simulation. The number of red draws can also be computed exactly: after $t$ draws with $k$ of them red, the urn holds a known number of red balls and a known total, so the chance that the next draw is red is known, and the whole distribution of $k$ after $n$ draws follows by stepping forward one draw at a time. Every figure from here on is computed this way, with no simulation and no sampling error.

The spread of an urn’s walk is the standard deviation of the number of red draws, and on logarithmic axes a power law is a straight line whose slope is the power. Friedman’s urn and the urn at $\rho = \tfrac13$ have slope one half: they spread like $\sqrt n$, exactly as a walk of fair coin tosses does and as the walk that becomes a curve requires before it can be rescaled into Brownian motion. Only the constant in front differs. For Friedman’s urn the variance of the number of red draws after $n$ draws is $n/12$; for fair tosses it is $n/4$, so the self-correcting urn has a third of a coin’s variance and $1/\sqrt3$ of its spread. For the urn at $\rho = \tfrac13$ the variance tends to $\tfrac34 n$, three times a coin’s. Its reinforcement shows only in the constant.

A single formula covers all of these. For a symmetric urn of this kind with $\rho$ below one half, the variance of the number of red draws grows like

$$\frac{n}{4(1 - 2\rho)}.$$

At $\rho = 0$ that is the coin’s $n/4$. At $\rho = -1$ it is $n/12$, which the exact computation reproduces to three figures. At $\rho = \tfrac13$ it is $\tfrac34 n$; the exact value at two thousand draws is still only $0.69 n$, because the correction falls away slowly, like $n^{-1/3}$, but it is moving towards the formula at every doubling. And the formula carries its own warning: as $\rho$ approaches one half the denominator approaches nought, and the variance per draw grows without bound. Something must change at the threshold, because the formula stops making sense there.

Above one half the slope is not one half at all. The urn at $\rho = \tfrac34$ spreads with slope $0.75$, Pólya’s urn with slope $1$. The spread grows like $n^{\rho}$, and the exponent is the ratio itself.

The exponent has a corner #

The five urns are five points. A whole family of urns traces the full relationship: let each draw add $a$ balls of its own colour and one of the other, for $a$ from nought to twenty. Then $\rho = (a - 1)/(a + 1)$ runs from $-1$, at Friedman’s urn, up towards one, and each urn gives a measured exponent.

The points fall on the larger of $\tfrac12$ and $\rho$. Every urn with $\rho$ below one half has exponent one half, however strongly it corrects itself and however strongly it reinforces, as long as the reinforcement stops short of the threshold. Above the threshold the exponent follows $\rho$. The line has a corner at one half, and the measured points round it off only slightly, because at exactly one half there is a logarithm that a finite range of $n$ still sees.

David Freedman proved this in 1965, in a paper titled simply Bernard Friedman’s urn: below one half the number of red draws, centred and divided by $\sqrt n$, tends to a normal distribution; at one half the right divisor is $\sqrt{n \log n}$; above one half it is $n^{\rho}$, and the limit is a random variable that is not normal. Athreya and Karlin reached the normal half of the picture in 1968 by a different route, embedding the urn in a continuous-time branching process in which each ball independently reproduces, and the general two-colour balanced case was settled by Bagchi and Pal in 1985.

Why the line falls at one half #

The threshold has a short explanation, and it is the same arithmetic that decides when an infinite sum converges.

Look at a single draw, the $t$-th. Its outcome is partly luck: the urn says red with some probability, and whether red comes out is a toss of a biased coin. That luck is about the size of one draw, and it moves the count of red draws by about one. But it also changes the urn. One draw’s worth of extra red is a fraction of about $1/t$ of the balls in the urn, and the urn responds to its own composition with strength $\rho$. Followed forward, that small change in the composition grows or shrinks as the urn fills, and by the $n$-th draw the single piece of luck at time $t$ has shifted the count of red draws by roughly $(n/t)^{\rho}$.

So the variance of the count at time $n$ is roughly a sum over all the draws of the squares of their effects:

$$\sum_{t=1}^{n} \left(\frac{n}{t}\right)^{2\rho} = n^{2\rho} \sum_{t=1}^{n} t^{-2\rho}.$$

The sum on the right is the one every first course in series tests: $\sum t^{-p}$ converges when $p$ is greater than one and diverges when it is at most one. Here $p = 2\rho$, so the dividing line is $\rho = \tfrac12$.

When $\rho$ is below one half the sum diverges, and grows like $n^{1 - 2\rho}$; multiplied by $n^{2\rho}$ that gives a variance proportional to $n$, the $\sqrt n$ spread. Most of it comes from the late draws, those with $t$ comparable to $n$, and there are very many of them, each contributing only a little. That is precisely the setting of the central limit theorem: a total made of many small, nearly independent pieces, none of which dominates. The result is a bell, for the same reason the pegs of the bell curve from coin flips produce one.

When $\rho$ is above one half the sum converges. The variance is $n^{2\rho}$ times a constant, a spread of $n^{\rho}$, and the constant is dominated by the first few terms — the draws with small $t$. The total is then not made of many small pieces. It is made mostly of a few large ones, and a sum dominated by a few terms has no reason to be normal. It looks like whatever those first few draws make it look like.

At exactly one half the sum is the harmonic series, which diverges like $\log n$. The variance is $n \log n$ in scale — the exact computation gives $1.89 n$ at two thousand draws, against a quarter of $n \log n$, which is $1.90 n$ — and the many late draws still dominate, by a logarithmic margin, so the limit is still normal, with the extra $\sqrt{\log n}$ in the divisor.

The same picture appears in a coin in front of every term, where random signs are put in front of $1, \tfrac12, \tfrac13, \dots$. There the terms shrink fast enough for the sum of squares to converge, the first few terms dominate, and the sum settles on a random number with a flat-topped distribution that is not a bell. An urn above one half is that series in disguise: its first few draws are the large early terms.

Ten draws that decide the rest #

The explanation makes a prediction that can be computed directly. If the spread above one half comes mostly from the first few draws, then after those draws most of the outcome should already be determined. Below one half it should not.

The question can be made exact. After $m$ draws, the best forecast of the final count — its expected value given what has been seen — is a definite number, and as the first $m$ draws vary, that forecast varies too. The variance of the forecast, as a share of the variance of the final count, is the share of the final spread already fixed by the first $m$ draws. For a balanced urn the forecast is a straight-line function of the count so far, and its slope can be carried forward exactly from draw $m$ to draw $n$.

After ten draws out of two thousand, Pólya’s urn has fixed 83 per cent of its final variance and the urn at $\rho = \tfrac34$ has fixed 75 per cent. After a single draw they have fixed a third and more than two-fifths respectively. The remaining 1,990 draws mostly carry forward what the first ten decided.

Below one half the picture is reversed. The urn at $\rho = \tfrac13$ has fixed 11 per cent after ten draws, and that share falls further as $n$ grows. Friedman’s self-correcting urn has fixed nothing worth printing: even after a thousand of its two thousand draws, the first half has fixed only an eighth of the final variance, because every lean the urn develops is pushed back. For comparison, independent coin tosses fix exactly $m/n$ of the variance in $m$ draws — half after half the draws. Friedman’s urn forgets faster than a coin. The urn at $\rho = \tfrac12$ sits between, at 32 per cent after ten draws, and its curve moves only as slowly as a logarithm towards forgetting.

This is the sense in which an urn forgets or does not. Below the threshold the fate of the urn is made late, and its beginning dissolves into the many draws that follow. Above it the fate is made early and then merely expanded.

When the limit is not a bell #

The exact distributions show what the limits look like. Centre the number of red draws on its mean and divide by its standard deviation, and every urn gives a curve of the same width; the question is the shape.

Below the threshold the curve is the bell. The thick curve for $\rho = \tfrac13$ and the dashed bell lie on one another so closely that the dashes are barely visible. Pólya’s urn gives a flat line: the number of red draws is exactly uniform, every count equally likely, the result the previous essay proved by counting orders of draws. The urn at $\rho = \tfrac34$ gives something new: a curve with two humps, one on each side of the middle, and a dip at the centre.

The humps have a plain cause. This urn adds seven of the drawn colour and one of the other, starting from one of each. After the first draw it holds eight of one colour and two of the other. That first draw has already tilted the urn four to one, and the next few mostly agree with it. So the urns divide early into those that went red and those that went blue, and the final count keeps that division as two humps. It is the clearest picture of the early draws deciding the outcome: the first of them can be read off the final distribution.

A single number summarises how far a shape is from the bell. Excess kurtosis compares how much of a distribution’s spread lies in its tails and shoulders with how much the bell puts there; it is nought for the bell, negative for distributions that are flatter or broader-shouldered, and exactly $-1.2$ for a uniform distribution.

The curves split into the same two groups as before. For Friedman’s urn the excess kurtosis is already within a hundredth of nought at 125 draws. For the urn at $\rho = \tfrac13$ it starts at $-0.11$ and shrinks steadily, to $-0.012$ at four thousand draws, heading for the bell. At exactly one half it shrinks too, from $-0.34$ to $-0.13$, slowly, as a limit with a logarithm in it should. Above one half it does not head for nought at all: at $\rho = \tfrac34$ it hovers near $-1$, moving by about a hundredth each time the number of draws doubles, and for Pólya’s urn it is $-1.2$ at every $n$. Those are the non-normal limits of Freedman’s theorem, drawn.

Whether the fluctuations of a sum are normal is often treated as a question about the size of the pieces. How fast the bell arrives measures the approach for independent pieces, and the rate there is one over the square root of the number of terms. Here the pieces are not independent and the answer is not a rate. Above one half the bell does not arrive at all, however long the urn runs.

A big start hides the memory without erasing it #

If the first few draws decide everything above one half, then how the urn starts should matter, and it does. Start the urn at $\rho = \tfrac34$ with sixteen balls of each colour instead of one, and the first draw adds eight balls to thirty-two rather than to two. It tilts the urn far less. The early draws then contribute many moderate pieces rather than a few huge ones, and the result should look more like a bell.

The figure separates two things. At $\rho = \tfrac13$ every starting size heads towards nought, and quadrupling the draws more than halves the distance from the bell, whatever the start. The urn forgets its start, as an urn below one half must. At $\rho = \tfrac34$ the thick line and the thin line nearly coincide: between a thousand draws and four thousand the shape hardly moves, so it has largely settled. But where it settles depends on the start. With one ball of each colour the excess kurtosis is about $-0.97$ and the distribution has two humps. With four of each the humps are gone and it is $-0.71$. With sixty-four of each it is $-0.12$, close to a bell.

So a large start can make the urn above one half look nearly normal. It does not make it forget. The limit is a different distribution for every starting composition, and that dependence is the memory: the urn carries its initial state into the outcome for ever, however many draws are made. Below one half the starting composition affects only how quickly the bell is reached, not whether.

Where the threshold turns up #

Two-colour urns are the simplest case of a general principle about growing random systems, and the threshold at one half reappears wherever the principle applies. An urn with many colours has a replacement matrix with many eigenvalues. The largest is again the growth rate, and the question is again whether every other eigenvalue’s real part stays below half of it. If it does, the fluctuations of the composition are normal; if any other eigenvalue exceeds half the largest, its direction carries a non-normal random limit. Svante Janson’s 2004 theorems give the general statement.

The most quoted example is a data structure. An $m$-ary search tree stores keys in nodes that each hold up to $m - 1$ of them, and the number of nodes it needs to store $n$ random keys can be analysed as an urn whose colours are the possible states of a node. The replacement matrix’s eigenvalues depend on $m$, and for $m$ up to 26 every non-principal eigenvalue stays below half the principal one: the space the tree uses has normal fluctuations around its mean. From $m = 27$ onwards a pair of complex eigenvalues has real part above the threshold, and the fluctuations are no longer normal — they oscillate, carrying a random phase set by the first keys inserted. Chern and Hwang described this phase change in 2001. Nothing about trees of 27-way nodes is special except an eigenvalue crossing one half.

The essays on chains reached the same separation from another side. In the average settles and the wobble does not, the law of large numbers and the central limit theorem are the same sums at two magnifications. For an urn above one half the first still holds — the share of red settles — but the second fails: the wobble around the settled value is neither $\sqrt n$ in size nor normal in shape, because the wobble was decided at the start rather than made up from the many draws since.

Still open: urns that are not balanced and replacements that are random #

The classification is complete for balanced urns, where every draw adds the same number of balls and the total is not random. It is far less complete when that fails. If a red draw adds three balls and a blue draw adds one, the size of the urn after $n$ draws depends on its history, the neat recursion that made every figure here exact is lost, and the eigenvalue description has to be rebuilt around a random clock. Many unbalanced two-colour urns have been worked out case by case, but a general rule as clean as the larger of one half and $\rho$ is not available.

Urns whose replacement numbers are themselves random — adding two red with probability one half and none otherwise, say — are covered by the branching-process method when the averages behave well, but the boundary cases are delicate, and urns that can remove balls run into a different problem: the composition can be driven to an edge where a colour is exhausted, and the urn’s survival becomes part of the question. Urns with infinitely many colours, which arise as models of random trees and of how new types enter a population, are an active subject.

The threshold itself raises a sharper question for the cases above it. The limit there is a random variable whose distribution depends on the start, and its moments can be computed, but its shape is known explicitly only in special cases — the uniform for Pólya’s urn, some beta-like laws for particular triangular urns. For the urn at $\rho = \tfrac34$ with one ball of each colour, the two-humped limit the figures show is defined, computable to any accuracy and not known in closed form.