2
$\begingroup$

Suppose we are performing a random walk in a group. More precisely, we have a finite generating set $S$ of a group $G$ and the probability of walking along generator $s$ is given by $\mu(s)$ for some fixed probability measure $\mu$ on $S$. Denote by $W(n, \mu)$ a random walk of length $n$ with respect to $\mu$, and let $A \subset G$. I can show the following implication. ($\mu_{unif}$ is the uniform probability measure.)

There is a $c < 1$ such that $P(W(n, \mu_{unif}) \in A) < c^n$ for sufficiently large $n$ $$\Rightarrow$$ For any probability measure $\mu$ supported on $S$, there is a $d < 1$ such that $P(W(n, \mu) \in A) < d^n$ for sufficiently large $n$

I can fairly easily prove this (in about a page) with only elementary arguments, so I am guessing this is known. Is there a reference with this statement somewhere? Perhaps, there is a one-line proof using some other result?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What are the conditions on the group? I assume free, because your result is true in a free group with two generators, and false for $Z^2$. $\endgroup$
    – Ron Maimon
    Commented Aug 1, 2011 at 20:10
  • $\begingroup$ I don't see why it's false for $Z^2$: The left side of the implication is always false. $\endgroup$
    – Anthony Quas
    Commented Aug 1, 2011 at 21:54
  • $\begingroup$ @Anthony: That's puzzling. As I understood the problem, it is saying that the probability that an n-step walk with a given generator set lands in a bounded set of points decays exponentially. This is false in Z^2 because the Gaussian kernel decays as a power, but it is true in a free group on two generators because you have exponential growth. It is possible that the OP meant an arbitrary subset, but then you could take A to be the whole group minus a few points, and it is trivially false. I think that is overly uncharitable interpretation, but perhaps the question could be clarified. $\endgroup$
    – Ron Maimon
    Commented Aug 2, 2011 at 4:21
  • $\begingroup$ @Ron: The statement is not about bounded subsets necessarily. The implication is: If we know that A is hit with exponentially decaying probability when $\mu$ is the uniform measure, then it is also true when $\mu$ is an arbitrary measure supported on S. $\endgroup$
    – Justin
    Commented Aug 2, 2011 at 16:54

0

Reset to default

You must log in to answer this question.