on $G$ is $\mu$-rapidly mixing for $\mu \le \max\{|\lambda_2|, |\lambda_{|V|}|\}$. (A proof for this assertion can be found in many places, see [@HLW06] for instance.)

Here comes the relation between expanders and rapid mixing of random walks. Since combinatorial expanders are very strongly connected, we expect that random walks on them would mix rapidly. This is indeed true and it is given formally by Cheeger’s inequality [@Alo86] which states that $$\lambda_2 \le 1 - \frac{h(G)^2}{2}.$$ Thus, it suffices to show that a graph is an $\epsilon$-combinatorial expander for some constant $\epsilon > 0$ in order to deduce that the random walk on it converges rapidly to the uniform distribution.

\[bound-lambda-n-rem\] The cautious reader would note that combinatorial expansion gives us a bound only on $\lambda_2$, but for rapid mixing we need to bound $\lambda_{|V|}$ as well. This is not a problem since $\lambda_{|V|} = -1$ if and only if the graph is bipartite. Thus, in most applications it is possible just to add self-loops at each vertex which “destroys the bipartiteness” of the graph and does not slow down the convergence rate too much. Nevertheless, we show at section \[trevisan-section\] that when dealing with high order random walks the smallest 