Expander walk sampling

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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).

Statement[edit]

Let G = (V, E) be an expander graph with normalized second-largest eigenvalue \lambda. Let n denote the number of vertices in G. Let f : V \rightarrow [0, 1] be a function on the vertices of G. Let \mu = E[f] denote the mean of f, i.e. \mu = \frac{1}{n} \sum_{v \in V} f(v). Then, if we let Y_0, Y_1, \ldots, Y_k denote the vertices encountered in a k-step random walk on G starting at a random vertex Y_0, we have the following for all \gamma > 0:

\Pr\left[\frac{1}{k} \sum_{i=0}^k f(Y_i) - \mu > \gamma\right] \leq e^{-\Omega (\gamma^2 (1-\lambda) k)}.

Here the \Omega hides an absolute constant \geq 1/10. An identical bound holds in the other direction:

\Pr\left[\frac{1}{k} \sum_{i=0}^k f(Y_i) - \mu < -\gamma\right] \leq e^{-\Omega (\gamma^2 (1-\lambda) k)}.

Uses[edit]

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 k independent samples from f is k \log n, whereas if we sample from an infinite family of constant-degree expanders this costs only \log n + O(k). Such families exist and are efficiently constructible, e.g. the Ramanujan graphs of Lubotzky-Phillips-Sarnak.

Notes[edit]

References[edit]

  • 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  |chapter= ignored (help)
  • 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 

External links[edit]

  • Proofs of the expander walk sampling theorem. [1] [2]