In this post I’ll tell you about a property of random walks on hyperbolic groups. To make a random walk on a group just start from the identity in the Cayley graph, then move to a neighbor with uniform probability and keep going. You have for each
a probability measure
on
telling you the probability of ending up at any given
.
is the law of a random variable
, and this sequence of random variables is referred to as (simple) random walk.
Theorem: Let be a simple random walk on a non-virtually cyclic hyperbolic group
. Then the expected Hausdorff distance between
and a geodesic connecting
to
is
.
Surprisingly, I couldn’t find this result in the literature, except for free groups (Ledrappier) [EDIT: I’ve been pointed out a reference (Corollary 3.9). The proof is quite different, but the overall aims are deeper.]. This post contains an essentially complete proof of the theorem. It’ll be a bit more technical than usual, but I just couldn’t resist blogging the full proof as it’s so short. I’m almost done writing up the same result for relatively hyperbolic groups (as well as a related result for mapping class groups). [EDIT: here it is.]
First, we show that any point on is close to a point in
. This has very little to do with random walks, it’s just a fact about paths connecting the endpoints of a geodesic in a hyperbolic space.
Lemma 1: There exists so that if the path
(say of length at leat
) connects the endpoints of a geodesic
in a
hyperbolic space and
, then
.
Another way of saying this is: hyperbolic spaces have (at least) exponential divergence.
The proof is not hard, you can find all the details in Bridson-Haefliger’s book, Proposition III.H.1.6.
The procedure is the following: you split into two subpaths of equal length and consider the triangle as in the picture:
is close to some
on one of the sides. Then you repeat using
instead of
, and if you keep going in logarithmically many steps you get to
.
And now we have to exclude the existence of large detours, something like in the following picture:
The idea is that the first and last point of the detour will be close to some point in
, and hence close to each other, the details are below. Anyway, this motivates showing that if
is at least logarithmically large, then so is
.
Lemma 2: There exists so that
.
The “” part is there just to make the proof work, but we’re happy if
for
as in the picture above, because this gives a logarithmic bound on the length of the detour.
The proof is based on the following classical inequality due (afaik) to Kesten, which holds for nonamenable groups: There exists so that
.
In words, the probability that does not make linear progress decays exponentially.
In order to prove the lemma, we just have to sum these inequalities up (using the fact that has the same distribution as
).
Fixing first (
possibilities) and letting the difference between
and
vary, we see that the probability in the statement of Lemma 2 is at most
,
and this is it, for large.
Ok, the endgame. If there are no points on at distance more than
from
we are happy. Otherwise, let
be so that
. Then each point on
is at distance at most
from either
or
. As you move from
to
along the geodesic you’ll be at first close to
and then you’ll be close to
, so at some point
you’ll be close to both. In particular, there are
so that
. By Lemma 2 (we can assume that) we have
. Hence,
is also logarithmically bounded, as well as
. The end.