A cluster grown by random walkers

Box counting turns a shape into a growth rate, and for the Koch curve or the Cantor set the rate can be computed from the rule that builds the set. Some fractals have no such rule. They are grown by a process, and the dimension has to be read off what the process produces, with nothing to check it against.

The cleanest example is a rule Thomas Witten and Leonard Sander proposed in 1981. Put one particle at the origin of a square grid. Release a second far away and let it take random steps — up, down, left or right, each equally likely — until it lands next to the first, and freeze it there. Release a third, and let it wander until it touches either of the two. Continue. Nothing in the rule mentions branches, shape or scale.

The result is all branches. Twenty thousand particles make a tree that reaches 303 lattice steps from its seed, while the same number packed into a disc would reach only about eighty. Its mass inside radius $r$ grows like $r^{1.7}$, between a line and a filled region, and every simulation in forty years has found the same exponent. The best theorem says only that it is at least $3/2$.

Why the tips win #

The branching has a simple cause, and it is visible in the colours. The particles that arrived last — orange — are almost all on the outermost tips. A walker coming from far away meets the outer parts of the cluster first, and to reach a hollow between two branches it has to wander deep into the gap without touching either side, which a random walk almost never manages. So a tip that sticks out a little gets more new particles than its neighbours, sticks out further, and gets more still. The hollows, called fjords, are screened.

That instability is the same one that makes a flat front unstable whenever growth is fed by diffusion: electrodeposited metal grows in branching trees from an electrode, a low-viscosity fluid pushed into a high-viscosity one fingers out instead of advancing flat, crystals of a mineral grow as dendrites in a crack. Witten and Sander’s model is the simplest process with this instability and nothing else, and its shapes resemble all of them. The instability was analysed for smooth fronts by William Mullins and Robert Sekerka in 1963: a flat surface growing by diffusion is unstable to bumps of every wavelength longer than a cutoff set by surface tension, which smooths small bumps away. The walker’s rule has no surface tension at all — a particle sticks wherever it first touches — so bumps of every size are unstable down to the lattice spacing, and the cluster branches at every scale it has. The walker is the diffusing material, and its first contact with the cluster is where growth happens.

Mass that grows like a fractional power #

A dimension can be measured three ways from one cluster, and the first is the most direct: count the particles within distance $r$ of the seed and see how the count grows.

For a filled disc the count grows like $r^2$, and the comparison cluster here, grown by adding a uniformly random empty neighbour at each step with no walking, has slope 2.01 — Murray Eden’s model of 1961, which grows compact blobs with ragged edges. The aggregate’s count grows like $r^{1.68}$ between radius 8 and 128. That is the mass dimension. It says that doubling the radius multiplies the mass by $2^{1.68} \approx 3.2$ rather than 4, and the factor is the same at every scale in the range, which is what self-similarity means for a random object: not that a part looks exactly like the whole, but that the statistics of parts and whole agree.

For the self-similar sets built by rules, the mass dimension, the box-counting dimension and Hausdorff’s dimension, defined by the cheapest covers, all coincide, and that agreement is a theorem about sets made of scaled copies of themselves. For sets built from unequally stretched copies they can disagree, and for a random cluster there is no theorem either way: the agreement has to be measured.

The value most often quoted for two-dimensional aggregation is about 1.71, from clusters of millions of particles grown in many independent runs. One cluster of twenty thousand gives 1.68 by this method, and the difference is within the scatter between individual clusters.

A radius between a disc and the only proof #

The second method follows the cluster as it grows. After $n$ particles, the radius of gyration — the root-mean-square distance of the particles from their own centre — is some number, and if the cluster has dimension $D$ then $n$ grows like that radius to the power $D$.

Over the last decade of growth the radius grows like $n^{1/1.74}$, giving a dimension of 1.74 — consistent with the mass method and with the literature, and a reminder that two estimates from the same cluster still differ in the second decimal. The figure also draws two reference slopes. A filled disc has radius growing like $n^{1/2}$. Harry Kesten proved in 1987 that the aggregate’s radius after $n$ particles grows no faster than about $n^{2/3}$, which means its dimension is at least $3/2$.

That bound is the only rigorous statement about the dimension of two-dimensional aggregation. The obvious upper bound, 2, is trivial and is not known to be strict: nobody has proved that the cluster is genuinely thinner than a filled region, though every simulation shows it is. The measured 1.7 sits between Kesten’s bound and the filled disc, nearer neither, and the gap between what is computed and what is proved has not narrowed in thirty-five years.

A dimension that depends on the box #

The third method is the one used for Koch curves: cover the cluster with boxes of side $\varepsilon$ and count how many are needed. Here the method shows something the others hide.

At the smallest boxes the slope is near 1, because at that scale the cluster is a tangle of branches one particle thick, and a thin branch is a curve. As the boxes grow the slope climbs, peaks at 1.68 between boxes of 16 and 32 steps, and then wavers as the boxes become so few that they see the whole cluster as a blob. So the cluster is fractal over a range of scales, from a few lattice steps to a fraction of its radius, and outside that range it looks like something else — a curve below, a dot above. A dimension estimated from too narrow a range, or from the wrong part of the range, is wrong, which is exactly the problem of telling a crossover from a curve in a measured record. Bigger clusters widen the range; no finite cluster makes it infinite.

The three methods are measuring the same quantity in principle and different quantities in practice. Mass against radius looks outward from the seed; the radius of gyration follows growth in time; box counting looks at the frozen shape at every scale. That they agree to within a few hundredths is evidence that the cluster really has a dimension, rather than a proof that it does — and for a random process with no rule to compute from, agreement between methods is the only evidence there is.

A few sites take almost every walker #

The screening that makes the branches can be measured directly. Freeze the finished cluster, release walkers far away as before, and record where each one first lands next to the cluster, without letting it stick.

Half of all first contacts land on the busiest 0.9 per cent of the perimeter sites, and 94 per cent of the sites are never touched by any of the eight thousand walkers — against 72 per cent that a sample of this size would miss if every site were equally likely. The distribution of first contacts is the cluster’s harmonic measure: the probability, for each part of the boundary, that a walker from far away reaches it first. It is also the electric charge an electrically conducting copy of the cluster would carry on each part of its surface, which is why lightning rods are pointed and why the same mathematics describes electrodeposition.

Harmonic measure on a jagged boundary is extraordinarily concentrated, and it has its own theory. Nikolai Makarov proved in 1985 that on any boundary in the plane, however rough, harmonic measure lives on a set of dimension exactly one — it cannot spread itself over a set as large as the boundary when the boundary is fractal. On the aggregate the concentration has a whole spectrum of strengths, from the tips where it is enormous to the fjords where it is negligible, and the multifractal spectrum of a measure that crowds at different rates is the natural description of it. The cluster’s dimension and its harmonic measure are two faces of one object: the shape determines where the walkers land, and where the walkers land determines how the shape grows.

The walk is what makes the branches #

The role of the walk is clearest when it is removed. Eden’s rule grows a cluster by the same steps in the same order — one new particle next to the cluster each time — but chooses the site uniformly among all empty neighbours instead of by where a walker arrives.

The two clusters have the same number of particles, and the aggregate’s radius is three times the Eden cluster’s. Eden’s rule gives every exposed site the same chance, so a site in a hollow is as likely to fill as a site on a tip, and hollows fill in: the cluster is compact, with a rough boundary whose roughness is its own well-studied subject, the shape a random growing ball takes. The walker’s harmonic measure gives tips almost everything, and nothing fills the hollows. One change in how the next site is chosen moves the dimension from 2 to about 1.7.

A dial between the blob and the tree #

Eden’s rule and the walker’s rule are the two ends of a family. In 1984 Lucien Niemeyer, Luciano Pietronero and Hans Wiesmann proposed a model of electrical breakdown — the branching discharge that cuts through an insulator — in which each perimeter site grows with probability proportional to its harmonic measure raised to a power $\eta$. At $\eta = 0$ every site has the same chance and the rule is Eden’s; at $\eta = 1$ the chances are the harmonic measure itself and the rule is equivalent to the walker’s; for larger $\eta$ the tips win even more decisively, and the clusters become sparser, with dimension falling towards one as the growth concentrates on a few needles.

The family makes the dimension a function of how strongly growth favours the tips, and it shows that 1.7 is not a magic number of two-dimensional growth but the value at one particular setting of the dial — the setting that diffusion produces. A continuous range of values between one and two is reached as the setting changes, and which one a physical system shows depends on how its growth rate depends on the field around it.

The opposite extreme to all of them is growth with no randomness at all. A pile of sand toppled by a fixed rule from a single cell grows a shape with intricate fractal patterns inside a nearly round boundary, deterministic in every grain; the walker’s aggregate is random in every particle and statistically self-similar instead. Both are grown by local rules, and their large-scale shapes have nothing in common.

Why random walks reach the cluster at all #

There is a quiet assumption in the rule: a walker released far away eventually touches the cluster. In two dimensions that is true for a deep reason, Pólya’s theorem that a random walk on the plane returns home — every point of the plane is visited eventually, and in particular the neighbourhood of the cluster is. In three dimensions a walk can escape for ever, and three-dimensional aggregation is defined by releasing walkers on a sphere around the cluster and discarding those that wander off; its clusters have dimension about 2.5.

The simulation here uses two standard economies. A walker far from the cluster cannot touch it in fewer steps than its distance, so it is moved in one jump to a random point at that distance, which approximates in distribution the steps it would have taken. And a walker that wanders much further away than it started is released again from the launching circle, which slightly distorts the far-field distribution but not the near-field one that decides where walkers land. Both are standard in simulations of aggregation, and both are designed to leave unchanged the statistics close to the cluster, where growth is decided.

What the simulations cannot settle #

The dimension 1.7 is a measurement, and no measurement has turned it into a theorem. The figures show one cluster of twenty thousand particles; each method has a range of validity set by the cluster’s size and the lattice’s spacing; and the literature’s 1.71 rests on far larger clusters but is the same kind of statement. Whether the dimension is a single well-defined number — whether large clusters are genuinely self-similar in law, rather than slowly changing their statistics as they grow — is not proved. There have been serious suggestions that very large clusters change shape slowly, influenced by the square lattice’s axes, and on-lattice clusters of millions of particles do grow faint diamond-shaped anisotropy, while off-lattice simulations do not.

The lattice itself is a choice. The figures use the square lattice, and the branches show a slight preference for the axes. Off-lattice aggregation, with particles as small discs moving in continuous random directions, gives the same dimension to within the precision of simulations, which is evidence that 1.7 is a property of diffusion-limited growth rather than of the grid. It is not a proof of that either.

Finally, the harmonic-measure figure counts first contacts of eight thousand walkers, and with more walkers fewer sites would be untouched. The comparison with the even case corrects for that, but the precise share of sites that harmonic measure effectively ignores is a sampling estimate, not an exact value.

Still open: a proof that the cluster is thin #

Is the dimension of two-dimensional diffusion-limited aggregation strictly less than two? Kesten’s bound shows it is at least $3/2$; nothing shows it is less than two. A proof would have to show that the screening seen in every simulation is strong enough, with probability one, to keep the cluster from filling space at large scales — a statement about harmonic measure on a random, evolving boundary, of a kind that probability theory has few tools for.

A related model has made progress. Matthew Hastings and Leonid Levitov proposed in 1998 to grow clusters by composing conformal maps, each adding a small bump where a randomly chosen point of harmonic measure lands; for some versions of their model the scaling limits have been identified rigorously, and the hope is that one variant captures aggregation. So far the variants that can be analysed are the ones whose clusters do not branch, and the branching variant, the one that looks like the picture at the top, remains as unproved as the original.

A dimension measured, not proved #

A cluster grown by random walkers that freeze on first contact has mass growing like $r^{1.7}$: three methods on one cluster of twenty thousand particles give 1.68, 1.74 and a box-counting peak of 1.68, and the literature’s value is about 1.71. The cause is screening: half of all walkers land on under one per cent of the boundary, so tips grow and fjords stay empty, and replacing the walk by a uniform choice of site gives a compact blob of dimension 2. The only theorem is Kesten’s, that the dimension is at least $3/2$; that it is less than two is believed by everyone and proved by no one.