A walk that follows its own footsteps

A walk that may not step where it has been took the simplest random walk and forbade it its own past. The walk that results is pushed outward by every site it has already used, spreads faster than an ordinary walk, and has resisted exact analysis for seventy years. This essay takes the opposite rule. The walk is not forbidden its past; it is drawn towards it. At each step it goes up with probability equal to the share of its steps so far that went up, so every up-step makes the next up-step likelier.

The rule is older than it looks. George Pólya studied it in 1923 as an urn: start with one red ball and one blue, draw a ball at random, put it back together with another of the same colour, and repeat. Stepping up for red and down for blue turns the sequence of draws into a walk, and the share of red in the urn is the walk’s chance of stepping up next. The urn was a model of contagion — each case of a disease making the next case of the same kind likelier — and it turns out to be one of the few reinforced processes that can be solved exactly.

Each walk chooses a speed and keeps it #

The figure shows the difference from an ordinary walk at once. An ordinary fair walk wanders inside a band that widens like $\sqrt n$, the spread that the walk that becomes a curve turns into Brownian motion. The urn walks leave the band within a few hundred steps and travel along nearly straight lines, each at its own speed: here from $-0.87$ to $0.99$ steps of height per step of time, with some walks barely moving and some climbing almost every step.

The straight lines are the reinforcement at work. After a few hundred steps the share of up-steps is some number, say 0.7, and the walk keeps stepping up with probability about 0.7, which keeps the share near 0.7; a single step changes the share by less than a thousandth. The walk has become, to a close approximation, an ordinary walk with a biased coin, and a biased walk travels in a straight line at speed $2p - 1$. What is not fixed is $p$. Each walk’s early steps, when the urn held only a few balls and each draw moved the share a lot, decide which biased coin it ends up tossing. Three of the twelve walks in the figure have speeds within 0.05 of nought; they are the ones that stay near the band and cross the starting level again and again, and they are a small instance of the walks that turn out, below, to carry an infinite average on their own.

How early the speed is decided #

How early is early can be measured. After $n$ draws with $r$ reds, the hidden bias still unknown to an observer has the beta distribution with parameters $r + 1$ and $n - r + 1$, whose standard deviation is about $\sqrt{p(1-p)/n}$. After ten draws that is around 0.14 for a walk near the middle; after a hundred, 0.05; after a thousand, 0.016. The figure’s walks are effectively committed to their speeds within the first hundred steps, and the remaining nineteen hundred refine the commitment rather than change it.

That is why the lines in the figure look straight from the left edge rather than becoming straight gradually. An ordinary walk with a fixed biased coin also travels along a line, but it wobbles around it by $\sqrt n$, and its wobble grows. The urn walk’s wobble around its eventual line is of the same order, and since its speed is set by its early history, that early wobble is frozen into the speed itself. Two urns that differ only in their first three draws end up travelling at speeds that typically differ by several tenths, a difference the next million draws never undo.

Every count is equally likely #

The distribution of where the walk is after $n$ steps can be computed exactly, by tracking the probability of each possible number of red draws one draw at a time. From one ball of each colour, it comes out flat.

Twenty draws from an urn starting with one red and one blue give every count of reds from 0 to 20 with probability exactly $1/21$. Twenty reds in a row is as likely as ten of each. For a fair coin the two would differ by a factor of 184,756; for the urn they are equal, because the first red makes the second likelier, and so on, and the reinforcement exactly compensates for there being only one way to draw twenty reds.

The calculation is short. The chance of a particular sequence with $k$ reds and $n - k$ blues is a product of fractions: the reds contribute $1 \cdot 2 \cdots k$ to the numerators, the blues $1 \cdot 2 \cdots (n - k)$, and the denominators are $2 \cdot 3 \cdots (n + 1)$ whatever the order. So every such sequence has probability $k!\,(n-k)!/(n+1)!$, there are $\binom{n}{k}$ of them, and their total is $1/(n+1)$, the same for every $k$.

Starting the urn with more balls weakens the reinforcement — a draw moves the share less — and the distribution develops a hump in the middle, as for two of each in the figure; starting it unevenly tilts the hump. The flat case is the one in which the urn’s memory is strongest.

Where the share settles #

Since each walk travels at a steady speed, the share of red settles down in every run, and the share it settles at has a distribution that the exact law already predicts. If every count from 0 to $n$ is equally likely, the share $k/n$ is spread evenly over the interval from 0 to 1, and as $n$ grows that becomes the uniform distribution.

For a general starting urn of $a$ red and $b$ blue balls, the limiting share follows the beta distribution with parameters $a$ and $b$, whose density is proportional to $x^{a-1}(1-x)^{b-1}$. The histograms match these curves for three starts, a uniform one, a symmetric hump and a decreasing curve for the urn tilted towards blue. The share is a martingale — its expected value after the next draw equals its present value, since the share of red is exactly the chance of adding a red — and a bounded martingale must converge, a fact of the same kind as the fair-game arguments in two barriers and a fair game. What the martingale property does not say is where it converges, and the answer is that it can converge anywhere, with a law set by the starting urn.

The order does not matter #

The calculation of the exact law used a fact that deserves its own figure: the chance of a sequence of draws depends only on how many reds it contains, not on the order in which they came.

The sixteen sequences of four draws fall into five groups by their number of reds, and within each group the chances are identical: every sequence with two reds and two blues has chance $1/30$, whether it is RRBB or BRBR, and every sequence with one red has chance $1/20$. A sequence of random draws with this property — every rearrangement equally likely — is called exchangeable. Independent tosses of a fixed coin are exchangeable; so are the urn’s draws, although they are far from independent, since each draw changes the chances for the next.

Bruno de Finetti proved in the 1930s that this is no coincidence. Every infinite exchangeable sequence of red and blue is a mixture of coin-tossing: there is a random bias $p$, chosen once from some distribution, and given $p$ the draws are independent tosses with that bias. For Pólya’s urn the hidden bias is uniform from one ball of each colour — beta in general — and it is exactly the limiting share of red. The urn can therefore be simulated in a second, completely different way: choose $p$ uniformly at random, then toss a $p$-coin forever. No observer of the draws could tell the two procedures apart.

That equivalence is the reason the urn sits beside Bayes as two rectangles as well as beside the walks. A person who believes the bias of a coin is uniformly distributed, and updates that belief by Bayes’s rule after each toss, predicts the next toss to come up red with probability $(r + 1)/(n + 2)$ after seeing $r$ reds in $n$ tosses — Laplace’s rule of succession — which is exactly the share of red in Pólya’s urn after the same draws. The urn is Bayesian learning written as a mechanism.

Two ways to run the same urn #

The equivalence can be checked on the smallest case. In the urn, the chance that the first draw is red is one half, and the chance that the first two are both red is $\tfrac12 \cdot \tfrac23 = \tfrac13$. In the coin picture, the chance that two tosses of a coin of bias $p$ are both red is $p^2$, and averaging $p^2$ over a uniformly chosen $p$ gives $\tfrac13$ as well. The same holds for every pattern of every length, which is what the sixteen equal-within-group chances in the figure express for patterns of four: averaging $p^k(1-p)^{4-k}$ over the uniform distribution gives $k!\,(4-k)!/5!$, the urn’s own number.

The second draw is not independent of the first: given a red first draw, the chance of red second is two-thirds, not one half. In the coin picture the reason is plain. A red first toss is evidence that $p$ is large, and a large $p$ makes the second toss likelier to be red too. The urn’s reinforcement and the coin’s unknown bias are two descriptions of one correlation, and the reinforcement is what learning looks like when it is built into the apparatus rather than performed by an observer.

The same mechanism, one urn per vertex, is the growth rule that a random tree is one part in e leaves contrasts with the uniform tree: a new point joins an existing point with probability proportional to how many neighbours it already has. Each point’s degree is reinforced exactly as a colour in Pólya’s urn is, and the hubs of preferential attachment are the urn’s runaway colours.

Returns that never stop, walks that do #

The most striking property concerns returns to the start. For an ordinary walk the chance of standing at the start after $2m$ steps is about $1/\sqrt{\pi m}$, and the expected number of returns by step $n$ grows like $\sqrt n$, which is how a walk that comes home proved the walk on a line comes home infinitely often. For the urn walk the chance of standing at the start after $2m$ steps is the chance of exactly $m$ reds in $2m$ draws, which by the flat law is exactly $1/(2m + 1)$.

Summing $1/(2m+1)$ gives a total that grows like half the logarithm of $n$ — slowly, but without limit. The expected number of returns is infinite. For an ordinary walk an infinite expectation of returns is what makes returning certain. For the urn walk it means nothing of the kind. Each walk travels at its own speed $2p - 1$, and unless $p$ is exactly one half, which happens with probability nought, the walk eventually leaves the start behind and never comes back. In two thousand simulated urn walks of twenty thousand steps, 92% made their last return within the first hundred steps, and about half never returned at all.

The two facts fit together because the average is carried by rare walks. A walk whose hidden bias happens to be very close to one half drifts away so slowly that it returns many times before it leaves, and the expected count is an average over all biases, weighted uniformly. The biases within $\varepsilon$ of one half have probability $2\varepsilon$ and contribute about $1/\varepsilon$ returns each, more or less, and summing over scales gives the logarithm. Almost every walk returns finitely often; the expectation is infinite. It is a clean example of an average that describes no typical case, of the same kind as the arcsine law of half the time is the rarest, where the average lead of a fair game is a half and a half is the least likely value.

What reinforcement does to a walk #

Set beside the walks drawn earlier in this series, the urn walk completes a contrast. The ordinary walk has no memory, spreads like $\sqrt n$ and returns forever. The self-avoiding walk remembers every site and avoids them all, and is pushed to spread faster, as $n^{3/4}$ in the plane, by a mechanism nobody has been able to analyse exactly. The urn walk remembers only its counts and is drawn towards repeating them, spreads linearly, returns finitely often, and can be solved completely, because the counts are all it remembers and the exchangeability theorem turns that memory into a single random number.

There are reinforced walks between these, and they are much harder. The edge-reinforced random walk lives on a graph and prefers edges it has crossed before, each crossing adding weight to that edge. On a single vertex with two edges it is an urn; on a line or a grid it is a family of urns, one at each vertex, that interact through the walk’s path, and whether it comes back to its start on the two-dimensional grid stood open for decades before being settled in the 2010s, through a connection with a model from statistical physics. The once-reinforced walk, which gives a fixed bonus to edges it has crossed at least once, is open on the grid.

What the figures do not show #

The simulations draw walks of a few thousand or twenty thousand steps, and the limiting statements are about infinite time; the agreement of the simulated histograms with the beta densities is checked statistically, at the level that six thousand samples allow, and the exact laws behind them are computed rather than simulated. The returns figure is exact for the expectations, and the statement that almost every walk returns only finitely often is a theorem — a consequence of each walk having a hidden bias different from one half — illustrated rather than proved by the simulation.

The figures also draw only two colours. With three or more colours the urn’s share settles to a random point of a triangle or a simplex with a Dirichlet distribution, the many-colour version of the beta law, and the walk becomes a walk in the plane that leaves along a random straight ray.

Still open: urns that remove and walks that remember edges #

Urns with other replacement rules are classified only in part. If drawing a red ball adds red balls and removes blue ones, or adds balls of both colours in fixed amounts, the urn is described by a matrix of replacement numbers, and the long-run behaviour depends on its eigenvalues: when the second eigenvalue is less than half the first, the shares are asymptotically normal, as for independent tosses, and when it is larger the fluctuations carry a random limit, as in Pólya’s own urn. The boundary cases and urns with random replacement rules are understood only in particular instances.

For reinforced walks the open problems are the recurrence questions. Whether the once-reinforced walk on the two-dimensional grid comes back to its start infinitely often is not known, and neither is the behaviour of edge-reinforced walks on many graphs between a line and the grid. The urn shows how far memory can change a walk when the memory is just two counts; the open cases are the ones where it remembers a whole picture of where it has been.