Where a random walk leaves the snowflake

The exponent a staircase shares with its set ended with measures that no self-similar rule produces. A measure built by splitting mass in fixed proportions, again and again, has local exponents that can be computed in closed form; a measure that arises from some other process has exponents that are well defined almost everywhere and known only in special cases. The sharpest example it named was harmonic measure: the measure on the boundary of a region that records where a random walk started inside first touches the edge. Nikolai Makarov proved in 1985 that for every simply connected region in the plane, however wild its boundary, harmonic measure lives on a set of dimension exactly one.

This essay measures that theorem on the region whose boundary is the best-known fractal of all. The Koch snowflake’s edge has dimension $\log 4/\log 3 \approx 1.262$ — each piece is four copies of itself at a third of the size, which a dimension that is not a whole number turned into a dimension by counting. A random walk does not see that edge evenly. It arrives at some places far more often than others, and the places where it arrives form a thinner set than the edge, of dimension one, as Makarov says. The figures find the walks’ dimension at $0.98$ from inside and $1.00$ from outside, find where on the edge the walks go, and find that from inside and from outside they go to opposite places.

A walk that jumps across circles #

Harmonic measure is defined by Brownian motion, the continuous limit of a random walk with ever smaller steps, and simulating Brownian motion step by tiny step until it reaches a fractal edge would take a great many steps. There is a shortcut, published by Mervin Muller in 1956 and called the walk on spheres. Brownian motion started at the centre of a disc leaves the disc through a point of its circle that is uniformly distributed, by symmetry. So from the current position, draw the largest circle about it that stays inside the region, jump to a uniformly random point of that circle, and repeat. Each jump is where an actual Brownian path would have crossed that circle, so the sequence of jump points is a subsequence of a genuine Brownian path, and it ends wherever that path would have ended. The walk stops when it comes within a small distance of the edge, here $10^{-5}$ on a snowflake whose smallest segments are $3^{-6} \approx 0.0014$ long.

The one expensive operation is the radius: the distance from a point to a boundary of $3 \times 4^6 = 12{,}288$ segments. It is found without examining most of them, using the snowflake’s own construction. Each Koch piece between two points $a$ and $b$ lies inside the disc with $ab$ as diameter, so a piece whose disc is farther than the nearest segment found so far cannot hold anything nearer and is never opened. The search descends the construction, opening the nearest pieces first, and touches a few dozen segments rather than twelve thousand.

The four walks drawn took 21, 10, 14 and 25 jumps, and the 60,000 walks behind the rest of the figures took $19.96$ on average. The radius does not fall steadily: a walk can land deep in a channel of the snowflake and then be thrown out into open space by the next jump, and the lines in the figure rise as well as fall. But near the boundary each jump has a fixed chance of halving the distance, which makes the number of jumps grow only with the logarithm of the required accuracy. Asking for a hundred times greater accuracy costs a few more jumps, not a hundred times as many, which is why the method can afford sixty thousand walks on a boundary this intricate.

Where the walks arrive #

The hero figure sorts the arrivals into the 768 pieces of the boundary at the fourth stage of the construction. By symmetry each of the three sides must receive a third of the walks, and the counts agree with that to within a fraction of a per cent, which is a check on the walk and on the segment bookkeeping together. Within a side the arrivals are anything but even. The busiest tenth of the pieces received 63 per cent of all the walks, and seventy-one of the 768 pieces received none at all in sixty thousand tries.

The warm pieces in the figure sit in a definite place: along the walls that lead into the snowflake’s inward corners, where two arms of the snowflake meet and the inside opens out round an angle of $240°$. The pieces at the outward tips, where the inside narrows to a $60°$ point, are almost never reached. That is the first and most robust fact about harmonic measure, and it holds for any corner, fractal or not. Near a corner whose angle, measured inside the region, is $\beta$, the chance of first arriving within distance $r$ of the corner scales like $r^{\pi/\beta}$. At a $60°$ tip the exponent is $3$, so the tip is a very poor target; at a $240°$ notch it is $3/4$, smaller than one, so the notch collects more than its length’s share. A random walker from inside is drawn to the places where the region bulges inward and kept away from the places where it pokes out.

Inside and outside see opposite edges #

Harmonic measure can also be taken from outside, as the place where Brownian motion started very far away first touches the snowflake. That is what two rays for every fraction measured for the Mandelbrot set, as the share of external angles landing in each limb. Here it is sampled by starting walks uniformly on a circle round the snowflake — which is where Brownian motion from infinity first meets that circle — and returning any walk that strays far away to the circle at a point drawn from the exact law for its return.

The two curves are mirror images. A corner that is a $240°$ notch from inside is a $120°$ point from outside, and a $60°$ tip from inside is a $300°$ bay from outside, so the exponents swap roles. The two pieces at a side’s central inward notch took $9.2$ per cent of that side’s inside walks and not one of the forty thousand walks from outside. The two pieces at the side’s central tip took $0.01$ per cent of the inside walks and $4.2$ per cent of the outside ones. The two measures live on different parts of the same curve, and either could be called “the” distribution of a random arrival.

What they share is the next measurement, and it is the one Makarov’s theorem is about. Both measures concentrate, and they concentrate onto sets of the same size.

A measure that is also a charge and a temperature #

Harmonic measure has three readings, and the figures can be read through any of them. The first is the one drawn: where a random walk first arrives. The second is the solution of the Dirichlet problem. Fix a temperature on the boundary — hot on one piece, cold everywhere else — and let heat settle; the steady temperature at the centre is exactly the harmonic measure of the hot piece seen from the centre. The steady temperature is a harmonic function, one whose value at every point is the average of its values on any circle round that point, and that averaging property is the walk on spheres read backwards: the temperature at a point is the average over the circle the walk jumps to. The same averaging drew a graph without crossings in every point at the average of its neighbours, where it is Tutte’s method, and it is the steady state of the flow that the corners go first followed towards equilibrium.

The third reading belongs to harmonic measure from outside. Put an electric charge on a conductor shaped like the snowflake and let it spread to equilibrium: the charge sits on the surface in exactly the proportions of harmonic measure from infinity. So the outside walks’ preference for the tips is the reason lightning conductors are pointed. Charge crowds onto sharp convex points, the field near them is strong, and the walks from far away, which are the field lines run backwards, arrive there disproportionately. The inside walks prefer the notches for the same reason inverted: from inside, a notch is the convex side. That the two measures are mirror images is the statement that a conductor’s inside and outside see opposite curvatures in the same boundary.

The random walk is the cheapest of the three to compute on a fractal, which is why it is the one drawn. Solving the heat or charge problem by a grid would need a grid finer than the snowflake’s smallest segment everywhere in the region, millions of cells for a sixth-stage snowflake, while each walk touches only the few dozen circles it jumps across. That is the same economy that makes a random walk come home a model of diffusion: the walk is the microscopic process, and the smooth equations describe its averages.

Counting the spread, level by level #

The dimension of a measure can be read from how its entropy grows as the boundary is cut more finely. At level $l$ the boundary is $3 \times 4^l$ pieces, each $3^{-l}$ long, and the entropy $-\sum q \ln q$ over the pieces’ shares $q$ measures how many pieces the measure effectively uses: $e^H$ of them. Going down one level multiplies the length scale by $1/3$. If the effective number of pieces grows by a factor of $3^D$ at each level, the measure has dimension $D$, and the entropy grows by $D \ln 3$.

The even measure, which gives every piece of the edge the same share, gains $\ln 4 = 1.386$ a level: it uses every piece, four times as many at each level, and its dimension is the edge’s, $1.262$. The walks start out the same way — the first level is forced by symmetry, each side’s four pieces receiving almost equal shares — and then fall behind. Between levels 2 and 5 the inside walks gain $1.078$ a level, which is $0.98 \ln 3$, and the outside walks $1.096$, which is $1.00 \ln 3$. Both are dimension one, to the accuracy sixty and forty thousand walks allow, on a curve of dimension $1.26$.

The levels used are chosen with care. At level 1 the measure has not yet started to concentrate, and at level 6, with 12,288 pieces and only sixty thousand walks, the counts in individual pieces are too small for the entropy to be trusted: an undersampled entropy is always too low, because pieces that should have a few walks show none. Levels 2 to 5 lie between, and there the gain per level is stable. A larger sample would push the reliable range one level deeper, at four times the cost.

A local exponent for every piece #

Entropy averages over the whole boundary. The local exponent of a piece shows the spread behind the average: how fast the share of walks shrinks as the piece is cut finer. For each piece at level 4, compare its share with the share of the piece two levels up that contains it, which is nine times as long; if the share has shrunk by $9^{\alpha}$, the piece has local exponent $\alpha$. The even measure gives every piece the same exponent, $\log 16/\log 9 = 1.262$, since the share is divided among sixteen pieces when the length is divided by nine.

The harmonic measure’s exponents are spread over a wide range, from below a half to nearly three, and the two ways of counting them tell different stories. Counted by pieces, the bulk lies to the right of $1.26$: most pieces of the boundary receive far less than their length’s share, many receiving almost nothing. Weighted by the walks — counting each piece as often as walks arrive there — the exponents gather to the left and average $0.98$. That is the content of Makarov’s theorem in a form the figures can show. The walks are concentrated on a set of pieces whose share shrinks exactly as fast as their length does, and the rest of the boundary, though it is most of the boundary by any count of pieces, carries a vanishing share.

The same spread of exponents organised a dimension for every rate of crowding, where a self-similar measure had a whole spectrum of local exponents with an exact formula. Harmonic measure on the snowflake has a spectrum too, and its shape has been studied numerically and in special cases, but there is no closed formula for it, because the walk’s preferences at each scale depend on the whole shape of the region rather than on a fixed splitting rule.

Fewer and fewer pieces #

A dimension of one on a curve of dimension $1.26$ has a plain consequence. At level $l$ there are $4^l$ pieces per side, but a measure of dimension one should need only about $3^l$ of them to hold most of its mass, so the share of pieces that matter should fall by a factor of about $3/4$ a level.

At level 1, eleven of the twelve pieces are needed to hold nine tenths of the walks. At level 2 it is 58 per cent of the pieces, at level 3, 36 per cent, at level 4, 28.5 per cent, and at level 5, 21.8 per cent. Half the walks are held by 4.5 per cent of the pieces at level 5. The fall is close to three quarters a level from level 3 on, as dimension one predicts, and the trend has no reason to stop: at every finer level, a smaller fraction of the boundary carries the walks. In the limit, the walks land on a set of zero length in the snowflake’s own sense — a set the even measure assigns nothing to — and yet they land somewhere every time.

What the walks cannot show #

Sixty thousand walks are a sample, and three things about the measurement are not settled by it. The first is the limit. A dimension is a statement about infinitely fine cutting, and the entropy was measured at five levels; the gain per level could drift at levels the sample cannot reach. Makarov’s theorem says it does not, for any simply connected region, and the figures are consistent with the theorem rather than a proof of it.

The second is the stopping distance. Every walk was stopped $10^{-5}$ from the edge, which means that the measure recorded is the measure of a slightly blurred boundary, and on a fractal the blur is not innocent: a walk that would have entered a fine channel is stopped at its mouth. At the levels used, pieces are hundreds of times longer than the stopping distance, so the blur is far below the resolution of any figure here, but it would matter if the same walks were cut into much finer pieces.

The third is the snowflake itself. The boundary drawn is the sixth stage of the construction, not the limit curve. Its smallest features are the finest pieces of the counting, and the experiment says nothing about what harmonic measure does on structure finer than that. The exponent at a single corner is a theorem about the limiting shape; that the counts near the corners behave this way at finite stages is a measurement.

Still open: the dimension in space #

Makarov’s theorem is special to the plane. Its proof uses the Riemann mapping theorem — the conformal map from a disc onto any simply connected region — and the way such maps distort lengths. In three or more dimensions there is no such map, and the question changes character. Jean Bourgain proved in 1987 that in space of dimension $d$ harmonic measure always lives on a set of dimension strictly less than $d$, by a fixed amount that does not depend on the region. The exact value of that bound in three dimensions is not known, and nor is the smallest dimension that harmonic measure on some region can be forced to have.

There are open questions in the plane as well. For regions that are not simply connected — the outside of a Cantor dust, say, which is many pieces — harmonic measure can have dimension less than one, and Peter Jones and Thomas Wolff proved in 1988 that it is never more than one; how much less it can be for a given kind of set is understood only in special families. And for the snowflake itself, the full spectrum of local exponents, which the counted-by-pieces bars only hint at, has no exact description.

Thinner than the edge #

The snowflake’s edge is a curve of infinite length, four times longer at every refinement, and of dimension $1.262$ — thicker than any smooth curve. A walk from the centre arrives at a point of it chosen by no rule a person would invent: preferring the notches, avoiding the tips, ignoring most of the length. What it picks out, taken over all walks, is a set of dimension one, the dimension of a smooth curve.

That coincidence is not about the snowflake. The same number would come out for the Mandelbrot set’s boundary, whose dimension is two, and for any other simply connected region in the plane. The error that does not care how many dimensions found Monte Carlo sampling indifferent to the dimension of the space it worked in; here a random walk is indifferent to the dimension of the boundary it lands on, and Makarov’s theorem is the precise statement of that indifference.