Diffusive estimates for random walks on stationary random graphs of polynomial growth

Abstract

Let $(G,\rho )$ be a stationary random graph, and use $B_{\rho }^G(r)$ to denote the ball of radius $r$ about $\rho$ in $G$. Suppose that $(G,\rho )$ has annealed polynomial growth, in the sense that $\mathbb{E}[|B_{\rho }^G(r)|]\le O(r^k)$ for some $k>0$ and every $r\ge 1$. Then there is an infinite sequence of times $\{t_n\}$ at which the random walk $\{X_t\}$ on $(G,\rho )$ is at most diffusive: Almost surely (over the choice of $(G,\rho )$), there is a number $C>0$ such that \[ \mathbb{E} \left[\mathrm{dist}_G(X_0, X_{t_n})^2 \mid X_0 = ρ, (G,ρ)\right]\leq C t_n\qquad \forall n \geq 1\,. \] This result is new even in the case when $G$ is a stationary random subgraph of ${\mathbb{Z}}^d$. Combined with the work of Benjamini, Duminil-Copin, Kozma, and Yadin (2015), it implies that $G$ almost surely does not admit a non-constant harmonic function of sublinear growth. To complement this, we argue that passing to a subsequence of times $\{t_n\}$ is necessary, as there are stationary random graphs of (almost sure) polynomial growth where the random walk is almost surely superdiffusive at an infinite subset of times.