How rarely a walk on a group comes home

A group can be drawn as a map: one point for each element, and an edge from each point to its neighbours under a chosen set of generators. The integers with the generator 1 give a line; pairs of integers with the two unit steps give the square grid; the free group on two letters, whose elements are words in $a$, $b$ and their inverses with nothing cancelling except a letter next to its own inverse, gives a tree in which every point has four neighbours and no path ever loops back.

Put a walker on such a map and let it take one edge at a time, each of the available edges with equal chance. The question here is the simplest one a walk invites: what is the chance that after $2n$ steps it is standing exactly where it started? On the line the answer is a binomial coefficient, and on the tree it is a small calculation. The two answers behave completely differently, and Harry Kesten showed in 1959 that the difference is not about lines and trees at all. It is about the shape of the group’s balls, the subject of the edge that is as big as the ball, read off by a walk instead of a ruler.

Coming home on three lattices and a tree #

On the line a walk of $2n$ steps is home exactly when it took $n$ steps right and $n$ left, so the chance is $\binom{2n}{n}/4^n$. On the square grid the walk can be turned diagonally into two independent walks on the line, one along each diagonal, so the chance is that number squared. In three dimensions there is no such trick, but the count is a sum: choose how many of the $2n$ steps go along each axis, $2i$, $2j$ and $2k$ with $i + j + k = n$, and balance each axis.

On the tree the count is easier than it looks. What matters is only the distance from the start: from the start every step leads away, and from anywhere else one of the four edges leads back and three lead further out. So the distance performs a walk on the whole numbers that steps up with chance $3/4$ and down with chance $1/4$, and the chance of being home is the chance that this biased walk is at nought. Every number in the figure was computed that way or by the lattice counts exactly, and checked at small $n$ against brute enumeration of every path.

The figure is on a logarithmic scale, and on that scale the difference is stark. The three lattice curves bend and flatten: the chance falls like $n^{-1/2}$ on the line, $n^{-1}$ on the plane and $n^{-3/2}$ in space, powers of $n$, which are slow. The tree’s curve is a straight line: every two steps the chance is multiplied by nearly the same factor, and after 120 steps it is about $e^{-23}$, some five million times smaller than in space.

Where the powers of n come from #

The lattice powers have a one-line explanation. After $2n$ steps on the line, the walker’s position is a sum of $2n$ independent steps of $\pm1$, spread over a range of width about $\sqrt{2n}$, and by the bell-curve approximation the chance of any single position near the middle is about one over that width: $1/\sqrt{\pi n}$, which Stirling’s formula confirms for $\binom{2n}{n}/4^n$. In $d$ dimensions the walk spreads over a box of side about $\sqrt n$ in each direction, a volume of about $n^{d/2}$, and the chance of being at any one point, home included, is about one over that volume.

So on a lattice the chance of coming home is just the reciprocal of the number of places the walk is likely to be, and that number grows like a power of the time. Nothing comparable holds on the tree. There, the number of places a walk of $2n$ steps can reach grows like $3^{2n}$, but the walk does not spread over them evenly either: it concentrates at distance about $n$, on a sphere of about $3^n$ points. The chance of being home is not one over a volume; it is the chance of an atypical history in which every outward step was cancelled.

The factor per step #

The straight line on the logarithmic scale has a slope, and the slope is the natural number to attach to a walk.

Take the $2n$-th root of the chance of being home after $2n$ steps. For the lattices it creeps towards 1, because a power of $n$ is less than any exponential: its $2n$-th root tends to one, however small the power. For the tree it settles below 1, on $\sqrt3/2$. That limit is called the spectral radius of the walk, written $\rho$, and Kesten proved that for a walk on a group it always exists.

All three curves approach their limits slowly, from below. The reason is the power of $n$ that sits in front of the exponential: on the tree the chance is close to a constant times $n^{-3/2}\rho^{2n}$, and the $n^{-3/2}$ drags the root down for a long time. A finite computation never certifies a limit of this kind on its own, and the lattices’ approach to 1 is particularly slow. What certifies the tree’s value is the exact calculation behind it, which gives $\rho = 2\sqrt{k-1}/k$ for a tree of degree $k$.

Every tree #

The tree of degree four is one of a family, and the formula covers all of them.

The trees of degree three to twelve all fall exponentially, at rates the formula gives to three decimal places once the slow factor $n^{-3/2}$ is out of the way. The probabilities involved are astronomically small — at three thousand steps on the tree of degree twelve the chance of being home is about $e^{-1780}$, far below anything a computer’s ordinary numbers can hold — and the computation is carried in logarithms throughout for exactly that reason.

The formula’s edge case is worth noticing. At $k = 2$ the “tree” is the line, each point with two neighbours, and $2\sqrt{1}/2 = 1$: no exponential decay, which is the line’s polynomial return. Every degree above two gives a rate below one, falling like $2/\sqrt k$ as the tree branches more. And the same number appears far from walks: $2\sqrt{k-1}$ is the threshold that defines the best possible finite networks of degree $k$, the Ramanujan graphs, whose second eigenvalue is as small as the infinite tree allows. A finite network cannot spread a walk faster than the tree it is a quotient of, and the best ones match it.

Escaping and wandering #

The two kinds of decay come from two kinds of motion.

On the tree the distance from home goes up three times out of four and down once, so it drifts outward at an average of half a step per step. After four hundred steps the walkers in the figure are about two hundred steps from home, along paths that cannot be retraced without undoing every step. On the grid the distance drifts outward only like the square root of the time, and the walk keeps coming back, as Pólya proved it must in one and two dimensions.

To be home after $2n$ steps the tree walker must have undone every step, and the chance of the biased distance walk ending at nought is the chance of a large deviation — exponentially small, with the rate given by how much more likely the outward step is. That is where $2\sqrt{k-1}/k$ comes from: it is $2\sqrt{pq}$ for a walk stepping up with chance $p = (k-1)/k$ and down with chance $q = 1/k$, the familiar decay rate of a biased walk’s chance to be back at its start.

Whether it ever comes home #

The return probability after $2n$ steps measures something finer than whether the walk returns at all, and the two questions have different answers on the tree. On the line and the plane the walk returns with certainty, infinitely often; in three-dimensional space it returns with chance about 0.34 and then wanders off. On the tree the chance of ever returning can be computed by hand from the distance walk: from distance one, a walk stepping up with chance $3/4$ and down with chance $1/4$ ever reaches nought with chance $(1/4)/(3/4) = 1/3$, the classical gambler’s-ruin answer. After its first step every walk on the tree of degree four is at distance one, so it returns at least once with chance one third.

Space and the tree are therefore both transient, both letting most of their walks escape for good, and they differ only in how fast the chance of being home decays: like $n^{-3/2}$ in space and like $(\sqrt3/2)^{2n}$ on the tree. Transience is the coarse distinction and the spectral radius the fine one. Kesten’s theorem is about the fine one, and it is the fine one that sees the boundary.

Kesten’s theorem #

Kesten’s theorem connects that rate to the geometry of the group. Recall the measurement in the edge that is as big as the ball: take a large finite set of elements, and ask what share of it lies on its boundary — the elements with a neighbour outside. In the lattices, large balls have a boundary that is a vanishing share of the whole; in the tree of degree $k$, the outermost sphere alone is $(k - 2)/(k - 1)$ of the ball, at every size. A group in which some finite sets have an arbitrarily small boundary share is called amenable.

Kesten’s theorem is the statement that the two numbers in the figure always move together: the spectral radius of a symmetric random walk on a finitely generated group equals 1 exactly when the group is amenable. A group whose finite sets can be made almost boundaryless is one in which the walk returns subexponentially often; a group in which every finite set has a fixed fraction of boundary is one in which returns are exponentially rare.

One direction is the intuition of the drift figure made exact. If every finite set leaks a fixed share of its mass across its boundary at each step, the walk cannot stay near home: the chance of being in any fixed set decays by a fixed factor. The other direction is harder and says that small boundaries force slow decay; it uses the same functional analysis as the narrowest door that sets a chain’s pace, where Cheeger’s inequality trades an eigenvalue for the size of a bottleneck. Kesten’s theorem is the infinite version: the eigenvalue is $\rho$, and the bottleneck is the boundary of a finite set.

The free group inside the rotations of space #

The tree is not an exotic object. Two rotations of three-dimensional space about different axes, by angles that are irrational multiples of a full turn, generally satisfy no relation at all: no word in them and their inverses gives the identity unless it cancels letter by letter. They generate a copy of the free group on two letters, which is how Hausdorff found the free group inside the rotations and how the paradoxical decomposition of the ball begins.

A walk that applies one of those four rotations at random at each step is therefore a walk on the tree, at the level of words. The chance that after $2n$ steps the accumulated rotation is exactly the identity is the tree’s return probability, $(\sqrt3/2)^{2n}$ up to the power of $n$ in front. The rotations themselves, as points of the sphere of directions, spread out quickly, and that rapid spreading — fast mixing on the sphere from a group whose walk escapes like a tree’s — is the principle behind several constructions of evenly spread points on spheres, for which rotations generating a free group are chosen on purpose.

Amenable groups that still grow fast #

The theorem is about boundaries, not about growth, and the two can come apart. The line grows linearly, the plane quadratically; the tree grows exponentially, its balls tripling at every step. It is tempting to think exponential growth is what drives the walk away. It is not.

The group of maps of the line generated by “add one” and “double” grows exponentially — its balls multiply by a fixed factor every few steps — but it is amenable: there are finite sets in it whose boundary is a small share, built along the doubling direction. Kesten’s theorem then says its walk returns subexponentially often, and in fact the chance of being home after $2n$ steps decays like $e^{-c n^{1/3}}$ — faster than any power, slower than any exponential. The same $n^{1/3}$ appears for the lamplighter groups, which picture a walker on a line flipping lamps as it goes. These groups have too many elements within reach for counting their walks exactly at useful sizes, which is why they are described here rather than drawn, but they are the evidence that the theorem’s geometry is the boundary and not the growth.

What the counting cannot show #

Every probability in the figures is exact for the steps drawn: the lattice values are multinomial sums, the tree values come from the exact chain on distance, carried in logarithms, and both were checked against enumeration of every path at small sizes. The walks in the drift figure are seeded samples, there to show the motion and not to measure anything.

What the figures cannot show is a limit. The spectral radius is defined by $n \to \infty$, and the computations approach it slowly from below; for the trees the exact value is known by the calculation of the biased distance walk, and for the lattices it is known to be 1 because their return probabilities are powers of $n$. Kesten’s theorem itself, in both directions, is a statement about every finitely generated group, and no finite computation on four groups tests it.

The boundary shares in the last figure are for balls, and amenability is about all finite sets. For the lattices the balls already have vanishing boundary; for trees nothing has, since the outer sphere of every finite subtree is large. In general the sets that witness amenability need not be balls, and in the exponentially growing amenable groups they are not.

Still open: how slowly a walk can come home #

For amenable groups the return probability decays subexponentially, and how slowly is a property of the group. On the lattice $\mathbb{Z}^d$ it is $n^{-d/2}$; on groups of polynomial growth of degree $d$, Varopoulos showed, it is also $n^{-d/2}$; on the add-and-double group and the lamplighters it is $e^{-cn^{1/3}}$. Between those, a whole range of decay profiles occurs, and which profiles are possible, and which groups realise them, is not fully mapped.

There is a related question about non-amenable groups that is simpler to state and open in general. The spectral radius depends on the generators chosen, and the free group has the smallest possible value among groups with the same number of generators. Which groups and generating sets come close to that minimum — how “free-like” a group must be to make its walk escape at the tree’s rate — is understood for free products and some hyperbolic groups and not in general. And for the groups whose presentations are given by finitely many relations, deciding amenability, and so deciding whether $\rho = 1$, is not algorithmically possible at all.

A rate that measures shape #

A walk on a group knows nothing about boundaries; it just takes random steps. A boundary share knows nothing about chance; it is a ratio of counts. Kesten’s theorem says that the first, measured by how fast the chance of coming home decays, detects exactly whether the second can be made small. The line, the plane and space let their walks come home at a polynomial rate because large pieces of them are nearly all interior; the tree sends its walks away at the exponential rate $\sqrt3/2$ because every piece of it is mostly edge. The same number, $2\sqrt{k-1}/k$, then turns up as the limit on how well any finite network can mix — a geometric fact, a probabilistic one and a spectral one, which are the same fact.