In the mathematical discipline of graph theory, the expander walk sampling theorem intuitively states that sampling vertices in an expander graph by doing relatively short random walk can simulate sampling the vertices independently from a uniform distribution.
The earliest version of this theorem is due to Ajtai, Komlós & Szemerédi (1987), and the more general version is typically attributed to Gillman (1998).
be an n-vertex expander graph with positively weighted edges, and let
denote the stochastic matrix of the graph, and let
be the second largest eigenvalue of
denote the vertices encountered in a
converges to some limiting point,
The theorem states that for a weighted graph
is chosen by an initial distribution
The theorem gives a bound for the rate of convergence to
with respect to the length of the random walk, hence giving a more efficient method to estimate
compared to independent sampling the vertices of
In order to prove the theorem, we provide a few definitions followed by three lemmas.
are symmetric, they have real eigenvalues.
) + γ ) + k log λ ( r )
Proof: By Markov's inequality,
chosen according to the probability distribution
As this can be interpreted by summing over all possible trajectories
Combining the two results proves the lemma.
, Proof summary: We Taylor expand
by matrix manipulation, and then prove (ii)
using (i) and Cauchy's estimate from complex analysis.
The results combine to show that Proof of theorem Combining lemma 2 and lemma 3, we get that Interpreting the exponent on the right hand side of the inequality as a quadratic in
and minimising the expression, we see that A similar bound holds, hence setting
gives the desired result.
This theorem is useful in randomness reductions in the study of derandomization [2], showing that expander random walks are good pseudorandom generators against various classes of test functions.
Sampling from an expander walk is an example of a randomness-efficient sampler.
Note that the number of bits used in sampling
, whereas if we sample from an infinite family of constant-degree expanders this costs only
Such families exist and are efficiently constructible, e.g. the Ramanujan graphs of Lubotzky-Phillips-Sarnak.