## Tracking of random walks with geodesics

In this post I’ll tell you about a property of random walks on hyperbolic groups. To make a random walk on a group $G$ just start from the identity in the Cayley graph, then move to a neighbor with uniform probability and keep going. You have for each $n$ a probability measure $\mu_n$ on $G$ telling you the probability of ending up at any given $g\in G$. $\mu_n$ is the law of a random variable $X_n$, and this sequence of random variables is referred to as (simple) random walk.

Theorem: Let $\{X_n\}$ be a simple random walk on a non-virtually cyclic hyperbolic group $G$. Then the expected Hausdorff distance between $\{X_i\}_{i\leq n}$ and a geodesic connecting $1$ to $X_n$ is $O(\log(n))$.

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 $[1,X_n]$ is close to a point in $\gamma_n=\{X_i\}_{i\leq n}$. 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 $C_1\geq 1$ so that if the path $\alpha$ (say of length at leat $2$) connects the endpoints of a geodesic $\gamma$ in a $\delta-$hyperbolic space and $p\in\gamma$, then $d(p,\alpha)\leq C_1\log(length(\alpha))$.

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 $\alpha$ into two subpaths of equal length and consider the triangle as in the picture:

$p$ is close to some $p_1$ on one of the sides. Then you repeat using $p_1$ instead of $p$, and if you keep going in logarithmically many steps you get to $\alpha$.

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 $X_{i_0},X_{i_1}$ will be close to some point in $[1,X_n]$, and hence close to each other, the details are below. Anyway, this motivates showing that if $|i-j|$ is at least logarithmically large, then so is $d(X_i,X_j)$.

Lemma 2: There exists $C_2$ so that
$\mathbb{P}[\exists i,j\leq n: |i-j|\geq C_2\log(n), d(X_i,X_j)\leq |i-j|/C_2]$  $=o(n^{-2})$.

The “$|i-j|\geq C_2\log(n)$” part is there just to make the proof work, but we’re happy if $|i_1-i_2|\leq C_2\log(n)$ for $i_1,i_2$ 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 $K>0$ so that

$\mathbb{P}[d(1,X_n)\leq n/K]\leq Ke^{-n/K}$.

In words, the probability that $X_n$ 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 $d(X_i,X_j)$ has the same distribution as $d(1,X_{|i-j|})$).
Fixing $i$ first ($n$ possibilities) and letting the difference between $i$ and $j$ vary, we see that the probability in the statement of Lemma 2 is at most

$n\times \sum_{j\geq C_2\log(n)} Ke^{-j/K}\leq K n\cdot n^{-C_2/K} \times \sum_{j\geq 0} e^{-j/K}$,

and this is it, for $C_2$ large.

Ok, the endgame. If there are no points on $\alpha_n$ at distance more than $C_1\log(n)$ from $[1,X_n]$ we are happy. Otherwise, let $i$ be so that $d(X_i,[1,X_n])> C_1\log(n)$. Then each point on $[1,X_n]$ is at distance at most $C_1\log(n)$ from either $\alpha^-_n=\{X_j\}_{j or $\alpha^+_n=\{X_j\}_{j>i}$. As you move from $1$ to $X_n$ along the geodesic you’ll be at first close to $\alpha^-_n$ and then you’ll be close to $\alpha^+_n$, so at some point $p$ you’ll be close to both. In particular, there are $i_0 so that $d(X_i,X_j)\leq 2C_1\log(n)$. By Lemma 2 (we can assume that) we have $|i_0-i_1|\leq 2C_1C_2\log(n)$. Hence, $d(X_i,X_{i_0})\leq |i-i_0|$ is also logarithmically bounded, as well as $d(X_i,[1,X_n])\leq d(X_i,X_{i_0})+d(X_{i_0},[1,X_n])$. The end.

This entry was posted in random walks. Bookmark the permalink.