Probability that a word in the free group becomes (much) shorter? 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).)
 A: (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$".
A: 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).$$
A: 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.
