The shape a random ball grows into

The polygon a lattice becomes from far away drew the balls of the square grid for several sets of moves and found that, rescaled, each converges to a polygon that can be written down in a line: a diamond for the four unit steps, an octagon for the knight. It ended on a version of the question whose answer nobody can write down. Give every edge of the grid an independent random travel time, all with the same distribution, and let the ball of radius $t$ be every point a signal from the origin can reach within time $t$. What shape does that ball grow into?

The model is first-passage percolation, introduced by John Hammersley and Dominic Welsh in 1965 to describe fluid seeping through porous rock, and its first theorem is that the question has an answer. J. Theodore Cox and Richard Durrett proved in 1981 that the rescaled balls converge, almost surely, to a fixed convex set determined by the travel-time law. The theorem says nothing about what that set is, and fifty years later it is still not known for any continuous law.

What can be done is to compute it. This essay runs the model — Dijkstra’s shortest-path algorithm on a box of up to sixty thousand points, a few hundred times — and measures the shape, the rate at which it is approached, the size of the fluctuations around it, and the one case where something is known exactly.

A ball with random roads #

The first arrival time at each point is the length of the fastest path to it, where a path’s length is the sum of its edges’ travel times. That is a shortest-path problem, and Dijkstra’s algorithm solves it exactly: settle the origin, then repeatedly settle the unsettled point with the smallest tentative time and update its neighbours. Every time in the figure is exact for the random roads drawn.

The picture is already informative. The bands of arrival time are roughly concentric and roughly round — nothing like the diamond the same grid gives when every edge takes time one. Randomness has smoothed the grid’s corners: a signal heading diagonally can pick among a great many staircase paths of equal step count and use whichever happens to be fastest, while a signal heading along an axis has fewer good options, and the two effects roughly balance. The edge of each band is ragged at the scale of a few edges, and that raggedness is the fluctuation the later figures measure.

Why a limit shape exists #

The existence of a shape rests on one inequality. Write $T(x)$ for the passage time from the origin to $x$. The fastest path to $x + y$ is no slower than the fastest path to $x$ followed by the fastest path from $x$ to $x + y$, so

$$T(x + y) \le T(x) + T(x, x + y).$$

Passage times are subadditive. Along a fixed direction, the times to $n$ times a given step form a subadditive sequence of random variables, and John Kingman’s subadditive ergodic theorem of 1968 says such a sequence, divided by $n$, converges almost surely to a constant — the time constant in that direction. Its reciprocal is the distance the ball reaches per unit time, and Cox and Durrett assembled the directions into a shape and showed the whole rescaled ball converges to it.

Convexity comes free from subadditivity too. If the ball reaches $x$ and $y$ in time $t$ each, it reaches halfway between them in time at most $t$, because the time to $\tfrac12(x+y)$ is at most half the time to $x$ plus half the time from $x$ onward, on average. And the shape inherits the grid’s symmetries: reflections in the axes and the diagonals, and quarter turns, since the travel times do not prefer any direction the grid does not.

The shape, measured #

Measuring the time to a point at distance 80 in each of thirteen directions, and averaging over runs, gives one quarter of the shape. For exponential and uniform travel times the curve is within a few per cent of a circular arc: along the diagonal it reaches between 98% and 102% as far as along the axis, which at this size is within the finite-size error of equality. For the law in which an edge takes time 1 with chance 0.8 and time 2 otherwise the shape is very different, straight near the diagonal and far inside the circle there.

Nothing forces the continuous shapes to be circles, and they are known not to be exactly circular in high enough dimensions, where Harry Kesten showed the limit shape for some laws is not a Euclidean ball. In two dimensions no law with continuous travel times is known to produce a circle, and none is known not to. What the computation shows is only that the shapes are close to round at the resolution available — close enough that deciding whether they are exactly round is out of reach of simulation.

A slow approach #

Part of the difficulty is that the limit is approached slowly. The time per step along the axis, averaged over sixty runs, falls from 0.578 at eight steps to 0.436 at a hundred and twenty-eight, and the curve has not flattened. Subadditivity explains the direction: the fastest path over $n$ steps can use detours the fastest paths over shorter stretches could not, so the average time per step can only decrease as $n$ grows, towards its limit from above. It does not explain the rate, and the rate is slow — the correction to the time per step is conjectured to decay like $n$ to the power minus two thirds, which at a hundred steps is still several per cent.

That is why every number in the shape figure is provisional. The directions approach their limits at slightly different rates, and a shape measured at distance 80 is a shape at distance 80. Exact values of the time constant are not known for any continuous law, even along the axis, and the best rigorous bounds for the exponential law are much wider than the simulation’s own uncertainty.

Fluctuations of the wrong size #

A passage time over $n$ steps is a sum of about $n$ travel times, and a sum of $n$ independent terms fluctuates by about $\sqrt n$, as the wobble of an average showed. The passage time does not. Its standard deviation grows like $n$ to a power near one third — the measured slope is 0.27 over the range computed, with the same slow approach as the mean — and at a hundred and ninety-two steps the spread is about a third of what the independent-sum estimate would give.

The reason is that the passage time is a minimum over paths, not a sum along one. The fastest path adapts to the particular random roads, routing round slow edges, and a minimum over many strongly correlated options fluctuates less than any one of them. The exponent one third is the prediction of the Kardar–Parisi–Zhang theory of growing random interfaces, the same universality class as the longest climb of a shuffle, whose fluctuations are of size $n^{1/6}$ on a mean of $2\sqrt n$ — exponent one third relative to the square root of the size. For certain exactly solvable relatives of first-passage percolation, Kurt Johansson and others proved the one-third law and identified the limiting distribution as the Tracy–Widom law. For first-passage percolation itself, with any continuous law, the exponent is not proved: the best bounds show the variance grows more slowly than $n$, by a logarithmic factor, and nothing much better.

Where a flat side appears #

For one kind of law the shape is known in part, and it has a flat side. Richard Durrett and Thomas Liggett showed in 1981 that when the smallest possible travel time is taken with high enough probability, the shape has a straight segment centred on the diagonal. With travel times of 1 or 2, the time to the diagonal point $(k, k)$ is at least $2k$, since any path there has at least $2k$ edges, and it equals $2k$ exactly when there is a path that only steps up and right using only edges of time 1.

Whether such a path exists for large $k$ is a question in oriented percolation: keep each edge with chance $p$ and ask whether an up-and-right path of kept edges runs to infinity. It does, with positive probability, exactly when $p$ exceeds a threshold — the same kind of sudden appearance of an infinite connected structure as the moment a giant appears in a random graph — about 0.6447 on the square grid. Above that threshold the time constant along the diagonal is exactly the minimum, and the same holds for an interval of directions round the diagonal, which is the flat side. The figure shows the transition: the diagonal ratio falls towards one as $p$ rises and sits at one from about 0.65 on.

The flat side is a consequence of an atom in the travel-time law — a value taken with positive probability that is also the smallest possible value. For continuous laws there is no such atom, and the shape is conjectured to be strictly convex: curved everywhere, with no straight piece at all. Strict convexity matters for more than tidiness. The derivations of the one-third fluctuation exponent assume the shape’s boundary curves, and at a flat side the fluctuations are known to behave differently.

The same model on other groups #

First-passage percolation needs only a graph and a travel-time law, and the square grid is the Cayley graph of the simplest infinite group with two generators, which is why the question sits in the picture of a group as a map. On other Cayley graphs the same subadditivity gives a time constant in every direction, but what those constants assemble into depends on the group. How fast the ball fills found that the grid’s balls grow like the square of the radius, and it is that polynomial growth which lets a rescaled ball have a limit shape in the plane: the rescaling by $1/t$ lands every ball in one fixed space.

For groups whose balls grow exponentially — the free group, whose Cayley graph is a tree, or the groups of hyperbolic surfaces — there is no such space to land in, and the edge that is as big as the ball showed why: most of an exponentially growing ball is on its boundary. The questions change accordingly, from the shape of the ball to the direction in which the fastest paths escape and the fluctuations of passage times along them, and on trees many of them have exact answers, because a tree offers exactly one path between any two points and the minimum over paths disappears. The square grid is hard precisely because it is in between: its balls grow slowly enough to have a shape and its paths are numerous enough that the fastest one cannot be written down.

The fastest paths themselves #

The shape is one object; the fastest paths that realise it are another, and they are studied as closely. A fastest path never revisits a point — a loop could be cut out to make it faster — so it is a self-avoiding path, the object a walk that may not step where it has been followed. But it is not a random self-avoiding path: it is chosen by the medium, and it wanders away from the straight line between its ends by about $n^{2/3}$, the transversal exponent that goes with fluctuations of size $n^{1/3}$ in the Kardar–Parisi–Zhang picture. That the fastest paths to far-away points in the same direction eventually coalesce, sharing a long common stretch before they separate, is proved in some settings and is part of what makes the model’s geometry rigid despite the randomness.

Where this sits among random shapes #

The model belongs to a family of random objects that grow into deterministic shapes when rescaled. The shape a random partition takes found a random staircase converging to a curve given by a formula, and in that case the curve is known exactly, because the model has an exact solution. Hammersley’s process for the longest increasing subsequence has a limit shape known exactly for the same reason. First-passage percolation is the version without a solvable structure: the shape exists by a soft argument, subadditivity, and every attempt to compute it runs into the fact that shortest paths in a random medium have no closed form.

The grid’s own ball from the lattice polygon, the diamond, is the case in which every edge takes time one: then the shape is exactly the unit ball of the $\ell^1$ norm. Adding randomness moves the shape outward towards a circle, and the measured shapes suggest it moves almost all the way. How close it gets, as a function of the law, is one of the ways the model is studied; known results bound the shape between the diamond and a larger square, and the computations show it much closer to round than those bounds require.

What the figures cannot show #

The simulations are finite. The balls are drawn on a box of about fifty thousand points, the shape is measured at distance 80 from twelve runs, and the fluctuations from a hundred and fifty runs per distance up to 192 steps. Every number carries a finite-size bias of several per cent in the direction the convergence figure shows, and a statistical uncertainty of about a per cent. The differences between the continuous shapes and a circle are the same size as those errors, so the figure cannot say whether the shapes are round.

The box also matters: paths that would leave the box are not allowed, which slightly slows the times to points near its edge. The measurements keep the target points well inside the box to limit the effect, and the trend with box size is small at the distances used.

And the oriented-percolation threshold, 0.6447, is itself known only numerically; its exact value is not known, and the transition in the diagonal figure is blurred by the finite distance, as every percolation threshold measured on a finite grid is.

Still open: the shape, and whether it is round #

For no continuous travel-time law on the square grid is the limit shape known, and it is not known whether any of them is strictly convex, whether any is a circle, or whether the boundary has the curvature the one-third fluctuation law needs. The fluctuation exponent itself is conjectured to be one third for every law with a strictly convex shape and is not proved for any. Even the qualitative statement that the fluctuations are of smaller order than $\sqrt n$ by a power — rather than by the logarithm that has been proved — is open.

These are among the central open problems of random growth, and they are open for the same reason as the shape itself: the passage time is a minimum over exponentially many paths, and outside a handful of exactly solvable cousins there is no formula for the minimum. The plain lattice gave its shape in a line; adding a little randomness gives a shape that has resisted half a century of effort.

A shape that exists and cannot be named #

The theorem of Cox and Durrett is an unusual kind of result: it proves that a specific convex set exists, determined completely by the travel-time law, and gives no way to compute any point of its boundary. The simulations draw it to a few per cent and find it nearly round, with a flat side only when the law has an atom at its minimum, a slow approach to its limit and fluctuations of the size a whole class of random growth models share. The grid’s diamond was the answer when the roads were identical; with random roads the answer is a curve that everyone can see and nobody can write down.