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

Consider a Markov chain on $\mathbb{Z}^d$ with transition kernel $P$ for adjacent vertices (non-diagonal). Essentially this is a $d$ dimensional random walk with the probability of a transition dependent on it's location in the grid. This comes from a random conductance model. The theorem that concerns me is a general result for Markov chains, but I leave this motivation to assist in its proof (see below).

Let $P^{2k}(0,0)$ be the probability of going from the origin and back in $2k$ steps. Moreover, suppose $P$ is reversible. The theorem that concerns me is: 

$P^{2n}(0,0)$ is decreasing in $n$. 

I am interested in a probabilistic proof of this. The proof that I know is of a spectral nature:

Define $\langle f,g\rangle:= \sum_{X\in\mathbb{Z}^d} \pi(x)f(x)g(x)$,

where $\pi(x)$ is the stationary measure. This gives an inner product on $L^2(\mathbb{Z}^d)$. In the case of a random conductance model, $\pi(x)$ would be the sum of random edge weights at $x$. 


$P^{2k}(0,0)=\langle \delta_0,P^{2k}\delta_0\rangle$,

and since $P$ is self adjoint with $\|P\|_2\leq 1$, the desired result follows. 

I have tried various approaches such as conditioning on the hitting times of the origin and as well trying to prove the result by induction. I would like to see a proof that showcases a probabilistic argument. For example, is it possible to show the result from the machinery of evolving sets of Morris and Peres?

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

I am not exactly sure about what is meant by "probabilistic", but there is a simple argument based on the Cauchy inequality (no spectral theory involved) which provides a so-called "ratio limit theorem" for return probabilities. It is valid for any reversible chain with an infinite stationary measure, i.e., any reversible chain which is not positive recurrent.

Let $\phi_n(x)=p_n(o,x)/\pi(x)$ be the density of the $n$-step transition probability from the reference point $o$ with respect to the stationary measure $\pi$ (I use a slightly different notation). I will normalize the measure $\pi$ in such a way that $\pi(o)=1$. Then for any $n,m\ge 0$ $$ p_{n+m}(o,o) = \sum_x p_n(o,x) p_m(x,o) = \sum_x p_n(o,x) p_m(o,x) \frac{1}{\pi(x)} = \langle \phi_n,\phi_m\rangle \;, $$ where $\langle\cdot,\cdot\rangle$ denotes the scalar product with respect to the stationary measure $\pi$. In particular, for $n=k-1$ and $m=k+1$ $$ p_{2k}(o,o) = \langle\phi_{k-1},\phi_{k+1}\rangle_\pi \le \|\phi_{k-1}\| \|\phi_{k+1}\| \;, $$ whence $$ \frac{p_{2k}(o,o)}{p_{2k-2}(o,o)} \le \frac{p_{2k+2}(o,o)}{p_{2k}(o,o)} \;. $$ The above inequalities are strict unless $\phi_{k-1}=\phi_{k+1}$, in which case also $\phi_{k+3}=\phi_{k+5}=\dots=\phi_{k-1}$, which implies that all the return probabilities $p_{2k}(o,o), p_{2k+2}(o,o),\dots$ are the same, which is only possible for a positive recurrent chain. Thus, discarding the positive recurrence case, the sequence of ratios $p_{2k+2}(o,o)/p_{2k}(o,o)$ is strictly increasing. Obviously, its limit can not be greater than 1, whence the claim.

Actually, in the situation considered by the OP the value of the above limit, in other words, the spectral radius of the transition operator, is precisely 1 provided the operator has bounded geometry (i.e., the weights of edges are uniformly bounded from below and above).

share|cite|improve this answer
Thanks for the detailed answer. Although the spectral arguments are not entirely dissimilar from this, I like the ratio limit you derive. I was hoping for an argument that's more combinatorial. Yet there are some issues of parity that come into play if you derive a similar ratio limit for odd cycles (nonexistent for my purposes but interesting nonetheless). – Alex R. Apr 28 '11 at 20:30
I agree. It would, indeed, be interesting to find a more combinatorial argument. – R W Apr 29 '11 at 12:09
Deat RW, it would be very interesting to have your insights in this new post… as you seem well versed in this field. Anyhow appreciate you considering it. – user929304 Mar 4 at 3: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.