Asymptotic length of reduced word on free group with replacements

This seems to be an elementary question, but it's proving hard for me to just Google. Suppose you have a sequence which picks elements out of $\{a, a^{-1}, b, b^{-1}, c, c^{-1}\}$ with equal probability. After, say, seven steps you'll get words like $a b c c^{-1} a c b^{-1} $ which in this case reduces to $a b a c b^{-1} $ after canceling inverses. My question is this: if I write $c$ as some string of $a, a^{-1}, b, b^{-1}$, (and write $c^{-1}$ as the inverse of that) are there any theorems about the expected length of the new sequence after reduction? For example, I could take $c = a^{-1} b b$ so my previous word becomes just $ab b$. I care mostly about the case of a very long word.

Solution 1:

The keywords are random walks on (hyperbolic) groups and speed of escape. There are many references on the subject (e.g. this one, although it's likely to be too general for your problem), and the precise result you seem to be interested in is a theorem by Kesten (1959).

Setting

Let $F_2$ be the free group on two generators. Let us consider a sequence of i.i.d. $F_2$-valued random variables $(X_k)$, with $\mathbb{P} (X_0 = d) = 1/6$ for $d\in \{a,a^{-1}, b, b^{-1}, c, c^{-1}\}$ (replace $c$ by any word in $a$, $b$ you like). Note that the $X_k$'s are symmetric: $X_k^{-1}$ has the same distribution as $X_k$, and the support of their distribution generates $F_2$.

Define a random walk on $F_2$ by taking $S_0 := e$, and $S_{n+1} = X_n S_n$.

The group $F_2$ is endowed with the word metric, that is $d(e, g)$ is the length of the shortest way to write $g$ as a product of the generators $a$, $b$ and their inverses. What you are interested in is $d(e, S_n)$.

Observations

Note that $d(e, S_{n+m}) \leq d(e, S_n)+d(e, S_m)$. Hence, the stochastic process $(d(e, S_n))_{n \geq 0}$ is subadditive. Some general results of ergodic theory (e.g. Kingman's subbaditive theorem which is a generalization of the law of large numbers) tells you that there is a real $\ell \geq 0$ such that, almost surely,

$$\ell = \lim_{n \to + \infty} \frac{d(e, S_n)}{n}.$$

Not that this is true for any discrete group (with a left-invariant metric) and any random walk with bounded steps. However, the limit can easily be $0$; indeed, if you take a simple random walk on $\mathbb{Z}^d$, then the central limit theorem tells you that $d(e, S_n)$ is of the order of $\sqrt{n}$, and thus grow sub-linearly.

(Non)-amenable groups

At this point, it is useful to distinguish between two kind of groups: those which are amenable, and those which are not. While there are many equivalent definitions, I'll just give two criteria:

• if a discrete group has polynomial (or sub-exponential) growth, then it is amenable. For instance, a ball of radius $n$ in $\mathbb{Z}^d$ has $\sim n^d$ elements, so $\mathbb{Z}^d$ has polynomial growth.

• If a discrete group contains a copy of $F_2$ as a subgroup, then it is not amenable.

A theorem of Kesten

It turns out that non-amenability is exactly what we need to get a linear rate of growth!

Theorem (Kesten)

Let $G$ be a finitely generated group. Let $(S_n) = (X_{n-1} \ldots X_0)$ be a random walk on $G$. Let $\mu \in \mathcal{P} (G)$ be the distribution of $X_0$. Assume that the support of $\mu$ is bounded, and generates $G$. Assume furthermore that the random walk is symmetric, i.e. $X_0 \equiv X_0^{-1}$ in distribution. Then $\ell >0$ if and only if $G$ is non-amenable.

Your problem fits perfectly this framework. In other word, no matter what $c$ you choose, almost surely, the length of the reduced words shall grow linearly (with a speed $\ell$ which depends only on $c$).

I guess that the next step would be to find $\ell$ as a function of $c$, and even get a more elementary proof for given (not too long) $c$. That said, before going to the specifics, I believe that a rough picture of the general theory is useful.