17
$\begingroup$

Let $w$ be a word of length $2\ell$ chosen at random on the alphabet $\{x_1,x_1^{-1},x_2,x_2^{-1},\dotsc,x_k,x_k^{-1}\}$. By the reduction $\rho(w)$ I mean what you obtain by deleting substrings of the form $x_i x_i^{-1}$ or $x_i^{-1} x_i$ (and repeating, and repeating, until you cannot do it further).

What is the probability that the length of $\rho(w)$ is at most $2 s$, where $s\leq \ell$ is given?

(In the special case $s=0$, there is a good (indeed optimal in the limit $\ell\to \infty$) bound due to Kesten ("Symmetric random walks on groups", 1959).)

$\endgroup$
6
  • $\begingroup$ Sorry if this is a silly question, but why are you only considering words of even length? Doesn't the problem still make sense if you replace $2\ell$ by $\ell$ and $2s$ by $s$? $\endgroup$ Jul 17, 2012 at 13:25
  • 1
    $\begingroup$ @Michael: if you replace $2l$ by $l$ and $2s$ by $s$, you would have to assume that $l$ and $s$ are of the same parity. You cannot get a word of even length by cancelation from a word of odd length. With $2l$ and $2s$ you avoid this problem. $\endgroup$
    – user6976
    Jul 17, 2012 at 13:32
  • 1
    $\begingroup$ @Mark: I know, but couldn't you also ask the question for $2\ell +1$ and $2s + 1$? I was wondering if there was any reason for considering only the even length words if the odd length case also makes sense. $\endgroup$ Jul 17, 2012 at 13:50
  • 6
    $\begingroup$ Completely off topic, but using characters from different fonts (script $\ell$, italic $s$) for the same purpose (indices) makes my heart sink. Anyone who says this is to avoid confusion between a $1$ and an $l$ needs glasses. $\endgroup$
    – J.J. Green
    Jul 17, 2012 at 14:59
  • 10
    $\begingroup$ @J.J. Green: In many fonts, the difference between some of 1, l, I, i, | is hard to tell. Even with glasses, which I wear since childhood. Worse, indices tend to occur in subscripts, in smaller font. Classic example: l and I in Computer Modern, the default (La)TeX font. I find $C_I$ and $C_l$ difficult to distinguish there (and on this website, too). Yes I can distinguish them when focusing, but a single mixup when reading can cause lots of confusion. Hence many people use \ell instead of l. If you have a better solution (note that you usually can't choose fonts in journals), please tell! $\endgroup$
    – Max Horn
    Jul 18, 2012 at 11:16

3 Answers 3

11
$\begingroup$

Adding a random generator or inverse to the end of a nonempty word has a $\frac {2k-1}{2k}$ chance of increasing the reduced length by $1$, and a $\frac{1}{2k}$ chance to decrease the reduced length by $1$. The empty word is always increased in length by $1$.

The walks from $0$ to $2t$ of length $2n$ on the nonnegative integers can be counted by the reflection principle as ${2n \choose n-t} - {2n \choose n-t-1}.$

The probability that the reductions of the prefixes of a word follow a particular walk $W$ is $$\frac {(2k-1)^{n+t}}{(2k)^{2n}} \bigg(\frac{2k}{2k-1}\bigg)^{a(W)}$$

where $a(W)$ is the number of times the walk visits $0$ before the endpoint. $a(W)$ is between $1$ and $\min(n-t+1,n)$. Walks with a fixed value of $a(W)$ can be enumerated, but even without doing so, we get the following estimates for the probability that the length of the reduced word is $2t$:

$$1 \le \frac{2k}{2k-1}\le\frac{Prob(2t)}{\bigg({2n \choose n-t} - {2n \choose n-t-1}\bigg) \frac {(2k-1)^{n+t}}{(2k)^{2n}}}\le \bigg(\frac{2k}{2k-1}\bigg)^{n-t+1} \le \exp\big(\frac{n-t+1}{2k-1}\big).$$

$\endgroup$
9
$\begingroup$

(Edit : added something for big values of $s$).

An easy upper bound that generalizes Kesten's bound is given by $(\sqrt{2k-1}/k)^{2\ell} \sqrt{N_s}$ where $N_s$ is the number of reduced words of length at most $2s$. As noted in the comments, this in only interesting if $s$ is not to close to $\ell$.

Proof: Let $A$ denote the generator of the random walk on $F_k$, i.e. $A = \frac{1}{2k} \sum_{i=1}^k \lambda(g_i) + \lambda(g_i^{-1}) \in B(\ell^2 F_k)$, $\lambda$ is the left regular representation. To avoid confusion I denote by $|\cdot|$ the norm in $\ell^2 F_k$ and $\|\cdot\|$ the operator norm on $B(\ell^2 F_k)$. Then Kesten's theorem is that $\|A\|=(\sqrt{2k-1}/k)$. And the probability you are loooking for is $\langle A^{2\ell} \delta_0,\sum_{|\omega|\leq 2s} \delta_\omega\rangle$, which is less than $\|A^{2\ell} \| |\delta_0| |\sum_{|\omega|\leq 2s} \delta_\omega| = (\sqrt{2k-1}/k)^{2\ell} \sqrt{N_s}$.


For large values of $s$, you can get asymptotic results by combining the law of large numbers and the central limit theorem.

Indeed, there is a natural coupling for different values of $\ell$ (consider the uniform probability on infinite sequences of elements of the alphabet, and for each $\ell$ only remember the first $2\ell$ letters), and if $d_\ell$ is the random variable denoting the half of the length of a word of length $2\ell$, you have that $d_{\ell+1} - d_\ell$ is equal to $-1,0$ or $1$ with probability $1/4 k^2$, $(2k-1)/2k^2$ and $(2k-1)^2/4k^2$, unless $d_\ell = 0$. But Kesten's bound shows that we can forget this "unless" and work in the ideal random walk on $\mathbb R$ model, and apply the law of large numbers and the central limit theorem. Namely the probability that $d_\ell$ is less that $((k-1)/k) \ell + C \sqrt \ell$ has an explicitely computable limit for every $C$. In particular the probability that $d_\ell<\alpha \ell$ goes to zero if $\alpha<(k-1)/k$, and $1/2$ if $\alpha=(k-1)/k$ and $1$ otherwise.

If you want some more precise results (eg if $s/\ell \to \alpha < (k-1)/k$), a naive guess would be to apply large deviation techniques. But one should be careful and take into account the "unless $d_\ell = 0$".

$\endgroup$
5
  • $\begingroup$ Thanks, but isn't this upper bound bigger than one (i.e., worse than trivial) as soon as $s\geq (2(log(k)/log(2k−1))−1)\ell$? $\endgroup$ Jul 17, 2012 at 14:08
  • $\begingroup$ Yes, you are right. This bound is only interesting when $s$ is not to large. $\endgroup$ Jul 17, 2012 at 14:18
  • $\begingroup$ What values of the ratio $\ell/s$ are you interested in? $\endgroup$ Jul 17, 2012 at 14:20
  • $\begingroup$ "All of them!" was too short an answer to be accepted by MathOverflow (by a few characters). $\endgroup$ Jul 17, 2012 at 15:23
  • $\begingroup$ Really?$\text{}\mathbb{}$ $\endgroup$ Jul 18, 2012 at 2:47
1
$\begingroup$

This is studied in much greater generality in the paper of Cartwright and Woess (2004) [they walk on buildings, while this question is about trees], and prove a central limit theorem, which means, in this case, that for $s \in [3/4 l \pm O(\sqrt{l})]$, you have the central limit theorem estimate, where you can compute the variance explicitly. For $s$ much smaller than that, you should have a large deviation estimate, which I am not sure they do derive.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.