Spectral Mixing Bounds for Lazy Walks

Lazy Walks and Their Mixing Time

A spectral gap measures how rapidly a random walk forgets differences between its starting distributions. For a lazy walk, the gap gives both an upper bound on the time needed to get close to stationarity and, through an eigenfunction, a lower bound on how quickly the worst starting state can mix. These bounds make explicit the roles of the starting vertex, graph size and desired accuracy.

Throughout, let \(G=(V,E)\) be a finite, connected, simple, undirected graph with \(n=|V|\ge2\). Write \(\deg(v)\) for the degree of \(v\). The transition matrix \(Q\) of simple random walk has \(Q(u,v)=1/\deg(u)\) when \(uv\in E\), and \(Q(u,v)=0\) otherwise. The lazy walk stays put with probability \(1/2\) and otherwise takes a simple random-walk step.

The graph assumptions ensure that every degree is positive, \(\pi\) is defined at every vertex, and the walk is irreducible. The identity \(\pi(u)Q(u,v)=\pi(v)Q(v,u)\) for every pair \(u,v\) shows reversibility; it also holds with \(P\) in place of \(Q\). Consequently, \(P\) is self-adjoint for the inner product \(\langle f,g\rangle_\pi=\sum_v\pi(v)f(v)g(v)\), and \(\pi\) is stationary.

The Spectral Gap

Order the eigenvalues of \(P\) as \(1=\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n\). The eigenvalue \(1\) has only constant eigenfunctions because the graph is connected. All eigenvalues of \(P\) are nonnegative: \(Q\) is a self-adjoint contraction, so its eigenvalues belong to \([-1,1]\), and the eigenvalues of \((I+Q)/2\) belong to \([0,1]\). Here contraction follows, for example, from Jensen's inequality and stationarity: \(\sum_u\pi(u)(Qf(u))^2\le\sum_u\pi(u)\sum_vQ(u,v)f(v)^2=\sum_v\pi(v)f(v)^2\).

For a mean-zero function \(f\), expansion in an orthonormal eigenbasis gives \(\|P^t f\|_{2,\pi}\le\lambda_2^t\|f\|_{2,\pi}\). This is the contraction behind the upper mixing estimate. For the lower estimate, an eigenfunction for \(\lambda_2\) retains a known fraction of its initial value after every step.

An Upper Bound from the Starting Vertex

Proof. Let \(h_t(v)=P^t(x,v)/\pi(v)-1\). Since \(\pi\) is stationary, \(\sum_v\pi(v)h_t(v)=0\), and reversibility implies that \(h_t=P^t h_0\). At time zero, \(h_0(v)=\mathbf{1}_{\{v=x\}}/\pi(x)-1\), so \(\|h_0\|_{2,\pi}^2=\pi(x)(1/\pi(x)-1)^2+(1-\pi(x))=\frac1{\pi(x)}-1\). The mean-zero contraction therefore gives \(\|h_t\|_{2,\pi}\le\lambda_2^t\sqrt{1/\pi(x)-1}\). By Cauchy–Schwarz, \[ \|P^t(x,\cdot)-\pi\|_{\mathrm{TV}} =\tfrac12\sum_v\pi(v)|h_t(v)| \le\tfrac12\|h_t\|_{2,\pi}. \] This proves the first bound. For \(0<\gamma<1\), \(1-\gamma\le e^{-\gamma}\); when \(\gamma=1\), \(\lambda_2=0\) and the stated conclusion for \(t\ge1\) follows directly. \(\square\)

Put \(C_x=\frac12\sqrt{1/\pi(x)-1}\). If \(C_x\le\varepsilon\), the bound already guarantees that the walk from \(x\) is within \(\varepsilon\) at time zero. Otherwise, for \(0<\gamma<1\), it is enough to take \(t\ge\left\lceil\gamma^{-1}\log(C_x/\varepsilon)\right\rceil\). The estimate uses the actual stationary mass of the starting vertex, not just a graph-wide worst case.

For a bound in terms of graph size, let \(\pi_{\min}=\min_v\pi(v)\). Since a connected graph on \(n\ge2\) vertices has degree at least \(1\) and at most \(n-1\), and \(2|E|\le n(n-1)\), we have \(\pi_{\min}\ge1/[n(n-1)]\). Thus \(C_x\le\frac12\sqrt{n(n-1)}\le n/2\). For \(0<\varepsilon<1/2\), a convenient consequence is \[ t_{\mathrm{mix}}(\varepsilon)\le \left\lceil\frac1\gamma\log\left(\frac{n}{2\varepsilon}\right)\right\rceil . \] This is a sufficient bound; it need not equal the actual mixing time.

A Lower Bound from an Eigenfunction

Proof. Since \(\lambda_2<1\), stationarity and the eigenfunction equation imply \(\sum_v\pi(v)f(v)=0\): indeed, \(\sum_v\pi(v)f(v)=\sum_v\pi(v)(Pf)(v)=\lambda_2\sum_v\pi(v)f(v)\), so the sum is zero. Starting at \(x\), the expected value of \(f\) after \(t\) steps is \((P^tf)(x)=\lambda_2^t f(x)\), whereas its stationary expectation is zero. For any two distributions \(\mu,\nu\) and any \(f\) with \(|f|\le1\), \(|\sum_v f(v)(\mu(v)-\nu(v))|\le\sum_v|\mu(v)-\nu(v)|=2\|\mu-\nu\|_{\mathrm{TV}}\). Applying this to the walk distribution and \(\pi\) proves the first inequality. At a vertex with \(|f(x)|=1\), the distance is greater than \(\varepsilon\) whenever \(\lambda_2^t>2\varepsilon\). Taking logarithms shows that every integer \(t<\log(1/(2\varepsilon))/[-\log(\lambda_2)]\) fails the worst-case mixing test, which gives the stated ceiling bound. \(\square\)

This lower bound depends on an initial state where the eigenfunction has large magnitude. It is not a claim that every starting vertex mixes slowly. When \(\lambda_2=0\), the displayed logarithmic lower bound does not apply; in that case every mean-zero component is erased after one step, and the eigenfunction argument gives no positive lower bound.

Starting State and Graph Size in Practice

For a \(d\)-regular graph, \(\pi(x)=1/n\) for every vertex, so the starting-state upper bound becomes \[ \|P^t(x,\cdot)-\pi\|_{\mathrm{TV}} \le\frac12\sqrt{n-1}\,(1-\gamma)^t. \] The prefactor grows with graph size: reaching a fixed small error generally requires a time proportional to \(\gamma^{-1}\log n\), in addition to the dependence on \(\log(1/\varepsilon)\). In a nonregular graph, \(\pi(x)\) replaces \(1/n\); starting at a low-stationary-mass vertex can give a weaker upper estimate.

Common Pitfalls

Do not confuse a bound with an exact mixing time. On the three-vertex path, the upper estimate from vertex \(1\) gives \(2\) steps at error \(1/4\), while direct calculation shows that \(1\) step suffices. An upper bound guarantees enough steps; it does not assert that fewer steps fail.

Do not apply the eigenfunction lower bound to every starting vertex. Its strength includes the factor \(|f(x)|\). A vertex where the chosen eigenfunction is zero gives no lower bound from that eigenfunction, even though another starting vertex may retain a large deviation.

Use the lazy-walk gap. The transition matrix in these estimates is \(P=(I+Q)/2\), not the simple-walk matrix \(Q\). Laziness shifts and rescales the eigenvalues, preventing negative eigenvalues from producing periodic oscillation and making the relevant contraction rate \(1-\gamma=\lambda_2(P)\).