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$ – Mikael de la Salle Feb 17 '14 at 20:46
  • $\begingroup$ OK, an infinite graph... (I've edited the question) $\endgroup$ – Michal Kotowski Feb 17 '14 at 20:50

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$ – Michal Kotowski Feb 18 '14 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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