Expander walk sampling


In the mathematical discipline of graph theory, the expander walk sampling theorem states that sampling vertices in an expander graph by doing a random walk is almost as good as sampling the vertices independently from a uniform distribution.
The earliest version of this theorem is due to, and the more general version is typically attributed to.

Statement

Let be an expander graph with normalized second-largest eigenvalue. Let denote the number of vertices in. Let be a function on the vertices of. Let denote the mean of, i.e.. Then, if we let denote the vertices encountered in a -step random walk on starting at a random vertex, we have the following for all :
Here the hides an absolute constant. An identical bound holds in the other direction:

Uses

This theorem is useful in randomness reduction in the study of derandomization. Sampling from an expander walk is an example of a randomness-efficient sampler. Note that the number of bits used in sampling independent samples from is, 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.