3
$\begingroup$

Let $\Gamma$ denote the Cayley graph for a finitely generated group $G$, and let $p_n(x, y)$ denote the transition probability that a random walk starting at $x$ reaches $y$ at time $n$. A famous "Gaussian bound" due to Carne and Varopoulos states that given a reversible Markov chain, one has that $$ p_n(x, y) \leq 2 \sqrt{ \frac{\mu (y)}{\mu (x)}}\rho^n e^{-\frac{d(x, y)^2}{2n}}, $$ where $\mu$ is a stationary measure for the Markov chain, and $\rho$ is the norm of the Markov operator $Pu(x) := \sum_{y \in \Gamma} p(x, y)u(y)$.

I am trying to understand the application of the above bound to Cayley graphs. The bound aligns with my vague intuition obtained from Gaussian heat kernel bounds in the continuous setting. But I am thrown off by the stationary measure term and the concept of "reversible", which I don't really understand. Does such a measure always exist, particularly if the random walk is not recurrent? Also, how is such a bound useful, unless one has very explicit information about some stationary measure? Also, what about reversibility on a Cayley graph?

Further, a stationary measure is defined by $\mu (x) = \sum_{y \in \Gamma} p(x, y) \mu(y)$. I am seriously confused over this definition: what is stopping the measure from being $\mu(x) \equiv 1$ for all $x \in \Gamma$?

$\endgroup$

1 Answer 1

1
$\begingroup$

I strongly recommand Woess' book Random walks on infinite graphs and groups for all this.

In the first chapters, the authors takes time to explain all basic concepts, such as (positive) recurrence (Section 1.B) and reversibility (Section 2.A).

Your definition of stationary is not right. The Markov operator acts on measures by $$P\mu(x)=\sum_y\mu(y)p(y,x).$$ However, the action on functions you define is correct. Hence, a stationnary measure (invariant measure in Woess' book) is a measure on the graph such that $$\mu(x)=\sum_y\mu(y)p(y,x).$$

Now, reversibility means there exists a function $m$ such that $$m(x)p(x,y)=m(y)p(y,x).$$ The function $m$ is then a stationary measure and it is implicit in Carne-Varapoulos bound that the stationary measure $\mu$ is this one.

Lots of details on this theorem are provided in chapter 13 of the book Probability on trees and networks (Lyons and Peres). You also have many explanations on similar bounds in Section 14 of Woess' book.

I hope this answers your questions.

$\endgroup$
1
  • $\begingroup$ Thanks for your answer, I think some of my doubts are answered now. In particular if the measure on the group $\eta (x^{-1}y) := p(x, y)$ is symmetric, then the stationary measure is $1$, is that correct? Then the Carne-Varopoulos bound always holds. Otherwise one requires something extra, like recurrence (as in Woess). $\endgroup$
    – user482846
    May 23, 2022 at 20:35

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.