# Return probabilities for random walks on infinite Schreier graphs

Question: Is there a sequence $(\delta_n)_n$ of real numbers with $\delta_n \to 0$ as $n \to \infty$, such that the following holds:

Let $F$ be a free group on two generators, let $F \curvearrowright X$ be a transitive action on an infinite set, and let $x \in X$. Then, the probability that a random word of length $n$ in $F$ fixes $x \in X$ is smaller than $\delta_n$.

I would like to consider random unreduced words (so that there are $4^n$ such words of length $n$ and each is equally likely), but probably this does not matter much. It corresponds to the nearest neighbor random walk on the Schreier graph corresponding to the action of $F$ on $X$.

It is clear that for each individual action $x \in X$, the return probability decays; and it seems plausible that this happens uniformly over all actions.

-
Do you assume that the action is faithful or it doesn't matter? – Benjamin Steinberg Mar 14 '12 at 21:04
Reformulation (with reduced words, i.e., random walks with no backtrack): let $I$ be the set of infinite index subgroups in $F$. Define $\delta_n=\sup_{H\in I}(\#(B_n\cap H)$, where $B_n$ is the $n$-ball in $F$. Is it true that $\delta_n/\#(B_n)$ tends to zero? – YCor Mar 14 '12 at 21:19
Benjamin, it does not matter for me. – Andreas Thom Mar 15 '12 at 8:10

So, if I understand things right, we have a random walk on an undirected connected graph with possibly multiple edges and degree 4 at each vertex that starts at some vertex $x$.

The usual way to proceed is to consider the vector $P=P_n$ whose components $P_n(y)$ are the probabilities to end at $y$ after $n$ steps. The dynamics is $P_{n+1}=AP_n$ where $A$ is one quarter of the incidence matrix. The key is that the $\ell^2$ norm of $P_n$ drops at each step by some constant multiple of the "gradient energy" $E=\sum_y \sum_{z,w\in N(y)}|P_n(z)-P_n(w)|^2$ where $N(y)$ is the set of neighbors of $y$. This allows to control the $L^\infty$ norm of $P_n$ (that also can go only down) very easily. If we made $n$ steps, the energy at some step was at most $C/n$. Now, take any vertex $v$ and join it with a faraway vertex by a shortest path $v=v_0--v_1--v_2--v_3--\dots$. Then the energy is at least $\sum_{k=0}^\infty |P(v_{2k})-P(v_{2k+2})|^2$. Now it remains to note that the $\ell^1$ norm of $P$ is always $1$, so we can estimate $P(v)$ by $1/M+\sqrt{M/n}$ with any integer $M$ we want (among first $M$ vertices with even indices, we have at least one with the probability $1/M$ or less and the sum of differences on the return path to $v$ from there is bounded by $\sqrt{M/n}$ by Cauchy-Schwarz. Taking $M=n^{1/3}$ gives $\delta_n=O(n^{-1/3})$. This is by no means optimal but it gives you the general idea of how such proofs go.

I leave it to the professional probabilists to refer you to the relevant literature.

-
Thanks, this is what I was looking for. A concrete argument. However, I still have problems to follow the steps. You call the $\ell^2$-norm of $P_n$ the energy, right? Why does it drop by some constant multiple of $E$? I also do not understand the later parts of the argument. – Andreas Thom Mar 27 '12 at 15:07
Not the $\ell^2$ norm of $P_n$ but the $\ell^2$-norm of its two-step gradient! (the square of the average of a few numbers is less than the average of squares by a constant times the sum of squares of pairwise differences). – fedja Mar 27 '12 at 15:54
@fedja - would you mind spelling out the argument a little more? I get your remark about squares-of-averages-minus-average-of-squares, but I don't see how that implies that $E$ decreases. – user21162 Mar 29 '12 at 2:13
$E$ does not. The $\ell^2$-norm does. If $E$ stays above $1/n$ for $n$ steps, then the total decrease of the $\ell^2$ norm is at least $1$ but it was just $1$ in the beginning. OK, I'll write it more carefully, just a bit later... – fedja Mar 29 '12 at 3:25

While Fedja has given a concrete argument, it occured to me that it also follows from (more or less) abstract nonsense, by compactness-and-contradiction.

Let me explain in more detail. Let $\delta_n$ be the supremum over all actions $G \curvearrowright X$ and $x \in X$ of the return probability after $n$ steps.

We need to show that $\delta_n \to 0$ as $n \to \infty$. It is clear that $\delta_{2n}$ is decreasing. This follows since the return probabilities after 2n steps for each individual action is decreasing, since they are given by the moments of positive contraction on a Hilbert space. Now, if $\inf_n \delta_{2n} = \delta >0$, then we find a sequence of actions $G \curvearrowright X_n$ and $x_n \in X_n$, such that the return probability after $2n$ (and hence $2k$ for $k<n$) steps to $x_n$ is greater or equal $\delta/2$.

Now, the space of transitive actions with chosen point is compact! Indeed, it is just the Chabauty space of subgroups of the free group, which is obviously compact. Moreover, the return probabilities are continuous functions on the space of transitive actions with chosen point. Hence, we find a limit point in this space and hence a limit action, for which the return probability after $2n$ steps is greater or equal $\delta/2$ for all $n$. Now, the only thing we can quickly say about the limit is that it is not finite. Indeed, the finite transitive actions are all isolated in the space of actions. This is a contradiction since we know already that for each individual action the return probabilities tend to zero.

-
Nice! I tried this Chabauty argument but I missed the point that $\delta_{2n}$ is decreasing and couldn't conclude. Anyway, this does not give any explicit bound. Do you expect $\delta_n$ to be in $1/n$? Fedja's argument (that I didn't check) shows it's at most $1/n^{1/3}$ and the case of $\mathbf{Z}$ shows it's at least $1/n$ (asymptotically). – YCor Mar 27 '12 at 20:48
It seems to me that the random walk on $\mathbb Z$ is the one where it is most difficult to get lost; $\delta_n$ should be maximal. However, I do not know if this intuition is misleading. – Andreas Thom Mar 28 '12 at 5:44
sorry, for $\mathbf{Z}$ the probability of return is $n^{-1/2}$ (exercise using Stirling's formula). So the behavior of $\delta_n$ should be between $n^{-1/2}$ and $n^{-1/3}$. – YCor Mar 28 '12 at 23:01
Actually, you can get $n^{-1/2}$ with the technique I described. It requires just one more trick. If you are interested, I'll post the details :). – fedja Mar 29 '12 at 0:31
Sure, more details would be great! – Andreas Thom Mar 29 '12 at 7:06