From Expansion to Fast Sampling
A random walk on a graph can be used to generate vertices that are close to uniformly distributed, without listing all vertices or selecting one directly. The key is that the walk must forget its starting point quickly. For a regular expander, a spectral gap bounded away from zero ensures that this happens after a number of steps proportional to the logarithm of the number of vertices.
Uniform sampling requires care about the stationary distribution. In a \(d\)-regular graph, the uniform distribution is stationary. For a nonregular graph, the ordinary random walk is generally stationary with probabilities proportional to vertex degrees, not uniform. We therefore formulate the main result for finite, connected, \(d\)-regular simple graphs, with \(d\ge 1\). The graphs may vary in a family, but their degrees are bounded and their lazy-walk spectral gaps have a common positive lower bound.
The matrix \(P\) is symmetric, so its eigenvalues are real. Its largest eigenvalue is \(1\). Write \(\lambda_*(G)\) for the largest absolute value of any other eigenvalue, and define the lazy spectral gap by \(\gamma(G)=1-\lambda_*(G)\). Connectedness makes the eigenvalue \(1\) simple. Laziness shifts every eigenvalue of the ordinary random-walk matrix into \([0,1]\): if \(\theta\in[-1,1]\) is an eigenvalue of \(\mathbf{A}(G)/d\), its lazy-walk eigenvalue is \((1+\theta)/2\). In particular, laziness removes the negative eigenvalue of magnitude \(1\) that causes periodicity in a connected bipartite graph.
The Spectral Mixing Bound
For probability distributions \(\mu\) and \(\nu\) on \(V\), their total variation distance is \(\|\mu-\nu\|_{\mathrm{TV}}=\frac12\sum_{v\in V}|\mu(v)-\nu(v)|\). The mixing time at accuracy \(0<\varepsilon<1\) is the least integer \(t\ge0\) for which \(\max_{x\in V}\|P^t(x,\cdot)-\pi\|_{\mathrm{TV}}\le\varepsilon\). The maximum means that the guarantee holds from every starting vertex.
Proof. Give real-valued functions on \(V\) the inner product \(\langle f,g\rangle_\pi=\frac1n\sum_{v\in V}f(v)g(v)\), and let \(\|f\|_{2,\pi}=\sqrt{\langle f,f\rangle_\pi}\). Because \(P\) is symmetric, it is self-adjoint for this inner product. The density of the point mass at \(x\), relative to \(\pi\), is \(f_0(v)=n\) if \(v=x\) and \(f_0(v)=0\) otherwise. Its mean is \(1\), and direct substitution gives \(\|f_0-1\|_{2,\pi}^2=((n-1)^2+(n-1))/n=n-1\).
Since \(P\) is symmetric and stochastic, it preserves the constant functions and the subspace of functions of mean zero. On that subspace every eigenvalue has absolute value at most \(\lambda_*(G)\). Expanding \(f_0-1\) in an orthonormal eigenbasis therefore gives \(\|P^t(f_0-1)\|_{2,\pi}\le\lambda_*(G)^t\sqrt{n-1}\). Symmetry also means that the density after \(t\) steps from \(x\) is \(P^t f_0\). By Cauchy–Schwarz, $$ \|P^t(x,\cdot)-\pi\|_{\mathrm{TV}} =\frac12\|P^t(f_0-1)\|_{1,\pi} \le\frac12\|P^t(f_0-1)\|_{2,\pi} \le\frac12\sqrt{n-1}\lambda_*(G)^t. $$ This proves the first inequality. For the time estimate, \(\lambda_*(G)=1-\gamma(G)\le e^{-\gamma(G)}\), using \(1-u\le e^{-u}\) for \(u\ge0\). It is sufficient that \(\frac12\sqrt n\,e^{-\gamma(G)t}\le\varepsilon\). Taking logarithms gives \(\gamma(G)t\ge\frac12\log n+\log(1/(2\varepsilon))\). If this right-hand side is negative, \(t=0\) already satisfies this sufficient inequality. The stated condition follows. \(\square\)
If every graph in a family has \(\gamma(G)\ge\gamma_0>0\), the bound gives a mixing time of order \(\log n+\log(1/\varepsilon)\), with constants depending on \(\gamma_0\). In particular, for fixed accuracy the number of steps grows at most logarithmically in \(n\). A bounded degree makes the local random choice inexpensive; the spectral gap, rather than bounded degree alone, supplies the rapid convergence.
Worked Bounds on Small Graphs
Worked Example: Mixing on \(K_4\)
Let \(G=K_4\), with \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24,34\}\). This is a connected 3-regular graph. The adjacency matrix has eigenvalue \(3\) on the constant vector and eigenvalue \(-1\) on the three-dimensional subspace of vectors whose coordinates sum to zero. Thus the lazy transition matrix has eigenvalues \(1\) and \((1+(-1/3))/2=1/3\), the latter with multiplicity three. Therefore \(\lambda_*=1/3\) and \(\gamma=1-1/3=2/3\).
Start at vertex \(1\). From the transition rule, the probability of staying at \(1\) in one step is \(1/2\), and the probability of moving to each of \(2,3,4\) is \((1/2)(1/3)=1/6\). The starting distribution minus uniform is an eigenvector component with eigenvalue \(1/3\), so after \(t\) steps the probabilities are \(1/4+(3/4)(1/3)^t\) at \(1\), and \(1/4-(1/4)(1/3)^t\) at each other vertex. The total variation distance is half the sum of the four absolute differences, namely \((3/4)(1/3)^t\).
Check: At \(t=2\), the exact distance is \((3/4)(1/9)=1/12\). The theorem gives \((1/2)\sqrt{4-1}(1/3)^2=\sqrt3/18\), which is at least \(1/12\), as required. At \(t=0\), the exact distance is \(3/4\), agreeing with the distance between a point mass and the uniform distribution on four vertices.
Worked Example: Two Steps on \(K_{3,3}\)
Let \(G=K_{3,3}\), with parts \(L=\{a,b,c\}\) and \(R=\{x,y,z\}\), and edge set \(E=\{ax,ay,az,bx,by,bz,cx,cy,cz\}\). The graph is connected and 3-regular. Its adjacency eigenvalues are \(3,-3,0,0,0,0\), so the lazy eigenvalues are \(1,0,1/2,1/2,1/2,1/2\). Hence \(\lambda_*=1/2\), \(\gamma=1/2\), and the stationary probability of each vertex is \(1/6\).
Start at \(a\). In one step, the walk stays at \(a\) with probability \(1/2\), goes to each vertex of \(R\) with probability \(1/6\), and assigns probability \(0\) to \(b,c\). For two steps, the probability of \(a\) is \((1/2)(1/2)+3(1/6)(1/6)=1/4+1/12=1/3\). The probability of \(b\) is \(3(1/6)(1/6)=1/12\), and the same computation gives \(1/12\) for \(c\). For each vertex in \(R\), the two-step probability is \((1/2)(1/6)+(1/6)(1/2)=1/12+1/12=1/6\).
The total variation distance is therefore \(\frac12(|1/3-1/6|+2|1/12-1/6|+3|1/6-1/6|)=\frac12(1/6+1/6)=1/6\). The spectral bound gives \((1/2)\sqrt{6-1}(1/2)^2=\sqrt5/8\), which is at least \(1/6\) because \(3\sqrt5\ge4\), as follows by squaring the positive sides to get \(45\ge16\). This example also shows why the lazy eigenvalues matter: the ordinary walk on this bipartite graph has eigenvalue \(-1\) and alternates between the two parts.
Approximate Sampling
Proof. For probability distributions \(\mu,\nu\) on a finite set, total variation distance equals \(\max_{A\subseteq V}|\mu(A)-\nu(A)|\). To verify this, put \(D=\{v:\mu(v)\ge\nu(v)\}\). Since \(\sum_v(\mu(v)-\nu(v))=0\), the sum of the positive differences over \(D\) equals half the sum of all absolute differences. No subset can have a larger absolute difference, because its positive contributions are bounded by that sum and its negative contributions have the same total magnitude. Taking \(\mu=P^t(x,\cdot)\), \(\nu=\pi\), and any particular \(A\) proves the claim. \(\square\)
Thus, after a sufficient number of steps, the endpoint is an approximate uniform sample in the precise sense that every event has probability within \(\varepsilon\) of its uniform probability. In the \(K_{3,3}\) example, take \(A=\{a\}\) after two steps. The walk gives \(\Pr(X_2\in A)=1/3\), whereas a uniform sample gives \(|A|/6=1/6\); the difference \(1/6\) is exactly the computed total variation distance. The spectral bound is a general guarantee, not usually an exact prediction of the error.
For a family with gap at least \(\gamma_0\), it is sufficient to run for an integer \(t\) at least $$ \frac{1}{\gamma_0}\left(\frac12\log n+\log\frac{1}{2\varepsilon}\right), $$ when the quantity in parentheses is positive. Rounding this value up gives a valid integer number of steps. If a bounded-degree graph is represented by its neighbor lists, each step uses one random choice to decide whether to stay and, when moving, one choice among at most a fixed number of neighbors. Consequently, the number of steps, and hence the number of such local transition choices, is logarithmic in \(n\) for fixed \(\varepsilon\). This concerns the cost of producing one approximate sample; generating multiple samples requires running the walk for each sample or otherwise specifying a sampling procedure.
Common Pitfalls
Using the wrong stationary distribution. The uniform conclusion depends on regularity. For example, on the path with \(V=\{1,2,3\}\) and \(E=\{12,23\}\), the ordinary random walk has stationary probabilities proportional to degrees: the degrees are \(1,2,1\), so the stationary distribution is \((1/4,1/2,1/4)\), not uniform. A spectral mixing statement for that walk does not establish uniform sampling.
Ignoring the absolute value in the non-lazy spectrum. On \(K_{3,3}\), the ordinary walk has eigenvalues \(1,-1,0,0,0,0\). Looking only at the second-largest eigenvalue in the usual numerical ordering could suggest rapid decay from the zero eigenvalues, but the eigenvalue \(-1\) does not decay under powers: \((-1)^t\) alternates between \(1\) and \(-1\). The lazy walk replaces it by \((1+(-1))/2=0\), and the relevant nonconstant absolute eigenvalue becomes \(1/2\). For a mixing estimate, the largest absolute nonconstant eigenvalue must be controlled.
Using the bound as an equality. The theorem supplies an upper bound, obtained through an \(L^2\)-to-total-variation estimate. It need not equal the actual distance. In \(K_{3,3}\) after two steps the exact distance is \(1/6\), while the stated bound is \(\sqrt5/8\). A bound certifies accuracy once it is below the target; it does not by itself report the exact distribution.
Check Your Understanding
Use the definitions and estimates above to answer the following.
- For a connected regular graph with \(\lambda_*=0.8\), what is its lazy spectral gap, and what factor bounds the \(L^2\) contraction after \(t\) steps?
- Why does a fixed positive lower bound on the lazy spectral gap imply a logarithmic mixing-time bound for fixed \(\varepsilon\)?
- For the specified \(K_{3,3}\), verify directly that the two-step probabilities from \(a\) sum to \(1\).
- What event-probability guarantee follows if the total variation distance from uniform is at most \(0.01\)?
- Explain why the ordinary random walk on a connected bipartite regular graph cannot be assumed to mix just because some of its nonconstant eigenvalues are zero.