Motivation
Repeated independent samples can be expensive when drawing a fresh random vertex requires many random bits. A random walk reuses its current vertex: at each step it chooses a neighbor. Whether this produces a nearly uniform sample depends on the graph. A graph can be connected yet mix slowly, and a connected bipartite graph can alternate forever between its two sides. Eigenvalues give a quantitative way to distinguish these behaviors. This unit proves a mixing estimate; using walks for full randomness-efficient amplification requires further joint-event bounds and is not claimed here.
Definitions
Definition 5.2.1
(Transition matrix and second absolute eigenvalue)
Let be a finite undirected -regular graph with vertices and . The transition matrix is , where is the adjacency matrix. Use column probability vectors: . Because is symmetric and each column sums to one, the uniform distribution is stationary. The real spectral theorem supplies an orthonormal eigenbasis. Write the eigenvalues as , choosing the normalized constant vector for , and let .
Definition 5.2.2
(Total variation distance)
For probability vectors , their total variation distance is . It equals the maximum, over vertex sets , of . To see this, let be the vertices on which ; since the coordinate differences sum to zero, the positive sum is half the absolute sum, and no other set gives a larger absolute difference.
Theorems
Theorem 5.2.3
(Spectral mixing bound)
For every initial distribution and integer ,
In particular, starting at any single vertex gives . If , the walk converges to uniform from every starting distribution.
Theorem 5.2.4
(Eigenvalue and periodicity criteria)
Every eigenvalue of lies in . If is connected, the eigenvalue has multiplicity one. If is connected and non-bipartite, is not an eigenvalue. Thus for a connected non-bipartite graph .
Proof sketch or proof idea
Proof
(Contraction of the deviation from uniform)
The vector is orthogonal to the constant vector because its coordinates sum to zero. Expand it in the orthonormal eigenbasis as . Then
By Cauchy–Schwarz, . Applying this to proves the first inequality. If is a point mass, its squared distance from is , yielding the second.
Proof
(Eigenvalues, connectedness and bipartiteness)
For the eigenvalue criteria, let be a real eigenvector with eigenvalue and choose a vertex with maximal . Since is the average of neighboring coordinates, , so . If , equality in the average forces every neighbor of to have value ; connectedness propagates this equality throughout the graph. Thus every -eigenvector is constant.
If , equality forces every neighbor of to have value . Propagating through a connected graph gives alternating values along every path. An odd cycle would force a nonzero value to equal its negative, a contradiction. Therefore a connected non-bipartite graph has no eigenvalue . Since the graph has finitely many eigenvalues and all nonconstant ones lie strictly between and , their maximum absolute value is strictly less than one.
Proof X-ray
Why the deviation starts at the second eigenvector
The proof splits into the stationary part and the deviation , and everything rests on the deviation being orthogonal to the constant vector: its coordinates sum to zero. That is what lets the expansion start at , so the factor never appears and only controls the decay. Symmetry of is used to obtain an orthonormal eigenbasis, so the squared norm is the sum with no cross terms.
The absolute value in is needed because decays no faster for than for ; an eigenvalue near stalls the contraction while alternating sign. The last step, , is the only place where enters: a Euclidean contraction becomes a total variation bound only after paying that factor.
Worked examples
Worked example 5.2.5
(Walk on a triangle)
For the loopless complete graph on three vertices, . The constant vector has eigenvalue , and every vector orthogonal to it has eigenvalue . Hence . From a point mass the theorem gives total variation at most . Negative eigenvalues cause an alternating correction, but its magnitude decays geometrically.
Worked example 5.2.6
(Periodic bipartite walk)
On a four-cycle, starting from one side of its bipartition, the walk is on that same side at even times and on the other side at odd times. Uniform measure assigns probability to either side, whereas the walk assigns one at the matching parity. Total variation is therefore at least at every time. The graph is connected, but is an eigenvalue and the walk does not converge to uniform.
Worked example 5.2.7
(A sufficient number of steps)
If a graph has and , then from any vertex the total variation distance after steps is at most . At this is less than . This is a sufficient bound; the actual distance can be smaller. The estimate uses an assumed spectral bound, which must be established separately for the chosen graph.
Common mistakes
Counterexample mode
Stationarity does not imply convergence
Uniform is stationary even for the four-cycle, yet a point mass does not converge to it. Stationarity says that a walk started at uniform remains uniform; convergence says that other starting distributions approach it. These are different claims.
Common mistake
(A regular graph need not be connected)
A regular graph can be disconnected; in that case a walk cannot leave its component, and eigenvalue has additional eigenvectors. The expression then equals one for an appropriate eigenbasis.
Common mistake
(Near-uniform marginals are not independent samples)
A bound on each single-time distribution does not make successive positions independent. In particular, nearly uniform marginals alone do not prove that a walk avoids a fixed bad set with exponentially small probability.
Removing periodicity by waiting
A standard modification is the lazy walk: at each step stay at the current vertex with probability , and otherwise take one step of the original walk. Its matrix is . It is symmetric and preserves uniform measure. If , then , so its eigenvalues are obtained from those of by this transformation. The eigenvalue becomes zero. On a connected graph every nonconstant eigenvalue of is strictly less than one, and consequently every nonconstant eigenvalue of lies in . Thus the same spectral proof gives convergence for the lazy walk on every connected regular graph, including bipartite graphs.
This modification changes the experiment. It is not legitimate to prove a lazy-walk bound and silently attribute it to the original non-lazy walk. A lazy step can remain at the same vertex, while the original walk on a loopless graph cannot. On the four-cycle, for instance, starting from a vertex, a lazy step puts probability on that vertex and on each neighbor. Repetition removes the deterministic parity alternation of the original walk.
Worked example 5.2.8
(The lazy four-cycle)
The transition eigenvalues of the non-lazy four-cycle are . Under they become . Hence . Starting at any vertex, after lazy steps the total variation distance to uniform is at most . The bound proves convergence, although it is not the exact distance at every time.
From total variation to event probabilities
If a distribution is within of uniform in total variation, then for every vertex set ,
This follows from the event characterization in the definition. For example, if a set contains ten percent of the vertices and the total variation distance is at most , its probability at that time lies between and . A pointwise claim for a particular vertex is also an event claim, but a total variation bound of can be much larger than the uniform mass ; it need not give a useful relative estimate for a very rare vertex.
Concept lensCombinatorial
Counting walks of length t
Let be the number of walks of length from to . Then , so uniformity says that the endpoints of the equally likely walks from are spread evenly. Since , whose operator norm is , every entry satisfies
Each pair of vertices is joined by almost exactly the uniform number of walks.
The statement is about one time. Even a walk started at stationarity has dependent positions: at every step its next vertex must be a neighbor of the current vertex. For a loopless graph, the probability of staying at the same vertex for a step is zero, whereas two independent uniform vertices coincide with probability . Hence exactly uniform marginals do not imply independence. A proof that many visits all fall in a bad set requires additional control of correlations, not merely application of the one-time mixing bound to each visit.
If independent near-uniform samples are actually needed, one straightforward construction is to run the walk separately with independent random bits for each sample, starting each from a fixed vertex and taking enough steps. The resulting outputs are independent because they depend on disjoint random seeds. This simple approach does not obtain the random-bit savings of a single correlated walk. The latter can be analyzed using stronger expansion or spectral arguments, but those bounds require their own proof and hypotheses.
Cuts and a necessary bottleneck test
For a vertex set , write for the undirected edges with one endpoint in and the other outside. If the initial vertex is uniform on a nonempty , then the probability of leaving in one step is exactly
Indeed, each of the starting vertices is equally likely, each of its incident edges is chosen with probability , and every boundary edge is counted once from its endpoint in . This ratio measures a bottleneck for that starting distribution. If it is small, most of the probability remains in for the next step, even if uniform measure on the whole graph assigns a much smaller mass to .
More precisely, if , the one-step distribution from uniform on assigns probability to , while uniform assigns . Their total variation distance is therefore at least the difference between these two probabilities whenever that difference is positive. A small boundary is evidence against rapid one-step mixing. This elementary observation is not a proof of a general spectral expansion theorem: relating every cut ratio to eigenvalues and to all later times requires additional arguments and appropriate constants.
Regularity makes uniform measure stationary here. For a nonregular undirected graph, the simple random walk generally has stationary distribution proportional to degree, not uniform. The symmetric matrix and norm argument can be adapted by changing the inner product, but the displayed uniform conclusions cannot be carried over unchanged. Similarly, a directed graph need not have a symmetric transition matrix or an orthonormal real eigenbasis; the spectral theorem used above is a real hypothesis of the method, not a decorative step.
Interpreting the spectral estimate
The quantity is often called an absolute spectral gap. The estimate shows directly why it matters: when is close to one, many steps may be needed before is small. When , to make the point-mass bound at most , it is sufficient that
provided the numerator is positive; otherwise zero steps already satisfy this particular bound. Round the resulting number upward to an integer. If , the spectral expression shows that one step reaches uniform exactly. These are sufficient conditions derived from the inequality, not necessarily optimal mixing times.
A graph family is useful for fast mixing if a common bound holds as the number of vertices grows. For a fixed desired total variation error, the displayed estimate then requires only a number of steps proportional to the logarithm of the number of vertices. The cost of a step must still be considered. If each vertex has explicitly addressable neighbors and is a power of two, a step can be selected with uniform random bits. For other degrees, exact uniform selection requires an appropriate sampling method; simply reducing a uniformly chosen bit string modulo can introduce bias.
The spectral theorem gives a bound uniform over all starting vertices, but it can be loose for a particular start or time. It replaces every nonconstant eigenvalue magnitude by the single worst value and applies Cauchy–Schwarz. Some coefficients in a given starting vector may vanish, and the inequality between one-norm and two-norm need not be sharp. A computed exact distribution can therefore mix faster than this certificate predicts without contradicting it.
Summary
Symmetry turns the random-walk transition matrix into an orthogonally diagonalizable operator. The nonconstant eigenvalues control how fast deviations from uniform contract in Euclidean norm; Cauchy–Schwarz converts this to a total variation guarantee. Connectedness removes extra stationary directions and non-bipartiteness removes alternating directions.
Exercises
Quick check
(Compute the nonconstant eigenvalue of the walk on the loopless complete graph and give .)
Write for and use that vanishes off the constants.
Solution · Answer
Here . The matrix is zero on vectors orthogonal to the constants, so the nonconstant eigenvalue is and .
Quick check
(For and , show that suffices for the bound from a point mass.)
Substitute , and into the point-mass bound.
Solution · Answer
The bound is .
Quick check
(Why does connectedness alone not guarantee convergence to uniform?)
Consider a connected bipartite graph such as the four-cycle.
Solution · Answer
A connected bipartite graph alternates between its two sides. The four-cycle example remains at total variation distance at least from uniform when started at a vertex.
Quick check
(If , what is the total variation distance from uniform at every time?)
Is stationary?
Solution · Answer
It is zero because and hence for every .