$\pi_0, \pi_1, \dotsc \in {\mathbb{R}}^V$. The transition from $\pi_t$ to $\pi_{t+1}$ is given by $\pi_{t+1} = \pi_t \widetilde A$, where $\widetilde A = ({{}^{1\!\!}/_{\!k}})A$ is the [*normalized adjacency matrix*]{} of $G$. Note that $\widetilde A(u,v)$ is the probability to move from $u$ to $v$ in a single step, and $\widetilde A^t(u,v)$ is the probability that a walk starting at $u$ will be at $v$ after $t$ steps. It follows that for any $t \in {\mathbb{N}}$, $\pi_t = \pi_0\widetilde A^t$.

Denote by $\mathbf u = ({{}^{1\!\!}/_{\!|V|}}, \dotsc, {{}^{1\!\!}/_{\!|V|}})$ the uniform distribution on the vertices. If $G$ is connected and non-bipartite, then $\pi_0\widetilde A^t \rightarrow \mathbf u$ as $t \rightarrow \infty$ for any initial probability distribution $\pi_0 \in {\mathbb{R}}^V$. The random walk on $G$ is said to be [*$\mu$-rapidly mixing*]{}, $0 < \mu < 1$, if for any initial probability distribution $\pi_0 \in {\mathbb{R}}^V$ and any $t \in {\mathbb{N}}$ $${\left\lVert \pi_t - \mathbf u \right\rVert}_2 \le \mu^t.$$

The common way to deduce the mixing rate of a random walk is by the spectrum of the normalized adjacency matrix of $G$. Denote by $1 = \lambda_1 \ge \lambda_2 \ge \dotsb \ge \lambda_{|V|} \ge -1$ the eigenvalues of $\widetilde A$. Then the random walk 