エキスパンダーウォークサンプリング

グラフ理論という数学の分野において、エキスパンダーウォークサンプリング定理は、比較的短いランダムウォークを行うことでエキスパンダーグラフ内の頂点をサンプリングすると、一様分布から独立して頂点をサンプリングすることをシミュレートできることを直感的に述べています。この定理の最も古いバージョンは、Ajtai、Komlós、Szemerédi (1987) によるもので、より一般的なバージョンは、通常、Gillman (1998) によるものとされています。

を正の重み付き辺を持つn頂点拡張グラフとし 、 とする。をグラフの確率行列とし、を の2番目に大きい固有値とする。を頂点 から始まるステップランダムウォークで遭遇する頂点とし、 とする。ここで${\displaystyle G=(V,E)}$${\displaystyle A\subset V}$${\displaystyle P}$${\displaystyle \lambda _{2}}$${\textstyle P}$${\displaystyle y_{0},y_{1},\ldots ,y_{k-1}}$${\displaystyle (k-1)}$${\displaystyle G}$${\displaystyle y_{0}}$${\textstyle \pi (A):=}$ ${\displaystyle \lim _{k\rightarrow \infty }{\frac {1}{k}}\sum _{i=0}^{k-1}\mathbf {1} _{A}(y_{i})}$${\textstyle \mathbf {1} _{A}(y){\begin{cases}1,&{\text{if }}y\in A\\0,&{\text{otherwise }}\end{cases}}}$

（ほとんどすべての軌道は、として、ある極限点に収束することがよく知られています^[1]。） ${\displaystyle y_{0},y_{1},\ldots ,y_{k-1}}$${\textstyle \pi (A)}$${\textstyle k\rightarrow }$${\textstyle \infty }$

定理は、重み付きグラフとランダム ウォーク(ここでは初期分布 によって選択)に対して、すべての に対して、次の境界が成立することを述べています。 ${\displaystyle G=(V,E)}$${\displaystyle y_{0},y_{1},\ldots ,y_{k-1}}$${\displaystyle y_{0}}$${\textstyle \mathbf {q} }$${\displaystyle \gamma >0}$

${\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)}.}$

ここで、はおよびに依存します。 ${\displaystyle C}$${\displaystyle \mathbf {q} ,G}$${\displaystyle A}$

この定理は、ランダムウォークの長さに対する への収束率の上限を与えるため、の頂点を独立にサンプリングするよりも効率的な推定方法となります。 ${\displaystyle \pi (A)}$${\displaystyle \pi (A)}$${\displaystyle G}$

定理を証明するために、いくつかの定義とそれに続く 3 つの補題を示します。

を辺の重みとし、をで表します。を の要素を持つ行列とし、 とします。 ${\displaystyle {\it {{w}_{xy}}}}$${\displaystyle xy\in E(G)}$${\textstyle {\it {{w}_{x}=\sum _{y:xy\in E(G)}{\it {{w}_{xy}.}}}}}$${\textstyle \pi (x):={\it {{w}_{x}/\sum _{y\in V}{\it {{w}_{y}}}}}}$${\textstyle {\frac {\mathbf {q} }{\sqrt {\pi }}}}$${\textstyle {\frac {\mathbf {q} (x)}{\sqrt {\pi (x)}}}}$${\textstyle N_{\pi ,\mathbf {q} }=||{\frac {\mathbf {q} }{\sqrt {\pi }}}||_{2}}$

およびとします。が確率行列、が であるとします。すると、次のようになります。 ${\displaystyle D={\text{diag}}(1/{\it {{w}_{i})}}}$${\displaystyle M=({\it {{w}_{ij})}}}$${\textstyle P(r)=PE_{r}}$${\textstyle P}$${\textstyle E_{r}={\text{diag}}(e^{r\mathbf {1} _{A}})}$${\textstyle r\geq 0}$

${\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}}}}$

ここで、と は対称なので、実固有値を持ちます。したがって、との固有値は等しいので、 の固有値は実数です。と をそれぞれの 1 番目と 2 番目に大きい固有値とします。 ${\displaystyle S:={\sqrt {D}}M{\sqrt {D}}{\text{ and }}S(r):={\sqrt {DE_{r}}}M{\sqrt {DE_{r}}}}$${\displaystyle S}$${\displaystyle S(r)}$${\displaystyle S(r)}$${\displaystyle P(r)}$${\textstyle P(r)}$${\textstyle \lambda (r)}$${\textstyle \lambda _{2}(r)}$${\textstyle P(r)}$

表記の便宜上、、、をすべて1 のベクトルと します。${\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)}$${\displaystyle \mathbf {1} }$

補題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}}$

証拠：

マルコフの不等式により、

${\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}}}$

ここで、確率分布に従って選択されたの期待値です。これは、すべての可能な軌道を合計することで解釈できるため、次のようになります。 ${\displaystyle E_{\mathbf {q} }}$${\displaystyle x_{0}}$${\displaystyle \mathbf {q} }$${\displaystyle x_{0},x_{1},...,x_{k}}$

${\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} }$

2 つの結果を組み合わせると補題が証明されます。

補題2

のために、 ${\displaystyle 0\leq r\leq 1}$

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

証拠：

との固有値は等しい ので、${\displaystyle P(r)}$${\displaystyle S(r)}$

${\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}}}$

補題3

が実数で、 ${\displaystyle r}$${\displaystyle 0\leq e^{r}-1\leq \epsilon /4}$

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

証明の要約:

テイラーは、次の 点について詳しく説明しました。${\textstyle \log \lambda (y)}$${\textstyle r=z}$

${\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}$

ここで、 はにおけるの1次導関数と2次導関数です。 であることを示します。次に、行列操作によって (i) を証明し、次に(i) と複素解析からのコーシー推定値を使用して (ii) を証明します。 ${\displaystyle m_{x}{\text{ and }}V_{x}}$${\displaystyle \log \lambda (r)}$${\displaystyle r=x}$${\displaystyle m_{0}=\lim _{k\to \infty }t_{k}=\pi (A).}$${\textstyle \epsilon _{r}\geq 3\epsilon /4}$${\displaystyle V_{r}\leq 10/\epsilon }$

結果を総合すると、

${\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}}}$

行ごとの証明はギルマン（1998）[1]に記載されている。

定理の証明

補題2と補題3を組み合わせると、

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

不等式の右辺の指数を2次式として解釈し、式を最小化すると、次の式が成り立つ。 ${\displaystyle r}$

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

同様の境界

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

が成立するため、設定により目的の結果が得られます。 ${\displaystyle C=2(1+\gamma \epsilon /10)N_{\pi ,\mathbf {q} }}$

この定理は、デランダム化の研究におけるランダム性の削減に役立ちます。 エクスパンダー ウォークからのサンプリングは、ランダム性効率の高いサンプラーの例です。から独立したサンプルをサンプリングする際に使用されるビット数はであるのに対し、定数次数のエクスパンダーの無限族からサンプリングする場合は のコストのみであることに注意してください。 このような族は存在し、効率的に構築できます (例: Lubotzky -Phillips- Sarnakのラマヌジャン グラフ)。 ${\displaystyle k}$${\displaystyle f}$${\displaystyle k\log n}$${\displaystyle \log n+O(k)}$