Motivation
To reduce the chance that all trials fail, one can choose independent random seeds for repeated runs. On a large seed space this can require many random bits. A walk on a regular graph uses one random initial vertex and then a random neighbor at each step. Its vertices are correlated, so independence cannot justify a product bound. A spectral argument can nevertheless bound the probability that every visited vertex lies in a fixed bad set.
This unit states the necessary graph assumption explicitly. It does not construct an expander family or prove that one exists with a particular degree and spectrum. The gain in random bits depends on having a suitable graph whose neighbors can be computed efficiently.
Definitions
Definition 5.1.1
(Absolute spectral bound for a regular graph)
Let be a finite undirected -regular graph with vertices, , and symmetric transition matrix . The uniform probability vector is . Let and suppose that every eigenvalue of on the subspace orthogonal to has absolute value at most . Equivalently, with , the symmetric operator has norm at most .
Definition 5.1.2
(Bad set and walk sample)
Fix a set of bad vertices of relative size . Let be the diagonal matrix with for and zero otherwise. A walk starts at a uniformly chosen vertex and takes independent uniform-neighbor steps to . The positions are generally dependent even though each marginal is uniform. Define .
Theorems
Theorem 5.1.3
(Repeated visits to a fixed bad set)
For every integer ,
In particular, if then and the bound decreases exponentially in .
Theorem 5.1.4
(One-sided amplification)
Suppose a deterministic verifier, supplied a uniformly random seed vertex, has a fixed bad-seed set of relative size at most for each fixed positive input, where , and never accepts a negative input for any seed. Run it on the walk vertices and accept if any run accepts. For a fixed positive input the probability of rejecting is at most
negative inputs are still never accepted. Write for this uniform upper-bound factor.
Proof sketch or proof idea
Proof
(Quadratic-form bound on the masked operator)
For any vector supported on , Cauchy–Schwarz gives
Since , the spectral assumption gives
Here the sharper middle inequality uses vanishing on and its norm bound on the orthogonal component. For an arbitrary vector , put to obtain . The matrix is symmetric, so the real spectral theorem implies .
The probability of the all-bad event equals
The equality also holds for , interpreting the zeroth power as the identity. Apply Cauchy–Schwarz and the operator norm bound. Since , the result is at most . This directly controls a joint event; it does not assert independence of the walk positions.
Proof
(From the joint bound to amplification)
For amplification, fix the input first. Rejection means that every seed used belongs to its bad set. The first theorem applies to that fixed set, and the right-hand side is nondecreasing in on , so gives the displayed bound. On a negative input every verifier run rejects for every seed, so the combined procedure cannot accept. The guarantee is for each fixed input; it does not require one walk to work simultaneously for all inputs.
Proof X-ray
Two hypotheses, one mask, one factor per step
The proof has two moves. First, the bound for supported on combines both hypotheses: smallness of limits the component along to by Cauchy–Schwarz, and the spectral hypothesis contracts the orthogonal component by . Neither hypothesis alone gives .
Second, the diagonal mask turns the joint event into a matrix product in which every transition carries the factor of norm at most , while the first mask contributes through . Symmetry of is what upgrades a quadratic-form bound to an operator-norm bound. Independence is never used, and the bound is the same for every of relative size whatever its internal edges, which is why it can be loose, as the small triangle check later in this unit shows.
Worked examples
Worked example 5.1.5
(Numerical failure guarantee)
If , and , then and the all-bad probability is at most . The five individual seeds are not independent; this number follows from the joint-event theorem.
Worked example 5.1.6
(The one-visit case)
For , uniform initialization gives exactly. The theorem gives . No transition is needed, and the spectral bound plays no role in this case.
Worked example 5.1.7
(A complete mixing ideal)
If , then and every next vertex is uniform independently of the previous one. The bound becomes , the familiar independent-sampling probability. A sparse graph will generally have positive and a weaker bound, traded against a cheaper neighbor choice.
Common mistakes
Counterexample mode
Uniform marginals do not multiply
On a loopless regular graph a stationary walk is uniform at each time, but it cannot remain at the same vertex in one step. Its adjacent positions are therefore not independent. A product of marginal probabilities needs justification; the masked-operator calculation supplies a different joint bound. Concretely, in the triangle with one bad vertex , , yet , not .
Common mistake
(The bad set must be fixed before sampling)
The set must be fixed for the input before the walk is sampled. A different bad set chosen adaptively after seeing each vertex is not covered by this theorem.
Common mistake
(Dropping the absolute value hides negative eigenvalues)
An eigenvalue bound without absolute values also fails to control a negative eigenvalue near ; the stated operator norm hypothesis includes both signs.
Why the masked matrix contracts
The proof separates a vector into its constant and orthogonal parts. The constant part is not contracted by , which is why a bound on nonconstant eigenvalues alone cannot say that every vector shrinks. But a vector supported on a proper subset cannot be mostly constant: the Cauchy–Schwarz estimate limits its squared constant component to at most times its squared norm. The remaining component lies in the subspace where the absolute eigenvalue bound applies. A small bad set and a genuine spectral gap are both used to obtain .
For a more explicit calculation, write with . Then and . The spectral hypothesis implies . Because and , it follows that
A negative eigenvalue is included in the absolute bound on the quadratic form. Symmetry is important in the next step: for a real symmetric matrix, its operator norm is the largest absolute eigenvalue, which is the maximum absolute Rayleigh quotient. Without symmetry, a quadratic-form bound alone need not control the operator norm in the same way.
The mask is a projection: and . Multiplying by does not renormalize a probability distribution. Instead, it discards the mass at vertices outside . The remaining total mass is the probability that the corresponding sequence of membership tests has succeeded. Thus the matrix formula tracks unconditional probability; inserting a normalization after every step would change the calculation and would require tracking the normalization factors separately.
Concept lensCombinatorial
Counting walks that stay in the bad set
Each -vertex walk has probability , so the all-bad probability equals the number of walks with all vertices in , divided by . The theorem therefore says that at most such walks exist, whereas is the trivial count. The factor is an average branching limit inside : the walks stay in only through the few edges leaving a vertex of for another vertex of .
Choosing the number of visits
Set . If and , a sufficient condition for failure probability at most is
when the logarithm's numerator is positive; round upward to an integer. If , one visit already suffices for this bound. If , there are no bad seeds and the failure probability is zero. These conditions are sufficient, not a claim that the inequality is sharp for a particular graph and bad set.
For example, with and , . To make the bound at most , it suffices to choose with . The calculation gives after rounding: . This number can be checked directly rather than relying on rounded logarithms. Actual failure probability can be smaller because the operator estimate treats all vectors supported on the bad set as if they achieved the worst contraction.
Worked example 5.1.8
(A full failure-bound calculation)
Suppose an input has at most one quarter bad seeds and a graph satisfies the required absolute eigenvalue bound . For eight walk vertices, the probability that all verifier runs fail is at most . Thus accepting on any successful run gives success probability at least for that fixed positive input. The theorem does not certify that the exact success probability is equal to this value.
Randomness and algorithmic cost
If and , the initial vertex can be sampled with fair bits and each subsequent uniformly chosen neighbor with fresh fair bits, for bits total. Independent uniform seed vertices would use bits. The comparison is useful when is much smaller than . For sizes that are not powers of two, exact uniform sampling needs an explicitly specified method and its bit cost must be analyzed; a simple modulo reduction can be biased.
The seed graph must also be usable by the algorithm. A proof that some graph has small nonconstant eigenvalues is not by itself an efficient neighbor procedure. A concrete implementation needs a representation of vertices, a way to compute each indexed neighbor, a verified degree and spectral guarantee, and a way to map each vertex to a verifier seed. The number of verifier executions is still , so a saving in randomness does not automatically reduce running time. These are conditions on an application, not extra conclusions of the spectral inequality.
Uniform initialization is part of the theorem. Starting from one fixed vertex can make the all-bad probability one at the first visit if that vertex is bad. A burn-in period may make the distribution close to uniform, but its approximation error must be included in a new analysis; it is not silently covered by the displayed expression. Similarly, the set of bad seeds can depend on the fixed input, but the proof fixes that input before considering the random walk.
Interpreting one-sided error
The verifier's one-sided guarantee has two parts. On a positive input, at most a specified fraction of seeds are bad, so repeated visits can reduce the chance of missing all good seeds. On a negative input, every seed must reject. The latter property ensures that accepting on any run introduces no false positives, regardless of correlations. If negative inputs have a nonzero false-positive rate, accepting on any run may increase that error; a separate analysis and aggregation rule are needed.
The statement is uniform over inputs in the sense that the same numerical bound applies to each fixed input satisfying the hypotheses. It does not automatically imply that one randomly generated walk succeeds for every possible input at once. To derive a simultaneous statement for a finite collection, one may apply a union bound over that collection, paying a factor equal to its size. For an infinite or very large collection, further structure is required. Distinguishing these quantifiers prevents a per-input guarantee from being overstated.
A direct check in a small graph
Consider a triangle and a bad set consisting of a single vertex. Here , , and the two nonconstant eigenvalues of the simple random walk are , so and . The theorem bounds two consecutive bad visits by . In fact their probability is zero: after visiting the sole bad vertex, the loopless walk must move to a different vertex. This example illustrates both the correctness and possible looseness of the bound. A general estimate cannot assume that every bad set has this special shape.
For the event probability is exactly the set's relative size, regardless of the graph. For later steps the number and arrangement of edges inside matter. The spectral hypothesis compresses those graph-specific details into a single bound valid for every set of a given size. Two bad sets with the same number of vertices can have different internal edges and different actual all-bad probabilities, even though the same upper bound applies to both.
The assumptions also explain failure cases. If the graph is disconnected, a nonconstant eigenvector can have eigenvalue one; a walk started in a small component remains there forever. If a connected graph is bipartite, eigenvalue minus one can prevent the absolute spectral bound from being smaller than one. A lazy modification can remove periodicity, but its eigenvalues and bit cost must be recalculated for that modified walk. The companion spectral-mixing unit proves those facts for regular graphs; this unit uses the resulting absolute bound as a hypothesis.
Summary
The uniform component of a vector supported on a small set is limited by the set's size. The nonuniform component contracts by the absolute spectral bound. Together these facts bound the masked transition operator and hence the probability of staying in the bad set over an entire walk.
Exercises
Quick check
(With , and , compute the bound.)
Compute first.
Solution · Answer
Here , so the bound is .
Quick check
(Why does and imply ?)
Factor .
Solution · Answer
Since , we have .
Quick check
(What does the theorem give when is empty?)
What is for an empty set?
Solution · Answer
Then and the probability and bound are both zero for every .
Quick check
(Does a bound on each vertex marginal alone establish the all-bad bound? Explain.)
Recall the triangle with one bad vertex.
Solution · Answer
No. Successive positions are correlated. The proof instead bounds the norm of the product of masked transition operators.