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

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.

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