Expander walk sampling

Let ${\displaystyle G=(V,E)}$ be an n-vertex expander graph with positively weighted edges, and let ${\displaystyle A\subset V}$. Let ${\displaystyle P}$ denote the stochastic matrix of the graph, and let ${\displaystyle \lambda _{2}}$ be the second largest eigenvalue of ${\textstyle P}$. Let ${\displaystyle y_{0},y_{1},\ldots ,y_{k-1}}$ denote the vertices encountered in a ${\displaystyle (k-1)}$-step random walk on ${\displaystyle G}$ starting at vertex ${\displaystyle y_{0}}$, and let ${\textstyle \pi (A):=}$ ${\displaystyle \lim _{k\rightarrow \infty }{\frac {1}{k}}\sum _{i=0}^{k-1}\mathbf {1} _{A}(y_{i})}$. Where ${\textstyle \mathbf {1} _{A}(y){\begin{cases}1,&{\text{if }}y\in A\\0,&{\text{otherwise }}\end{cases}}}$

(It is well known[1] that almost all trajectories ${\displaystyle y_{0},y_{1},\ldots ,y_{k-1}}$ converges to some limiting point, ${\textstyle \pi (A)}$, as ${\textstyle k\rightarrow }$${\textstyle \infty }$.)

The theorem states that for a weighted graph ${\displaystyle G=(V,E)}$ and a random walk ${\displaystyle y_{0},y_{1},\ldots ,y_{k-1}}$ where ${\displaystyle y_{0}}$ is chosen by an initial distribution ${\textstyle \mathbf {q} }$, for all ${\displaystyle \gamma >0}$, we have the following bound:

${\displaystyle \Pr \left[{\bigg |}{\frac {1}{k}}\sum _{i=0}^{k-1}\mathbf {1} _{A}(y_{i})-\pi (A){\bigg |}\geq \gamma \right]\leq Ce^{-{\frac {1}{20}}(\gamma ^{2}(1-\lambda _{2})k)}.}$

Where ${\displaystyle C}$ is dependant on ${\displaystyle \mathbf {q} ,G}$ and ${\displaystyle A}$.

The theorem gives a bound for the rate of convergence to ${\displaystyle \pi (A)}$ with respect to the length of the random walk, hence giving a more efficient method to estimate ${\displaystyle \pi (A)}$ compared to independent sampling the vertices of ${\displaystyle G}$.

In order to prove the theorem, we provide a few definitions followed by three lemmas.

Let ${\displaystyle {\it {{w}_{xy}}}}$ be the weight of the edge ${\displaystyle xy\in E(G)}$ and let ${\textstyle {\it {{w}_{x}=\sum _{y:xy\in E(G)}{\it {{w}_{xy}.}}}}}$ Denote by ${\textstyle \pi (x):={\it {{w}_{x}/\sum _{y\in V}{\it {{w}_{y}}}}}}$. Let ${\textstyle {\frac {\mathbf {q} }{\sqrt {\pi }}}}$ be the matrix with entries${\textstyle {\frac {\mathbf {q} (x)}{\sqrt {\pi (x)}}}}$ , and let ${\textstyle N_{\pi ,\mathbf {q} }=||{\frac {\mathbf {q} }{\sqrt {\pi }}}||_{2}}$.

Let ${\displaystyle D={\text{diag}}(1/{\it {{w}_{i})}}}$ and ${\displaystyle M=({\it {{w}_{ij})}}}$. Let ${\textstyle P(r)=PE_{r}}$ where ${\textstyle P}$ is the stochastic matrix, ${\textstyle E_{r}={\text{diag}}(e^{r\mathbf {1} _{A}})}$ and ${\textstyle r\geq 0}$. Then:

${\displaystyle P={\sqrt {D}}S{\sqrt {D^{-1}}}\qquad {\text{and}}\qquad P(r)={\sqrt {DE_{r}^{-1}}}S(r){\sqrt {E_{r}D^{-1}}}}$

Where ${\displaystyle S:={\sqrt {D}}M{\sqrt {D}}{\text{ and }}S(r):={\sqrt {DE_{r}}}M{\sqrt {DE_{r}}}}$. As ${\displaystyle S}$ and ${\displaystyle S(r)}$ are symmetric, they have real eigenvalues. Therefore, as the eigenvalues of ${\displaystyle S(r)}$ and ${\displaystyle P(r)}$ are equal, the eigenvalues of ${\textstyle P(r)}$ are real. Let ${\textstyle \lambda (r)}$ and ${\textstyle \lambda _{2}(r)}$ be the first and second largest eigenvalue of ${\textstyle P(r)}$ respectively.

For convenience of notation, let ${\textstyle t_{k}={\frac {1}{k}}\sum _{i=0}^{k-1}\mathbf {1} _{A}(y_{i})}$, ${\textstyle \epsilon =\lambda -\lambda _{2}}$, ${\textstyle \epsilon _{r}=\lambda (r)-\lambda _{2}(r)}$, and let ${\displaystyle \mathbf {1} }$ be the all-1 vector.

Lemma 1

${\displaystyle \Pr \left[t_{k}-\pi (A)\geq \gamma \right]\leq e^{-rk(\pi (A)+\gamma )+k\log \lambda (r)}(\mathbf {q} P(r)^{k}\mathbf {1} )/\lambda (r)^{k}}$

Proof:

By Markov’s inequality,

${\displaystyle {\begin{alignedat}{2}\Pr \left[t_{k}\geq \pi (A)+\gamma \right]=\Pr[e^{rt_{k}}\geq e^{rk(\pi (A)+\gamma )}]\leq e^{-rk(\pi (A)+\gamma )}E_{\mathbf {q} }e^{rt_{k}}\end{alignedat}}}$

Where ${\displaystyle E_{\mathbf {q} }}$ is the expectation of ${\displaystyle x_{0}}$ chosen according to the probability distribution ${\displaystyle \mathbf {q} }$. As this can be interpreted by summing over all possible trajectories ${\displaystyle x_{0},x_{1},...,x_{k}}$, hence:

${\displaystyle E_{\mathbf {q} }e^{rt}=\sum _{x_{1},x_{2},...,x_{k}}e^{rt}\mathbb {q} (x_{0})\Pi _{i=1}^{k}p_{x_{i-1}x_{i}}=\mathbf {q} P(r)^{k}\mathbf {1} }$

Combining the two results proves the lemma.

Lemma 2

For ${\displaystyle 0\leq r\leq 1}$,

${\displaystyle (\mathbf {q} P(r)^{k}\mathbf {1} )/\lambda (r)^{k}\leq (1+r)N_{\pi ,\mathbf {q} }}$

Proof:

As eigenvalues of ${\displaystyle P(r)}$ and ${\displaystyle S(r)}$ are equal,

${\displaystyle {\begin{aligned}(\mathbf {q} P(r)^{k}\mathbf {1} )/\lambda (r)^{k}&=(\mathbf {q} P{\sqrt {DE_{r}^{-1}}}S(r)^{k}{\sqrt {D^{-1}E_{r}}}\mathbf {1} )/\lambda (r)^{k}\\&\leq e^{r/2}||{\frac {\mathbf {q} }{\sqrt {\pi }}}||_{2}||S(r)^{k}||_{2}||{\sqrt {\pi }}||_{2}/\lambda (r)^{k}\\&\leq e^{r/2}N_{\pi ,\mathbf {q} }\\&\leq (1+r)N_{\pi ,\mathbf {q} }\qquad \square \end{aligned}}}$

Lemma 3

If ${\displaystyle r}$ is a real number such that ${\displaystyle 0\leq e^{r}-1\leq \epsilon /4}$,

${\displaystyle \log \lambda (r)\leq r\pi (A)+5r^{2}/\epsilon }$

Proof summary:

We Taylor expand ${\textstyle \log \lambda (y)}$ about point ${\textstyle r=z}$ to get:

${\displaystyle \log \lambda (r)=\log \lambda (z)+m_{z}(r-z)+(r-z)^{2}\int _{0}^{1}(1-t)V_{z+(r-z)t}dt}$

Where ${\displaystyle m_{x}{\text{ and }}V_{x}}$ are first and second derivatives of ${\displaystyle \log \lambda (r)}$ at ${\displaystyle r=x}$. We show that ${\displaystyle m_{0}=\lim _{k\to \infty }t_{k}=\pi (A).}$ We then prove that (i) ${\textstyle \epsilon _{r}\geq 3\epsilon /4}$ by matrix manipulation, and then prove (ii)${\displaystyle V_{r}\leq 10/\epsilon }$ using (i) and Cauchy’s estimate from complex analysis.

The results combine to show that

${\displaystyle {\begin{aligned}\log \lambda (r)=\log \lambda (0)+m_{0}r+r^{2}\int _{0}^{1}(1-t)V_{rt}dt\leq r\pi (A)+5r^{2}/\epsilon \end{aligned}}}$

A line to line proof can be found in Gilman (1998)

Proof of theorem

Combining lemma 2 and lemma 3, we get that

${\displaystyle \Pr[t_{k}-\pi (A)\geq \gamma ]\leq (1+r)N_{\pi ,\mathbf {q} }e^{-k(r\gamma -5r^{2}/\epsilon )}}$

Interpreting the exponent on the right hand side of the inequality as a quadratic in ${\displaystyle r}$ and minimising the expression, we see that

${\displaystyle \Pr[t_{k}-\pi (A)\geq \gamma ]\leq (1+\gamma \epsilon /10)N_{\pi ,\mathbf {q} }e^{-k\gamma ^{2}\epsilon /20}}$

A similar bound

${\displaystyle \Pr[t_{k}-\pi (A)\leq -\gamma ]\leq (1+\gamma \epsilon /10)N_{\pi ,\mathbf {q} }e^{-k\gamma ^{2}\epsilon /20}}$

holds, hence setting ${\displaystyle C=2(1+\gamma \epsilon /10)N_{\pi ,\mathbf {q} }}$ gives the desired result.

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.