Expander walk sampling

The expander walk sampling theorem, the earliest version of which is due to Ajtai-Komlós-Szemerédi and the more general version typically attributed to Gillman, states that sampling from an expander graph is almost as good as sampling independently.

tatement

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\; ightarrow\; [0,\; 1]$ be a function on the vertices of $G$. Let $mu\; =\; E\; [f]$ denote the true 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\; [frac\{1\}\{k\}\; sum\_\{i=0\}^k\; f(Y\_i)\; -\; mu\; >\; gamma]\; 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:

:

Uses

This lemma 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 $k\; +\; O(log\; n)$. Such families exist and are efficiently constructible, e.g. the Ramanujan graphs of Lubotzky-Phillips-Sarnak.

External links

* Proofs of the expander walk sampling theorem. [http://citeseer.ist.psu.edu/gillman98chernoff.html] [http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.aoap/1028903453]