3
$\begingroup$

Fact: Let $G$ be an $n$-vertex undirected graph and $(X_s)_{s\in \mathbb N}$ a stationary random walk on $G$. Then for every $s\in \mathbb{N}$, $ \mathbb{E}[d_G(X_s,X_0)^2] \le C s \log n $, for some universal constant $C>0$. Here $d_G$ is the shortest path metric on $G$.

This fact is a corollary of a theorem of Naor, Peres, Schramm, and Sheffield [https://arxiv.org/abs/math/0410422] stating that $\ell_p$, $p\ge 2$ has Markov type 2 with constant $O(\sqrt{p})$.

I'm looking for a "pure" probabilistic and/or combinatorial (and preferably, simple) proof of this fact, that in particular does not use Banach space notions such as smoothness.

$\endgroup$
3
$\begingroup$

As communicated to me by Assaf Naor, that bound also follows immediately from the Varopoulos-Carne bound $p_s(x,y) \le 2 \sqrt{\pi(y)/\pi(x)}\cdot e^{-d_G(x,y)/(2s)}$, where $p_s(x,y)$ is the probability of reaching $y$ after $s$ steps beginning at $x$, and $\pi$ is the stationary distribution. See Section 13.2 in the book "Probability on Trees and Networks" by Lyons and Peres

$\endgroup$

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.