A bound on the square distance of a random walk on undirected graph

Question

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.

Answer 1

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