From the Spectral Gap to Variance Contraction
A random walk averages a function over the neighbors of each vertex. Repeated averaging often smooths out differences between vertices, but a single step need not reduce every measure of variation. The eigenvalues of the walk operator give the precise one-step answer: the largest absolute value of a nonconstant eigenvalue determines the strongest possible contraction in squared norm.
There is an important qualification. The ordinary spectral gap \(1-\lambda_2\), where \(\lambda_2\) is the second-largest eigenvalue, controls how far eigenvalues lie below \(1\). It does not rule out an eigenvalue near \(-1\), which can preserve variation while reversing its sign. For one-step squared-norm contraction, we must account for both ends of the spectrum.
Random Walks and Variance on Regular Graphs
Throughout, \(G=(V,E)\) is a finite, connected, simple \(d\)-regular graph with \(d\ge 1\). Write \(n=|V|\). The simple random walk moves from a vertex to one of its \(d\) neighbors, chosen uniformly. Its transition operator \(P\) acts on a function \(f:V\to\mathbb R\) by averaging over neighbors:
The uniform probability measure on \(V\) is stationary: each vertex has probability \(1/n\), and regularity makes the transition matrix symmetric. Use the inner product and mean
Since \(P\mathbf{1}=\mathbf{1}\) and \(P\) preserves the mean, the centered function after one step is \(Pf-\overline f\mathbf{1}=P(f-\overline f\mathbf{1})\). It therefore suffices to study \(P\) on mean-zero functions. The matrix of \(P\) is the adjacency matrix divided by \(d\), so it is real and symmetric. By the spectral theorem for real symmetric matrices, it has an orthonormal basis of real eigenvectors.
Connectedness ensures that the eigenvalue \(1\) belongs only to constant functions. To see why, suppose \(Pf=f\). The identity below follows by expanding the squares and using \(d\)-regularity:
The left side is zero when \(Pf=f\), so every summand on the right is zero. Thus \(f\) has the same value at the endpoints of every edge. Since \(G\) is connected, \(f\) is constant. Also, all eigenvalues lie in \([-1,1]\): for every \(f\), the inequality that the square of an average is at most the average of the squares gives \(\|Pf\|^2\le\|f\|^2\). Applying this to an eigenvector gives \(|\lambda_i|\le1\).
The One-Step Contraction Theorem
Proof. Subtract the mean from \(f\), writing \(g=f-\overline f\mathbf{1}\). Mean preservation gives \(Pg=Pf-\overline f\mathbf{1}\), so \(\operatorname{Var}(f)=\|g\|^2\) and \(\operatorname{Var}(Pf)=\|Pg\|^2\). The function \(g\) is orthogonal to the constants. Expand it in an orthonormal eigenbasis \(u_2,\ldots,u_n\) for the orthogonal complement of the constants: \(g=\sum_{i=2}^n a_i u_i\). Then \(Pg=\sum_{i=2}^n a_i\lambda_i u_i\). Orthonormality gives \(\|Pg\|^2=\sum_{i=2}^n a_i^2\lambda_i^2\le\rho^2\sum_{i=2}^n a_i^2=\rho^2\|g\|^2\). This proves the inequality. If \(\rho>0\), choose an eigenvector \(g=u_j\) with \(|\lambda_j|=\rho\); then \(\|Pg\|^2=\lambda_j^2\|g\|^2=\rho^2\|g\|^2\), proving sharpness. If \(\rho=0\), every mean-zero eigenvalue is zero, so \(Pg=0\); for general \(f\), \(Pf=\overline f\mathbf{1}\). \(\square\)
The square in this result matters: the theorem bounds variance, which is a squared norm. The corresponding norm bound is \(\|Pf\|\le\rho\|f\|\) for mean-zero \(f\). If the walk operator has only nonnegative eigenvalues, then \(\rho=\lambda_2\), so the ordinary gap suffices and the variance factor is \(\lambda_2^2=(1-\gamma)^2\). Without that extra condition, \(\lambda_n\) may have larger absolute value than \(\lambda_2\).
Worked Example: One-Step Contraction on \(K_4\)
Let \(G=K_4\), with \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24,34\}\). Every vertex has degree \(3\), so \((Pf)(i)\) is the average of the values at the other three vertices.
The eigenvalues can be found directly. For a function \(f\), \((Pf)(i)=(\sum_j f(j)-f(i))/3\). For a constant function this equals the same constant, so the constant eigenvalue is \(1\). For a mean-zero function, \(\sum_j f(j)=0\), giving \(Pf=-f/3\). Thus all three eigenvalues on the mean-zero subspace are \(-1/3\). Consequently, \(\rho=1/3\), \(\gamma=1-(-1/3)=4/3\), and \(\gamma_{\mathrm{abs}}=1-1/3=2/3\).
Take \(f=(1,-1,0,0)\), whose mean is \((1-1+0+0)/4=0\). Its variance is \((1^2+(-1)^2+0^2+0^2)/4=1/2\). Since \(Pf=-f/3\), we obtain \(Pf=(-1/3,1/3,0,0)\), with mean zero and variance \(((1/9)+(1/9)+0+0)/4=1/18\). The ratio is \((1/18)/(1/2)=1/9=\rho^2\).
Check: The theorem predicts \(\operatorname{Var}(Pf)\le(1/3)^2(1/2)=1/18\); the direct calculation gives exactly \(1/18\). This function is an eigenfunction, so it attains the bound.
Worked Example: Why the Ordinary Gap Can Mislead
Let \(G=C_4\), with \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\). This is a connected 2-regular graph. Its transition operator averages the values at the two neighboring vertices.
The constant vector \((1,1,1,1)\) has eigenvalue \(1\). The vectors \((1,0,-1,0)\) and \((0,1,0,-1)\) are sent to zero, so each has eigenvalue \(0\). The alternating vector \(h=(1,-1,1,-1)\) is sent to \(-h\): each vertex has two neighbors with value opposite its own. These four independent vectors give all eigenvalues \(1,0,0,-1\). Therefore \(\lambda_2=0\), the ordinary gap is \(\gamma=1\), but \(\rho=1\) and \(\gamma_{\mathrm{abs}}=0\).
The function \(h\) has mean \((1-1+1-1)/4=0\) and variance \((1+1+1+1)/4=1\). Since \(Ph=-h\), its variance after one step is also \(1\). Thus there is no strict one-step variance contraction, despite the ordinary gap being \(1\).
Check: Substituting \(\rho=1\) into the theorem gives \(\operatorname{Var}(Ph)\le1^2\operatorname{Var}(h)=1\), and the direct calculation gives equality. The negative eigenvalue, not the eigenvalue \(0\), sets the contraction factor.
Worked Example: A Lazy Walk on \(C_4\)
On the same graph, define the lazy operator \(Q=(I+P)/2\): at each step, the walk stays at its current vertex with probability \(1/2\), and otherwise makes a simple random-walk step. This example uses laziness to show how changing the operator changes the one-step contraction.
If \(Pu=\lambda u\), then \(Qu=(1+\lambda)u/2\). Applying this to the four eigenvalues \(1,0,0,-1\) found above, the eigenvalues of \(Q\) are \(1,1/2,1/2,0\). Hence the absolute spectral radius away from constants is \(\rho_Q=1/2\), and the variance contraction factor is \(\rho_Q^2=1/4\).
For a direct calculation, take \(f=(1,0,-1,0)\). Its mean is \(0\) and its variance is \((1+0+1+0)/4=1/2\). The earlier eigenvalue calculation gives \(Pf=0\), so \(Qf=(f+Pf)/2=f/2=(1/2,0,-1/2,0)\). Its mean is \(0\), and its variance is \((1/4+0+1/4+0)/4=1/8\). The ratio is \((1/8)/(1/2)=1/4\).
Check: The theorem for \(Q\) gives \(\operatorname{Var}(Qf)\le(1/2)^2(1/2)=1/8\), matching the direct calculation. The eigenvalue \(-1\) of \(P\) becomes \(0\) for \(Q\), while the eigenvalues \(0\) become \(1/2\); all are now nonnegative.
How to Interpret the Bound
The bound is sharp as a statement about all mean-zero functions: a function aligned with an eigenvector of largest nonconstant absolute eigenvalue contracts exactly at the stated rate. A particular function may contract faster, because its eigenvector expansion may place little or no weight on the eigenvalues of magnitude \(\rho\). In the proof, this is visible in the sum \(\sum_{i=2}^n a_i^2\lambda_i^2\): each component is multiplied by its own squared eigenvalue.
Connectedness is essential to this formulation. If the graph is disconnected, functions that are constant on each component can be mean-zero without being constant on the whole graph. Such functions are fixed by \(P\), so the absolute spectral radius away from global constants is \(1\), and no strict contraction holds for every mean-zero function.
Common mistake: On \(C_4\), one might calculate \(\lambda_2=0\), set the contraction factor to \(0^2\), and conclude that every mean-zero function is sent to zero. This misses the eigenvalue \(-1\). The correction is to calculate the maximum absolute value over all nonconstant eigenvalues: \(\rho=\max(|0|,|0|,|-1|)=1\). The theorem then correctly allows no contraction. Whenever the claim concerns one-step squared norms, check both positive and negative ends of the spectrum.
Check Your Understanding
Use the definitions and the eigenvalues of the stated operators to answer each question.
- For a connected regular graph with nonconstant eigenvalues \(1/3\) and \(-2/3\), compute the ordinary gap and the absolute spectral gap. What one-step variance factor does the theorem give?
- Why does a mean-zero eigenfunction with eigenvalue \(-1\) keep the same variance after one step?
- Suppose a connected regular graph has nonnegative eigenvalues. Express the theorem’s variance factor in terms of its ordinary spectral gap.
- For \(C_4\), what eigenvalue does the lazy operator \((I+P)/2\) assign to an eigenfunction of \(P\) with eigenvalue \(-1\)?
- Explain why connectedness matters when defining contraction for every function with global mean zero.