Expander walk sampling explained

In the mathematical discipline of graph theory, the expander walk sampling theorem intuitively states that sampling vertices in an expander graph by doing relatively short random walk can simulate sampling the vertices independently from a uniform distribution.The earliest version of this theorem is due to, and the more general version is typically attributed to .

Statement

Let

G = (V,E) be an n-vertex expander graph with positively weighted edges, and let A\subset V . Let P denote the stochastic matrix of the graph, and let λ _{2} be the second largest eigenvalue of $P$. Let y _{0,} y _{1,} \ldots, y _{k-1} denote the vertices encountered in a (k -1 ) -step random walk on G starting at vertex y _{0} , and let $\backslash pi\; (A):=$ \lim _{k → infty} (1)/(k) \sum ^{k -1} _{i =0} 1 _{A(y} _{i)} . Where

(It is well known^[1] that almost all trajectories

y _{0,} y _{1,} \ldots, y _{k-1} converges to some limiting point, $\backslash pi\; (A)$, as $k\; \backslash rightarrow$$\backslash infty$

.)

The theorem states that for a weighted graph

G = (V,E) and a random walk y _{0,} y _{1,} \ldots, y _{k-1} where y _{0} is chosen by an initial distribution $\backslash mathbf$, for all \gamma > 0 , we have the following bound:\Pr\left[ | (1)/(k) \sum ^{k -1} _{i =0} 1 _{A(y} _{i)} - \pi(A) | \geq \gamma\right] \leq C e ^{- (1)/((\gamma ^{2} ( 1-λ _{2)} k) 20)} .

Where

C is dependent on q , G and A .

The theorem gives a bound for the rate of convergence to

\pi(A) with respect to the length of the random walk, hence giving a more efficient method to estimate \pi(A) compared to independent sampling the vertices of G .

Proof

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

Let

\it{w} _{xy} be the weight of the edge xy\in E(G) and let $\backslash it\_x=\backslash sum\_\backslash it\_.$ Denote by $\backslash pi(x):=\backslash it\_x/\backslash sum\_\; \backslash it\_y$. Let $\backslash frac$ be the matrix with entries$\backslash frac$, and let $N\_=||\backslash frac||\_$.

Let

D = diag ( 1 /\it{w} _{i} ) and M = (\it{w} _{ij} ) . Let $P(r)=PE\_r$ where $P$ is the stochastic matrix, $E\_r=\backslash text(e^)$ and $r\; \backslash ge\; 0$. Then:P = \sqrt{D}S\sqrt{D ^{-1} } \qquad \text \qquad P(r) = \sqrtS(r)\sqrtWhere S: = \sqrt{D}M\sqrt{D} and S(r) : = \sqrt{DE _{r}M\sqrt{DE} _{r}} . As S and S(r) are symmetric, they have real eigenvalues. Therefore, as the eigenvalues of S(r) and P(r) are equal, the eigenvalues of $P(r)$ are real. Let $\backslash lambda(r)$ and $\backslash lambda\_2(r)$ be the first and second largest eigenvalue of $P(r)$ respectively.

For convenience of notation, let $t\_k=\backslash frac\; \backslash sum\_^\; \backslash mathbf\_A(y\_i)$, $\backslash epsilon=\backslash lambda-\backslash lambda\_2$, $\backslash epsilon\_r=\backslash lambda(r)-\backslash lambda\_2(r)$, and let

1 be the all-1 vector.

Lemma 1

\Pr\left[t _{k-} \pi(A) \ge \gamma\right] \leq e ^{-rk(\pi(A)+\gamma)+klogλ(r)} ( q P(r) ^{k1)/λ(r)} ^{k}

Proof:

By Markov's inequality,

\begin{alignat}{ 2 } \Pr\left[t _{k} \ge \pi(A) + \gamma\right] = \Pr[e ^{rt _{k}} \ge e ^{rk(\pi(A)+\gamma)} ]\leq e ^{-rk(\pi(A)+\gamma)} E ^{rt _{k}} _{q e} \end{alignat}

Where

E _{q} is the expectation of x _{0} chosen according to the probability distribution q . As this can be interpreted by summing over all possible trajectories x _{0,x} _{1,..} .,x _{k} , hence:E _{q} e ^{rt} = \sum _{x _{1,x} _{2,...,x} _{k}} e ^{rt} q (x _{0)\Pi} ^{kp} ^{x _{i-1} x _{i}} = q P(r) ^{k1}

Combining the two results proves the lemma.

Lemma 2

For

0 \le r \le 1 ,( q P(r) ^{k1)/λ(r)} ^{k\le} ( 1+ r)N _{\pi,q} Proof:

As eigenvalues of

P(r) and S(r) are equal,\begin{align} ( q P(r) ^{k1)/λ(r)} ^{k&=} ( q P\sqrt{DE ^{-1} _{r} }S(r)^k \sqrt\mathbf)/\lambda(r)^k\\ &\le e^||\frac||_2||S(r)^k||_2||\sqrt||_2/\lambda(r)^k\\&\le e^N_\\&\le (1+r)N_\qquad \square\end

Lemma 3

If

r is a real number such that 0 \le e ^{r-1\le} \epsilon/ 4 ,logλ (r)\le r\pi(A) +5 r ^{2/\epsilon} Proof summary:

We Taylor expand $\backslash log\; \backslash lambda(y)$ about point $r=z$ to get:

logλ (r) = logλ (z) + m ^{1} _{0} ( 1- t)V _{z+(r-z)t} dt Where m _{x} and V _{x} are first and second derivatives of log λ (r) at r = x . We show that m _{0=\lim} _{k} t _{k=\pi(A).} We then prove that (i) $\backslash epsilon\_r\backslash ge\; 3\backslash epsilon/4$ by matrix manipulation, and then prove (ii)V _{r\le} 10 /\epsilon using (i) and Cauchy's estimate from complex analysis.

The results combine to show that

\begin{align} logλ (r) = logλ ( 0 ) + m ^{1} _{0} ( 1- t)V _{rt} dt \le r\pi(A) +5 r ^{2/\epsilon \end{align}}

A line to line proof can be found in Gilman (1998)https://epubs.siam.org/doi/pdf/10.1137/S0097539794268765#page23Proof of theorem

Combining lemma 2 and lemma 3, we get that

\Pr[t _{k-\pi(A)\ge} \gamma]\le( 1+ r)N _{\pi,q} e ^{- k(r\gamma -5 r ^{2/\epsilon)}} Interpreting the exponent on the right hand side of the inequality as a quadratic in r and minimising the expression, we see that \Pr[t _{k-\pi(A)\ge} \gamma]\le( 1+ \gamma\epsilon/ 10 )N _{\pi,q} e ^{- k\gamma ^{2\epsilon/20}} A similar bound\Pr[t _{k-\pi(A)\le} - \gamma]\le ( 1+ \gamma\epsilon/ 10 )N _{\pi,q} e ^{- k\gamma ^{2\epsilon/20}} holds, hence setting C =2 ( 1+ \gamma\epsilon/ 10 )N _{\pi,q} gives the desired result.

Uses

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.

References

• M.. STOC '87. Ajtai. J.. Komlós. E.. Szemerédi. Deterministic simulation in LOGSPACE. Proceedings of the nineteenth annual ACM symposium on Theory of computing. 132–140. 1987. ACM. 10.1145/28395.28410. 0897912217. free.
• D. . Gillman . 26319459 . A Chernoff Bound for Random Walks on Expander Graphs . SIAM Journal on Computing . 27 . 1203–1220 . 1998 . Society for Industrial and Applied Mathematics . 10.1137/S0097539794268765 . 4.

Notes and References

1. Book: Doob, J.L.. Stochastic Processes. Wiley. 1953. Theorem 6.1.