Theorem 17.17 -- return probabilities of the lazy walk

Let $G$ be a finite simple graph on a non-empty vertex set $V$, connected (any vertex is reachable from any other along edges) and with every degree positive. Write $\deg(v)$ for the number of neighbours of $v$, $|E|$ for the number of edges, and $\Delta=\max_v\deg(v)$ for the maximal degree. Simple random walk on $G$ jumps from $x$ to a uniformly chosen neighbour, $P(x,y)=\deg(x)^{-1}$ when $x\sim y$ and $0$ otherwise; its lazy version $\tilde P=\tfrac12(I+P)$ stays put with probability $\tfrac12$ at each step. On a connected graph the walk has the stationary distribution $\pi(x)=\deg(x)/2|E|$.

The theorem (Theorem 17.17 of Levin–Peres–Wilmer) asserts that the return probabilities of the lazy walk converge to $\pi$ at a rate controlled by the maximal degree alone: for every vertex $x$ and every time $t\ge1$,

The bound does not mention the size of the graph — only its maximal degree — which is what makes it useful for large sparse graphs, and it is proved by the evolving-set method of this mission rather than by any spectral estimate. (The dependence on $\Delta$ is not optimal; LPW remark that $c_1\Delta/\sqrt t$ also holds.)

A note on the connectedness hypothesis. LPW write $\pi(x)$ for the stationary distribution of the walk, which on a connected graph is $\deg(x)/2|E|$. The expression $\deg(x)/2|E|$ is of course a perfectly good number on any graph, and that is exactly what makes the omission of connectedness a falsehood rather than a vacuity: on a disconnected graph the walk started at $x$ never leaves the component of $x$, so its return probabilities converge to that component's stationary mass, which is strictly larger. On two disjoint edges every degree and the maximal degree equal $1$ and $|E|=2$; the lazy walk matrix is idempotent, so $\tilde P^{\,t}(x,x)=\tfrac12$ for every $t\ge1$ while $\deg(x)/2|E|=\tfrac14$, and at $t=100$ the claim would read $\tfrac14\le\sqrt2/10$. Positivity of the degrees rules out isolated vertices but not disconnection; it is kept alongside connectedness because a connected graph may still be the single vertex, where all three of $\deg(x)$, $\Delta$ and $|E|$ vanish.