What's the simplest example of a reversible random walk $X_n$ on an infinite vertex-transitive graph such that the expected distance from the origin is not increasing, i.e. there exists $n$ such that:

$\mathbb{E} \,d(X_0, X_{n+1}) < \mathbb{E}\,d(X_0, X_n)$?

EDIT: Douglas Zare provided an example below, but the random walk is not simple (we are giving bigger weight to one of the outgoing edges) and the nonmonotonicity is essentially due to a parity issue, which is not that interesting.

So let me reformulate the question: does there exist a simple random walk on an infinite vertex-transitive graph (preferably: a Cayley graph) where nonmonotonicity would not arise due to some periodicity issue? The phenomenon I have in mind is that some graphs have "dead ends", i.e. vertices from which every step takes the random walker closer to the origin (equivalently: geodesics to such vertices cannot be extended). But I don't know whether this obstruction can be serious enough so that on average the distance will be nonmonotonous.

  • $\begingroup$ What about a graph with exactly two vertices? $\endgroup$ Feb 17, 2014 at 20:46
  • $\begingroup$ OK, an infinite graph... (I've edited the question) $\endgroup$ Feb 17, 2014 at 20:50
  • $\begingroup$ The question is most interesting for lazy simple random walks, that stay in place with probability $1/2$. This eliminates all parity issues. $\endgroup$ Nov 21, 2021 at 2:09

2 Answers 2


EDIT Sorry - first mistook "transitive" for "transient". Here is an example of a simple random walk on a group. The idea, indeed, is that there is a small subset of the group near the identity with a "high concentration" of dead ends, whereas elsewhere the distance from the origin is a martingale. I show that the "anomalous" behavior happens for all (sufficiently big) odd $n$, which involves some sort of periodicity (still, one can't expect all $n$ to be anomalous).

Let $G=\mathbb Z_3\times\mathbb Z_3\times\mathbb Z$ endowed with the generating set $S$ which consists of 8 elements $(\pm 1,\pm 1,\pm 1)$. For an element $g=(g_1,g_2,g_3)\in G$ let $a=a(g)$ be the number of non-zero entries among $g_1,g_2$, and let $b=b(g)=|g_3|$. One can easily see that the length of $g$ only depends on the values $(a,b)$, and the length function can be easily found explicitly by drawing a picture: $$ \begin{aligned} l(0,0)&=0, \\ l(2,1)&=1, \\ l(1,0)=l(2,0)&=2, \\ l(0,1)=l(1,1)&=3, \end{aligned} $$ and $l(a,n)=n$ whenever $n\ge 2$.

Further, one can equally easily see that the image, under the projection $g\mapsto (a,b)$, of the simple random walk $(G,S)$ issued from the identity of $G$ is a product of the simple random walk on $B=\mathbb Z_+$ with reflection at 0 and of the random walk on $A=\{0,1,2\}$ with the following transition probabilities: $$ \begin{aligned} &p(0,2)=1 , \\ &p(1,1)=1/2, \; p(1,2)=1/2 \\ &p(2,0)=1/4, \; p(2,1)=1/2, \; p(2,2)=1/4 \end{aligned} $$ This observation together with the above formulas for the length function allows one to find the expectations $$ f(g) = f(a,b) = \mathbb E_g [ l(g_1) - l(g) ] $$ of length increments after one step of the simple random walk $(G,S)$. I will only need the values $$ f(0,1) = -1, f(1,1)=-1, f(2,1)=3/4 $$ and the fact that $f(a,n)=0$ whenever $n\ge 3$.

Now, the stationary distribution of the above chain on $A$ is $(1/9,4/9,4/9)$, so that the expectation of the function $f(\cdot,1)$ with respect to this distribution is strictly negative. Since at odd moments of time the quotient chain on $B$ only charges the odd points, one can conclude that for all sufficiently big odd $n$ (actually, probably for all odd $n$, but I have already done too many explicit computations here) $$ \mathbb E\, l(g_{n+1}) < \mathbb E\, l(g_n) \;. $$


Here are two examples with bipartite graphs.

Let the vertices be the integers. Take steps of $\pm(2n+1)$ with probability $2^{-n-2}$. This is bipartite and all vertices are connected to each vertex in the other part. At odd time steps, the distance from the origin is always $1$. At even time steps, the distance from the origin is usually $2$, with a small probability of $0$. For example, $\mathbb{E}d(x_0,x_2) = 1/6(0)+5/6(2) = 5/3 \gt \mathbb{E}d(x_0,x_3) = 1$ so the third step doesn't increase the average distance.

Let the vertices be $\lbrace n \rbrace_{n\in \mathbb Z} \cup \lbrace n' \rbrace_{n\in \mathbb Z}$. Let $n$ move to $n'$ with probability $p$ close to $1$, and to $(n-1)'$ or $(n+1)'$ with low probability. Symmetrically, let $n'$ move to $n$ with probability $p$ and to $(n-1)$ or $(n+1)$ with low probability. Taking two steps usually returns to the origin. $\mathbb{E}d(x_0,x_1) = 1$. $\mathbb{E}d(x_0,x_2) \le 2(1-p^2)$ which is less than $1$ for $p \gt 1/\sqrt{2}$ so the second step doesn't increase the average distance.

  • $\begingroup$ A nice example. But somehow this is still not what I had in mind, see the edit in the question. $\endgroup$ Feb 18, 2014 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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