expander walk sampling

Let $G=(V,E)$ be an n-vertex expander graph with positively weighted edges, and let $A\backslash subset\; V$. Let $P$

denote the stochastic matrix of the graph, and let $\backslash lambda\_2$ be the second largest eigenvalue of $P$. Let $y\_0,\; y\_1,\; \backslash 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):=$ $\backslash lim\_\{k\backslash rightarrow\backslash infty\}\; \backslash frac\{1\}\{k\}\; \backslash sum\_\{i\; =\; 0\}^\{k-1\}\; \backslash mathbf\{1\}\_A(y\_i)$. Where

(It is well known{{Cite book|last=Doob|first=J.L.|title=Stochastic Processes|publisher=Wiley|year=1953|location=Theorem 6.1}} that almost all trajectories $y\_0,\; y\_1,\; \backslash 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,\; \backslash ldots,\; y\_\{k-1\}$ where $y\_0$ is chosen by an initial distribution $\backslash mathbf\{q\}$, for all $\backslash gamma\; >\; 0$, we have the following bound:

:$\backslash Pr\backslash left[\backslash bigg|\; \backslash frac\{1\}\{k\}\; \backslash sum\_\{i=0\}^\{k-1\}\; \backslash mathbf\{1\}\_A(y\_i)\; -\; \backslash pi(A)\backslash bigg|\; \backslash geq\; \backslash gamma\backslash right]\; \backslash leq\; C\; e^\{-\backslash frac\{1\}\{20\}\; (\backslash gamma^2\; (1-\backslash lambda\_2)\; k)\}.$

Where $C$ is dependent on $\backslash mathbf\{q\},\; G$ and $A$

.

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

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

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

Let $D=\backslash text\{diag\}(1/\backslash it\{w\}\_i\; )$ and $M=(\backslash it\{w\}\_\{ij\})$. Let $P(r)=PE\_r$ where $P$ is the stochastic matrix, $E\_r=\backslash text\{diag\}(e^\{r\backslash mathbf\{1\}\_A\})$ and $r\; \backslash ge\; 0$

. Then:

:$P\; =\; \backslash sqrt\{D\}S\backslash sqrt\{D^\{-1\}\}\; \backslash qquad\; \backslash text\{and\}\; \backslash qquad\; P(r)\; =\; \backslash sqrt\{DE\_r^\{-1\}\}S(r)\backslash sqrt\{E\_rD^\{-1\}\}$

Where $S:=\backslash sqrt\{D\}M\backslash sqrt\{D\}\; \backslash text\{\; and\; \}\; S(r)\; :=\; \backslash sqrt\{DE\_r\}M\backslash 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\{1\}\{k\}\; \backslash sum\_\{i=0\}^\{k-1\}\; \backslash mathbf\{1\}\_A(y\_i)$, $\backslash epsilon=\backslash lambda-\backslash lambda\_2$

, $\backslash epsilon\_r=\backslash lambda(r)-\backslash lambda\_2(r)$

, and let $\backslash mathbf\{1\}$ be the all-1 vector.

Lemma 1

$\backslash Pr\backslash left[t\_k-\; \backslash pi(A)\; \backslash ge\; \backslash gamma\backslash right]\; \backslash leq\; e^\{-rk(\backslash pi(A)+\backslash gamma)+k\backslash log\backslash lambda(r)\}(\backslash mathbf\{q\}P(r)^k\backslash mathbf\{1\})/\backslash lambda(r)^k$

Proof:

By Markov's inequality,

$\backslash 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_\mathbf{q}e^{rt_k}

\end{alignat}

Where $E\_\backslash mathbf\{q\}$ is the expectation of $x\_0$ chosen according to the probability distribution $\backslash mathbf\{q\}$. As this can be interpreted by summing over all possible trajectories $x\_0,x\_1,..\; .,x\_k$, hence:

$E\_\{\backslash mathbf\{q\}\}e^\{rt\}=\backslash sum\_\{x\_1,x\_2,...,x\_k\}e^\{rt\}\backslash mathbb\{q\}(x\_0)\backslash Pi\_\{i=1\}^kp\_\{x\_\{i-1\}x\_i\}=\backslash mathbf\{q\}P(r)^k\backslash mathbf\{1\}$

Combining the two results proves the lemma.

Lemma 2

For $0\backslash le\; r\; \backslash le\; 1$,

:$(\backslash mathbf\{q\}P(r)^k\backslash mathbf\{1\})/\backslash lambda(r)^k\backslash le\; (1+r)N\_\{\backslash pi,\backslash mathbf\{q\}\}$

Proof:

As eigenvalues of $P(r)$ and $S(r)$ are equal,

$\backslash begin\{align\}$

(\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\\ &\le e^{r/2}||\frac{\mathbf{q}}{\sqrt{\pi}}||_2||S(r)^k||_2||\sqrt{\pi}||_2/\lambda(r)^k\\

&\le e^{r/2}N_{\pi,\mathbf{q}}\\

&\le (1+r)N_{\pi,\mathbf{q}}\qquad \square

\end{align}

Lemma 3

If $r$ is a real number such that $0\backslash le\; e^r-1\backslash le\; \backslash epsilon/4$,

:$\backslash log\backslash lambda(r)\backslash le\; r\backslash pi(A)+5r^2/\backslash epsilon$

Proof summary:

We Taylor expand $\backslash log\; \backslash lambda(y)$

about point $r=z$

to get:

:$\backslash log\backslash lambda(r)=\; \backslash log\backslash lambda(z)+m\_z(r-z)+(r-z)^2\backslash int\_0^1\; (1-t)V\_\{z+(r-z)t\}dt$

Where $m\_x\; \backslash text\{\; and\; \}\; V\_x$ are first and second derivatives of $\backslash log\; \backslash lambda(r)$ at $r=x$. We show that $m\_0=\backslash lim\_\{k\; \backslash to\; \backslash infty\}t\_k=\backslash 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\backslash le\; 10/\backslash epsilon$ using (i) and Cauchy's estimate from complex analysis.

The results combine to show that

:$\backslash begin\{align\}$

\log\lambda(r)= \log\lambda(0)+m_0r+r^2\int_0^1 (1-t)V_{rt}dt

\le r\pi(A)+5r^2/\epsilon

\end{align}

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

Proof of theorem

Combining lemma 2 and lemma 3, we get that

:$\backslash Pr[t\_k-\backslash pi(A)\backslash ge\; \backslash gamma]\backslash le(1+r)N\_\{\backslash pi,\backslash mathbf\{q\}\}e^\{-k(r\backslash gamma-5r^2/\backslash epsilon)\}$

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

:$\backslash Pr[t\_k-\backslash pi(A)\backslash ge\; \backslash gamma]\backslash le(1+\backslash gamma\backslash epsilon/10)N\_\{\backslash pi,\backslash mathbf\{q\}\}e^\{-k\backslash gamma^2\backslash epsilon/20\}$

A similar bound

:$\backslash Pr[t\_k-\backslash pi(A)\backslash le\; -\; \backslash gamma]\backslash le\; (1+\backslash gamma\backslash epsilon/10)N\_\{\backslash pi,\backslash mathbf\{q\}\}e^\{-k\backslash gamma^2\backslash epsilon/20\}$

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

This theorem is useful in randomness reductions in the study of derandomization,{{cite arXiv | eprint=2501.07752 | last1=Anand | first1=Emile | title=Towards the Pseudorandomness of Expander Random Walks for Read-Once ACC0 circuits | date=2025 | class=cs.CC }} showing that expander random walks are good pseudorandom generators against various classes of test functions. 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\; \backslash log\; n$, whereas if we sample from an infinite family of constant-degree expanders this costs only $\backslash log\; n\; +\; O(k)$. Such families exist and are efficiently constructible, e.g. the Ramanujan graphs of Lubotzky-Phillips-Sarnak.

{{Reflist}}

{{refbegin}}

• {{Cite conference|first1=M.|conference=STOC '87|last1=Ajtai|first2=J.|last2=Komlós|first3=E.|last3=Szemerédi|title=Deterministic simulation in LOGSPACE|book-title=Proceedings of the nineteenth annual ACM symposium on Theory of computing|pages=132–140|year=1987|work=ACM|doi=10.1145/28395.28410|isbn=0897912217|doi-access=free}}
• {{cite journal

| first=D. | last=Gillman

| s2cid=26319459

| title=A Chernoff Bound for Random Walks on Expander Graphs

| journal=SIAM Journal on Computing

| volume=27

| pages=1203–1220

| year=1998

| publisher=Society for Industrial and Applied Mathematics

| doi=10.1137/S0097539794268765

| issue=4

}}

• {{Citation|last=Doob|first=J.L.|title=Stochastic Processes|volume=Theorem 6.1|publication-date=1953|publisher=Wiley}}
• {{cite arXiv| eprint=2501.07752 | last1=Anand | first1=Emile | title=Towards the Pseudorandomness of Expander Random Walks for Read-Once ACC0 circuits | date=2025 | class=cs.CC }}

{{refend}}

Category:Sampling (statistics)