Expander walk sampling

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

${\displaystyle \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 ${\displaystyle \Omega }$ hides an absolute constant ${\displaystyle \geq 1/10}$. An identical bound holds in the other direction:

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

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

• Proofs of the expander walk sampling theorem.