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 Ajtai, Komlós & Szemerédi (1987), and the more general version is typically attributed to Gillman (1998).
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:
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.
- Ajtai, M.; Komlós, J.; Szemerédi, E. (1987), "Proceedings of the nineteenth annual ACM symposium on Theory of computing", ACM: 132–140, doi:10.1145/28395.28410
- Gillman, D. (1998), "A Chernoff Bound for Random Walks on Expander Graphs", SIAM Journal on Computing (Society for Industrial and Applied Mathematics) 27 (4,): 1203–1220, doi:10.1137/S0097539794268765