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

I'm trying to prove the following:

Let $G$ be a group with finite symmetric generating set $S$ and let $\Gamma(G,S)$ be the corresponding Cayley graph. Let $X_1, X_2,\cdots$ be a simple random walk starting from a fixed vertex $x\in\Gamma(G,S)$. For each $n$ let $\mu_n$ denote the law of $X_n$. Fix an integer $k>0$. Suppose that for some integer $m$, the support of $\mu_m$ and the support of $\mu_{m+k}$ are non-disjoint. Construct a coupling to show that $X_n$ and $X_{n+k}$ meet in finite time almost surely.

So, I think $X_n$ and $X_{n+k}$ meet in finite time a.s if and only if there exists a word of length exactly $k$ with letters from $S$ representing the identity element $e$? Because on the one hand, if no such word exists then $X_n$ and $X_{n+k}$ will never meet. On the other hand, since there are only finitely many words of length $k$, and $k$ steps of the random walk correspond to a uniform choice of one of them, eventually the random walk will come across the sequence of length $k$ corresponding to $e$ with probability limiting to 1 (so for example, for all even $k$, $X_n$ and $X_{n+k}$ will trivially meet in finite time a.s).

When it says that the supports of $\mu_m$ and $\mu_{m+k}$ are non-disjoint, does this mean that there is a word lying in the set of values that $X_m$ can take and also in the set of values $X_{m+k}$ can take? i.e there is some $y\in G$ so that $x^{-1}y$ can be expressed using exactly $m$ letters from $S$ and also so that it can be expressed using exactly $m+k$ letters from $S$? If so is there a purely group theoretic way to do the problem? The problem says to construct a coupling of $X_n$ and $X_{n+k}$ but I can't think of one that would work.

share|cite|improve this question
up vote 3 down vote accepted

There is a theorem of Foguel (MR0400332) according to which for any probability measure $\mu$ on any group (not necessarily countable) and any $k>0$ the limit of the (monotone) sequence $\|\mu^{*n}-\mu^{*(n+k)}\|$ is either 0 or 2. In the case of of countable groups it implies that if the supports of $\mu^{*N}$ and $\mu^{*(N+k)}$ overlap for certain $N$ and $k$, then the above limit is 0, which implies existence of the coupling you are asking about. Foguel's proof is entirely analytic (there is also another proof based on general 0-2 laws for Markov operators), but I think that it can be recast in coupling terms.

PS By the way, what's the source of your problem?

share|cite|improve this answer
Thanks! I found the paper with Foguel's theorem. It's exactly what I need. The problem is for a class on discrete probability, which I have no background in. – JAN Mar 3 '14 at 7:16

Your Answer


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

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