MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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$. – Ron Maimon Aug 1 '11 at 20:10
I don't see why it's false for $Z^2$: The left side of the implication is always false. – Anthony Quas Aug 1 '11 at 21:54
@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. – Ron Maimon Aug 2 '11 at 4:21
@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. – Justin Aug 2 '11 at 16:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.