緩和の順番を工夫してBellman-Ford法は改善できる

久々にブログのタイトル通りにアルゴリズム(Bellman-Ford法)に関する記事を書きます. それなりに丁寧に書いたつもりなので, Bellman-Ford法を知らない人でも楽しめると思います. プログラムの実行時間はアルゴリズムに加えて実装や実行環境に依存するため, アルゴリズムの計算量では原則として定数倍を無視して議論するわけですが, この記事で紹介する手法はそのような実行環境に依存せず, 本質的に演算回数を定数倍減らしているので競プロ的な(ナイーブな手法を改善していくという)面白さがあると思います.

概要. Bellman-Ford法は$O(mn)$時間で単一始点最短経路問題を解きます. このアルゴリズムは「各辺に対して緩和と呼ばれる操作を行う」ことを$n-1$回繰り返すというアルゴリズムです. 実は緩和を行う辺の順番を工夫することによって反復回数を$n-1$から$n/2$に改善することが可能です [Yen, 1970]. 本稿ではこの単純かつ素晴らしいアイデアを紹介します.

1. Bellman-Ford法とその正当性の証明

フォーマルに書くとBellman-Ford法は以下で定まるアルゴリズムです. まず距離を格納するリスト$\mathrm{dist}[u]$を,

\begin{align*}
\mathrm{dist}[u] = \begin{cases}
0 & \text{if $s=u$},\\
\infty & \text{otherwise}.
\end{cases}
\end{align*}
で初期化し, その後, 「各辺$e\in E$に対して $\mathrm{relax}(e)$ を行う」を$n-1$回繰り返します. ここで$\mathrm{relax}(e)$とは, 有向辺$e=(u,v)$に対し, その重みを$w_e$とすると,
\[
\mathrm{dist}[v] \leftarrow \min\{\mathrm{dist}[v], \mathrm{dist}[u]+w_e\}
\]
で更新する操作である.

Bellman-Ford法では見る辺の順番に関しては特に言及されておらず, どのような順番で辺を見たとしても高々$n-1$回の反復で(負閉路がない場合の)単一始点最短経路が正しく解けることが保証されます. その正当性として以下の「よくある」証明が知られています.

「よくある」Bellman-Ford法の証明.

各$i=0,\dots,n-1$に対して, $i$回目の反復が終了した時点での配列$\mathrm{dist}$を$\mathrm{dist}_i$と書くことにします. ただし$\mathrm{dist}_0$は初期化によって得られる$\mathrm{dist}$で, $\mathrm{dist}_{n-1}$はBellman-Ford法の出力です. 次の主張を$i$に関する帰納法で示します: 各$u\in V$に対して$\mathrm{dist}_i[u] = su$-経路のうち辺数が高々$i$であるもののうち最短の長さである. 実際, $i=0$の場合はこの主張は正しいです. また, $i\leq j$まで主張が正しいと仮定すると, $j+1$回目の反復について考えると, 漸化式
\begin{align*}
\mathrm{dist}_{j+1}[u] = \min_{v \in N^-(u) \cup \{u\}}\{ \mathrm{dist}_j[v] + w_{vu} \}
\end{align*}
を得ます (ただし$N^-(u)=\{v\in V\colon (v,u)\in E\}$は頂点$u$に入っていく辺のもう一方の端点からなる集合で, $w_{uu}=0$と定義している). 帰納法の仮定より各$\mathrm{dist}_j[v]$は辺数$j$本以下の中での最短$sv$経路の長さなので, $\mathrm{dist}_{j+1}[u]$は所望のものになっており, 主張が証明されました. さて, 元のグラフに負閉路がない場合は$s$から辿り着ける全ての頂点$u$に対して最短$su$経路は辺数が高々$n-1$なので, アルゴリズムの出力$\mathrm{dist}_{n-1}[u]$は確かに頂点$s$を始点とした最短経路長を格納した配列になっています. (証明終)

上記の帰納法に基づく証明により, Bellman-Ford法は始点$s$から近い順に最短経路長を決めていることがわかります. イメージとしては, $s$を根とした最短経路木(最短経路に属する辺からなる木. 最短経路が複数あるときは任意に一つだけ選んでその辺を木に追加していって構成できる) に対して, 根から順番に(幅優先探索の要領で)最短経路長が決定していくことがわかります. 特に, 各反復では最短経路木に含まれる辺のうち, 少なくとも1本が最短経路として同定されていきます. 木の辺数は$n-1$であることからもBellman-Ford法の反復回数が高々$n-1$であることが納得できると思います.

2. Yen(1970)の方法

Bellman-Ford法の解析では 「各反復では最短経路木に含まれる辺のうち, 少なくとも1本が最短経路として同定されていく」ことを示したわけですが, それでは「各反復では最短経路木に含まれる辺のうち, 少なくとも2本が最短経路として同定されていく」ならば, 反復回数は高々$\lceil n/2\rceil$となります. Yen(1970)による定数倍改善はこの観察に基づきます. Yen(1970)は, 以下のアルゴリズムによって定まる反復に基づくBellman-Ford法の反復回数は高々$\lceil n/2 \rceil$回であることを主張します:

1. 頂点に適当に番号づけて, $V=\{v_1,\dots,v_n\}$, 始点を$s=v_1$とする. 各辺$e=(v_i,v_j)$に対し, $i<j$ならば$e$を上昇辺, $i>j$ならば$e$を下降辺と呼ぶ.

2. 頂点を$v_1,\dots,v_n$の順番に見ていき, 各$v_i$に対して$v_i$を始点とする全ての上昇辺に対して緩和を実行する.

3. 頂点を$v_n,\dots,v_1$の順番に見ていき, 各$v_i$に対して$v_i$を始点とする全ての下降辺に対して緩和を実行する.

以下にこのアルゴリズムの正当性の証明を載せます.

Yen(1970)の手法の正当性の証明

頂点$u\in V\setminus \{s\}$を固定し, $su$-最短経路を任意に一つ選び, その経路を頂点列とみなし$P=(w_0,w_1,\dots,w_\ell)$とします (ただし$s=w_0,u=w_\ell$). このパス$P$は上昇辺からなる「増加部分」と下降辺からなる「減少部分」の交互列に分解できます. 例えば$P$が

$v_1 \to v_3 \to v_5 \to v_4 \to v_2 \to v_7 \to v_6$

という頂点列の場合, 

• $v_1 \to v_3 \to v_5$
• $v_5 \to v_4 \to v_2$
• $v_2 \to v_7$
• $v_7 \to v_6$
  

のように, 番号に関する極大な増加列と極大な減少列が交互に現れるように分解できます (始点を$s=v_1$にしているので最初は必ず増加列です). この分解を$P=(U_1,D_1,U_2,D_2)$と表すことにします. ここで$U_1=(v_1,v_3,v_5), U_2 = (v_2,v_7)$は増加列, $D_1=(v_5,v_4,v_2), D_2 = (v_7,v_6)$は減少列です. 一般に増加部分を$U_1,\dots,U_p$, 減少部分を$D_1,\dots,D_q$とし, 連続する上昇列と下降列を繋げて得られる$(U_i,D_i)$という$P$の部分列を山折りと呼ぶことにします. 各山降りは少なくとも2本の辺を含むため, 最短経路$P$が含む山折りの個数は高々$\lceil n/2\rceil$です. Yen(1970)のステップ2では小さい頂点から順番に上昇列を緩和していっているため, $P$の上昇列を順番に同定していきます. 同様にステップ3では$P$の下降列を順番に同定していきます. ステップ2-3を交互に繰り返すため, 一回の反復では一つの山折りに対応する部分列$(U_i,D_i)$の最短経路が順番で同定されていきます. 従って, 山折りの個数, すなわち高々$\lceil n/2\rceil$回の反復で最短経路が求まります. (証明終)

3. その後の進展

[Bannister and Eppstein, 2012]によって, 乱択を用いた反復回数のさらなる定数倍改善$n/3$が得られています (著者のブログ記事). このアルゴリズムも非常に単純なテクニックに基づいたものになっています. 具体的には, Yen(1970)では任意に選ばれた頂点順番に基づいて上昇辺と下降辺が定義されていましたが, これをランダムな順番にすると期待値の意味で反復回数が$n/3$になる, ということを示しています. ここではラフな証明を載せておきます. Yen(1970)の上記の解析により, 任意の最短経路$P$を同定するのに必要な反復回数はそれに含まれる山折りの個数で抑えることができます. 従って, 頂点番号がランダムに振られたときの$P$に含まれる山折りの個数の期待値について考察します. 最短経路の頂点列を$(v_0,\dots,v_\ell)$とし, 各$v_i$はランダムに振られた番号を表すとすると, 山折りの個数の期待値はおおよそ$\ell \cdot \sum_{i=1}^n (1/n) \cdot (i/n)^2 \approx \ell \cdot \int_0^1 x^2 \mathrm{d}x \leq n/3$となります (この式における$(1/n)\cdot (i/n)^2$というのは, パス中の頂点を一つ固定したときにその頂点の番号が$i$になり, かつ両隣の頂点の番号がどちらも$i$以下となる確率を意味します). ざっと論文を目を通したくらいなので詳しいことはわかりませんが, おそらく山折りの個数の集中性を示して(集中不等式の文脈ですでに知られている結果がほぼブラックボックスに使えるっぽい), 終着頂点に関するunion boundをとることによって証明がなされています.

なお, 執筆時(2023年12月時点)では負辺ありの単一始点最短経路問題に対するアルゴリズムのオーダーの改善も知られており, 特にFOCSのbest paperをとったブレイクスルーの結果[Bernstein, Nanongkai, Wulff-Nilsen, 2022]によって, 負辺を含むグラフの単一始点最短経路問題が$O(m\log^8(n)\log W)$時間で解けることが示されました. ここで$W>0$は, $w_e\geq -x$を満たす最小の$x$に対して$W=\max\{2,x\}$で定義される値です. ($2$とのmaxをとっているのはlogをとったときに$0$にならないようにするため.) さらに翌年, [Bringman, Cassis, Fischer, 2023]によって$O(m\log^2(n)\log(nW)\log\log n)$時間アルゴリズムが発表されました.

少し余談になりますが, 同じ会議(FOCS2023)では最短経路に関する別の論文[Duan, Mao, Shu, Yin, FOCS23]もあって, この論文ではcomparison-addition modelと呼ばれるモデルにおいて負辺なしの最短経路問題をダイクストラ法より高速に$O(m\cdot \sqrt{\log n\cdot \log\log n})$時間で解く乱択アルゴリズムを提案しています. comparison-addition modelとは, Bellman-Ford法の緩和操作のように, 数値の加算と比較のみが定数時間で行えるような環境を考えるモデルです. 彼らのアルゴリズムのアイデアは根幹の部分ではダイクストラ法と似たようなことをやっています. 通常のダイクストラ法では全ての頂点をヒープに入れて近い順に頂点を取り出してその周りの辺を緩和するというものでしたが, Duanらのアルゴリズムではパラメータ$k=\sqrt{\log n / \log\log n}$に対して, $n/k$個の頂点をランダムに選び, それらをまずFibnacci heapに入れ, 順番に頂点$u$を取り出して, $u$に"近い"頂点を緩和していくようなことをしています (arXiv版のSection 3参照).

4. 感想

講義のために最小費用流や最短経路問題の色々なアルゴリズムを勉強してみたのですが, マトロイドや離散凸といった一般的な枠組みを追求していく面白さとは違った面白さがあり, シンプルで賢いアルゴリズムは勉強していてとても楽しいですね.

5. 参考文献

• "An algorithm for Finding Shortest Routes from all Source Nodes to a Given Destination in General Network", Jin Y. Yen, Quarterly of Applied Mathematics, 27(4), pp.526--530, 1970.
• "Randomized Speedup of the Bellman–Ford Algorithm", Michael J. Bannister and David Eppstein, Proceedings of ANALCO, 2012.
• "Negative-Weight Single-Source Shortest Paths in Near-linear Time", Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen, Proceedings of FOCS, 2022.
• "Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!", Karl Bringmann, Alejandro Cassis, Nick Fischer, Proceedings of FOCS, 2023.

KL divergenceを使ったchernoff boundの証明

概要. Chernoff boundとは独立な確率変数の和の集中性を意味する不等式であり, moment generating functionを抑える方法などによって証明される. ここでは情報理論の道具(KL divergence)を使ってChernoff boundを証明する方法を知ったのでまとめました.

所感ですが, KL divergenceについては自分で定義に則って色々と手計算しまくってchain ruleなどが成り立つことを確認していけば, 慣れてくるものだと思います.

Preliminary

二つの確率変数$X,Y$に対し, それらのKL divergence $D(X||Y)$を
\begin{align*}
D(X||Y) = \sum_a \Pr[X=a]\log\frac{\Pr[X=a]}{\Pr[Y=a]}
\end{align*}
で定義します. ここで総和は$\Pr[X=a]>0$を満たす全ての$a$について動きます. このような$a$の集合を$X$の台(support)と呼び, $\mathsf{supp}(X)$と書きます. また, 確率変数と分布をしばし同一視した記述をします. すなわち, 二つの分布$\mu,\nu$に対してそのKL divergence $D(\mu||\nu)$も考えます.

また, 二つのベルヌーイ試行$\mathrm{Ber}(p),\mathrm{Ber}(q)$に対し, そのKL divergenceを$\delta(p||q)$とします. すなわち
\begin{align*}
\delta(p||q) = D(\mathrm{Ber}(p)||\mathrm{Ber}(q)) = p\log\frac{p}{q} + (1-p)\log\frac{1-p}{1-q}.
\end{align*}

次に, 条件つきKL divergenceを定義します.

定義 (条件つきKL divergence).
二つの確率変数の組$(X_1,X_2),(Y_1,Y_2)$に対し, 条件つきKL divergence $D(Y_1|Y_2 || X_1|X_2)$を以下で定める:
\begin{align*}
D(Y_1|Y_2 || X_1|X_2) &= \mathbb{E}_{y\sim Y_2}\left[ D(Y_1|_{Y_2=y} \,||\, X_1|_{X_2=y})\right] \\
&= \sum_{y_2\in\mathsf{supp}(Y_2)}\Pr[Y_2=y_2]\cdot \sum_{y_1\in\mathsf{supp}(Y_1)}\Pr[Y_1=y_1|Y_2=y_2]\log\frac{\Pr[Y_1=y_1|Y_2=y_2]}{\Pr[X_1=y_1|X_2=y_2]}
\end{align*}

KL divergenceに関する以下の基本的な事実を使います. これらは計算で確認できます:

1. 凸性: $D(\cdot||\cdot)$を分布の組$\to$実数値の関数とみなし, 分布をベクトルとみなしたとき, 凸性を持つ.

2. Chain rule: $D((Y_1,Y_2)||(X_1,X_2)) = D(Y_1|Y_2\,||\,X_1|X_2) + D(Y_2||X_2)$.

3. $X_1,X_2$が独立ならば, $D(Y_1|Y_2\,||\,X_1|X_2)\geq D(Y_1||X_1)$.

性質3の証明:
$D(\cdot||\cdot)$の凸性より,
\begin{align*}
D(Y_1|Y_2\,||\,X_1|X_2) &= \mathbb{E}_{y_2\sim Y_2}\left[ D\left(Y_1|_{Y_2=y}\,||\,X_1|_{X_2=y}\right) \right] \\
&\geq D\left(Y_1|_{Y_2}\,||\,X_2|_{Y_2}\right) & & \text{convexity and Jensen} \\
&= D(Y_1||X_2) & & \text{$X_1,X_2$ are independent}.
\end{align*}

定理 (Chernoff bound).
$X_1,\dots,X_n$を$\{0,1\}$値をとる独立な確率変数とし, $\mu=\frac{1}{n}\sum_{i=1}^n\mathbb{E}[X_i]$とする. このとき, 任意の$t>0$に対して
\begin{align*}
& \Pr\left[\frac{1}{n}\sum_{i=1}^n X_i \leq \mu - t\right] \leq \exp\left(-n\delta(\mu-t||\mu)\right), \\
& \Pr\left[\frac{1}{n}\sum_{i=1}^n X_i \geq \mu + t\right] \leq \exp\left(-n\delta(\mu+t||\mu)\right).
\end{align*}

証明

まず, 以下の事実を使います:
$X$を確率変数, $E$を$X$の事象とする. $Y=X|_E$を, $E$の発生で条件つけたときの$X$とする (つまり, 任意の$a\in E$に対して$\Pr[Y=a]=\Pr[X=a|E]$). このとき
\[
\log\frac{1}{\Pr[E]} = D(Y||X).
\]
これは簡単な計算で確認できます. 実際,
\begin{align*}
D(Y||X) &= \sum_{a\in E}\Pr[X=a|E]\log\frac{\Pr[X=a|E]}{\Pr[X=a]} \\
&= \sum_{a\in E}\Pr[X=a|E]\log\frac{\Pr[E|X=a]}{\Pr[E]} \\
&= \log\frac{1}{\Pr[E]}\sum_{a\in E}\Pr[X=a|E] & & \Pr[X=a|E]=1\text{ for }a\in E \\
&= \log\frac{1}{\Pr[E]}.
\end{align*}

では, Chernoff boundの証明に戻ります. 確率変数$X=(X_1,\dots,X_n)$に対して事象$E$を$E=\left\{\frac{1}{n}\sum_{i=1}^n X_i \geq \mu+t\right\}$とし, $Y=X|_E$とします. $X',Y'$を, 一様ランダムに選ばれた$i\sim[n]$に対し$X'=X_i$, $Y'=Y_i$と定義される確率変数とします. すると
\begin{align*}
\log\frac{1}{\Pr[E]} &= D(Y||X) \\
&= \sum_{i=1}^n D(Y^{\leq i}|Y^{\leq i-1}||X^{\leq i}|X^{\leq i-1}) & & \text{chain rule} \\
&= \sum_{i=1}^n D(Y_i|Y^{\leq i-1}||X_i|X^{\leq i-1}) \\
&\geq \sum_{i=1}^n D(Y_i||X_i) & & \text{$X_i$s are indepenent} \\
&= n\mathbb{E}_{i\sim[n]}\left[ D(Y_i||X_i)\right] \\
&\geq n D(Y'||X') & & \text{convexity of KL divergence and Jensen's inequality}.
\end{align*}

ここで, $D(Y'||X')$を計算してみます. どちらも$\{0,1\}$値確率変数であり, $X=(X_1,\dots,X_n)$で条件つけたときは$\Pr[X'=1]=\frac{1}\sum_{i=1}^n X_i$となるので, $\Pr[X'=1]=\mu$です. 一方で$Y=X|_E$なので, $E$の定義から$\Pr[Y'=1]\geq\mu+t$を得ます. 従って, $D(Y'||X')\geq \delta(\mu+t||\mu)$となり, upper tailを得ます.

lower tailも同様に示すことができます.　(証明終)

注釈1 ($\delta(p||q)$のバウンド).
Pinskerの不等式を用いると, $d_{\mathrm{tv}}(\mathrm{Ber}(p),\mathrm{Ber}(q))=|p-q|\leq \sqrt{\frac{\delta(p||q)}{2}}$を得ます. これをChernoff boundに代入するとHoeffding boundを得ます.

注釈2 ($[0,1]$値への拡張.)
証明では$D(Y'||X')$の下界を得るために$X$が$\{0,1\}$値をとることを利用しましたが, data processing 不等式などを使うと簡単に$[0,1]$値確率変数の集中不等式を得ることができます (詳細は省略).

逆向きのマルコフの不等式

マルコフの不等式とは確率の不等式を扱うときに必ずといっていいほど出てきます。

定理1 (マルコフの不等式).

$X$が非負の値をとる確率変数とする. 任意の$a>0$に対して

\begin{align*}
\Pr[X\geq a] \leq \frac{\mathbf{E}[X]}{a}.
\end{align*}

この不等式はChernoff boundやAzuma-Hoeffdingなど基本的な確率集中不等式の証明やunion boundの証明にも使えます. 実際, $k$個の事象$E_1,\dots,E_k$に対して$X$を$E_1,\dots,E_k$の中で発生した事象の個数を表す確率変数とすると, マルコフの不等式より

\begin{align*}
\Pr\left[\bigcup_{i=1}^k E_i\right] = \Pr[X\geq 1] \leq \mathbf{E}[X]=\sum_{i=1}^k\Pr[E_i]
\end{align*}

を得ます.

マルコフの不等式は$X$の期待値が小さければ$X$が小さくなりやすいというごく当たり前のことを主張する不等式です. では, 逆に期待値が大きければ$X$が大きくなりやすいという方向の不等式はないのでしょうか?

このようなことを示したいときは以下に示す「逆向きの」マルコフの不等式が使えないかを考えるのが最も基本的です：

定理2 (逆向きのマルコフの不等式)

$X$が$[0,1]$値をとる確率変数とし, $\mu=\mathbf{E}[X]$とすると,

\begin{align*}
\Pr[X\geq \mu/2] \geq \mu/2.
\end{align*}

証明.

マルコフの不等式より,

\begin{align*}
\Pr[X\leq 1-a] = \Pr[1-X\geq a] \leq \frac{1-\mu}{a}
\end{align*}

ここで$a=1-\mu/2$を代入すると

\begin{align*}
\Pr[X\leq \mu/2] \leq \frac{1-\mu}{1-\mu/2} = 1-\frac{\mu/2}{1-\mu/2} \leq 1-\mu/2.
\end{align*}

(証明終).

擬似ランダム生成器とNisan-Wigderson生成器

1. 擬似ランダム生成器

平均時計算量では分布のランダムっぽさを, その分布が任意の効率的な敵対者(=アルゴリズム)に対して一様分布と識別できないという性質によって定義する定式化があります. ここでは主に敵対者としてサイズ$s$の回路を考えます. 前回の記事でも紹介しましたが分布の擬似ランダム性を以下で定義します:

定義1 (擬似ランダム性).

$\{0,1\}^\ell$上の分布$D$がサイズ$s$に対して$\epsilon$-擬似ランダムであるとは, 任意のサイズ$s$の回路$C$に対して

\begin{align*}
|\mathbf{E}_{x\sim D}[C(x)]-\mathbf{E}_{x\sim U_n}[C(x)]| \leq \epsilon
\end{align*}

が成り立つことをいう (ここで$U_n$は$\{0,1\}^n$上の一様分布). 

定義2 (擬似ランダム生成器).

関数$G\colon \{0,1\}^n\to\{0,1\}^\ell$は, $\{0,1\}^\ell$上の分布$G(U_n)$がサイズ$s$に対して$\epsilon$-擬似ランダムであるとき, サイズ$s$に対する$\epsilon$-擬似ランダム生成器であるという.

擬似ランダム生成器は短いランダム文字列を受け取って長い擬似ランダム文字列を返す関数です. 例えば$\ell$ビットのランダム文字列$r$を使う乱択アルゴリズム$\mathcal{A}(x;r)$を考えたとき, $r$としてランダム文字列の代わりに$G(U_n)$を用いたアルゴリズム$\mathcal{A}(x;G(U_n))$もまた元の乱択アルゴリズム$\mathcal{A}(x;r)$とほぼ同じ振る舞いをすることが示せます (そうでないとすると, $\mathcal{A}(x;\cdot)$を使って$G(U_n)$と$U_\ell$を識別できるので). 全ての$n$ビットのシードを列挙すれば, $2^n$倍のオーバーヘッドでアルゴリズムを脱乱択することができます. このように考えると, $\ell$が大きいかつ$\epsilon$が小さいほど擬似ランダム生成器は良いということになります.

2. 簡単な例

2.1. 1ビットだけ伸ばす

前回の記事の定理(Yaoのnext-bit predictor)により, 関数$f\colon\{0,1\}^n\to\{0,1\}$がサイズ$s$に対して$(1/2-\epsilon)$困難であるならば, 関数$G\colon x\mapsto (x,f(x))$はサイズ$s-O(1)$に対して$\epsilon$-擬似ランダム生成器になります. この関数$G$は$\ell=n+1$なので, 1ビットだけ伸ばす擬似ランダム生成器です.

定理1.

関数$f\colon\{0,1\}^n\to\{0,1\}$がサイズ$s$に対して$(1/2-\epsilon)$-困難ならば, 関数$G\colon x\mapsto (x,f(x))$はサイズ$s-O(1)$に対して$\epsilon$-擬似ランダム生成器である.

2.2. 2ビットだけ伸ばす

関数$G\colon \{0,1\}^{2n}\to \{0,1\}^{2n+2}$を

\begin{align*}
G(x,y)=(x,f(x),y,f(y))
\end{align*}

としてみます (ここでは入力を前半と後半の$n$ビットずつに区切り, それぞれを$x,y\in\{0,1\}^n$としている). 同様の議論を使うとこれは2ビットだけ伸ばす擬似ランダム生成器になることが示せます.

定理2.

関数$f\colon\{0,1\}^n\to\{0,1\}$がサイズ$s$に対して$(1/2-\epsilon/2)$-困難ならば, 関数$G\colon (x,y)\mapsto (x,f(x),y,f(y))$はサイズ$s-O(1)$に対して$\epsilon$-擬似ランダム生成器である.

証明:

背理法で示す. あるサイズ$s'$の回路$C$が存在して

\begin{align*}
\mathbf{E}_{(x,y)\sim U_{2n}}[C(x,f(x),y,f(y)] - \mathbf{E}_{(z,w)\sim U_{2n+2}}[C(z,w)]>\epsilon
\end{align*}

となるとする (必要があれば出力ビットを反転することで絶対値を外せる). 期待値の線形性およびランダム文字列をそれぞれ$z=(x,b),w=(y,c)$と書き直すと

\begin{align*}
\mathbf{E}_{(x,b,y,c)\sim U_{2n+2}}[C(x,f(x),y,f(y)) - C(x,b,y,c)] > \epsilon
\end{align*}

を得ます. この式の左辺は, 同じ値を足したり引いたりすることで

\begin{align*}
\mathrm{(LHS)} &= \mathbf{E}[C(x,f(x),y,f(y))] - \mathbf{E}[C(x,f(x),y,c)] \\
&\hspace{1em}+ \mathbf{E}[C(x,f(x),y,c)] - \mathbf{E}[C(x,b,y,c)] > \epsilon
\end{align*}

を得ます. よって, 前半の差と後半の差の少なくとも一方は$>\epsilon/2$です. すなわち

\begin{align*}
&\mathbf{E}[C(x,f(x),y,f(y))] - \mathbf{E}[C(x,f(x),y,c)] > \epsilon/2 \\
&\hspace{10em}\text{ or }\\
&\mathbf{E}[C(x,f(x),y,c)] - \mathbf{E}[C(x,b,y,c)] > \epsilon/2
\end{align*}

です. もし前者が成り立つならば, ある$x^*\in\{0,1\}^n$が存在して回路$C'(y,c):=C(x^*,f(x^*),y,c)$を考えると, これは二つの分布$(y,f(y))$と$U_{n+1}$をアドバンテージ$>\epsilon/2$で識別する. これは定理1に反する. 後者が成り立つ場合でも同様に, 回路$C$においてうまく$(y,c)\in\{0,1\}^{n+1}$を選んで固定して得られる回路$C'$は定理1に反する.

(証明終)

コメント1. 上記の証明において, 回路の入力を部分的にうまく選んで固定して新しい回路を得ていました. 例えば前半のケースでは$x$を固定していましたが, このときの$x$の選び方は$(y,c)$の選び方には依存しないことに注意してください. また, $x$を固定すると$f(x)\in\{0,1\}$も自動的に固定されます. このように回路の入力を部分的にうまく選んだ値に固定することをハードワイヤ (hardwire)するといいます.

コメント2(適当に読み飛ばしてください). 上記の証明においては同じ値を足したり引いたりしてうまく式変形した後に, 二つのケースに分けてそれぞれについて$(U_n,f(U_n))$と$U_{n+1}$を識別する回路$C'$を構成しました. このときの式変形では, 

\begin{align*}
\mathbf{E}[C(D)]-\mathbf{E}[C(D')]>\epsilon
\end{align*}

の形をした左辺を二つの差分の和として表現していて, それぞれの差分では構成要素が一つしか異ならないテレスコープサムのような形に変形しています. このように, 二つの$D$と$D'$を補間するような分布列$D_0=D,D_1,\dots,D_k=D'$を用意して

\begin{align*}\mathbf{E}[C(D)]-\mathbf{E}[C(D')]=\sum_{i=1}^k \mathbf{E}[C(D_{i-1})-C(D_i)] >\epsilon \end{align*}

と式変形して議論することをハイブリッド議論 (hybrid argument)と呼び, 分布列$D_0,\dots,D_k$をハイブリッド分布と呼びます (平均時計算量の脱乱の分野では頻出です).

コメント3. 上記の証明ではあくまでも回路の存在性のみをいっていて, その回路が効率的に構築できるかどうか (つまり元となる回路$C$を入力として受け取って所望の回路$C'$を出力するアルゴリズムの存在性) については何も言っていないことに注意してください. 例えば$x=x^*$にハードワイヤする際に$f(x^*)$も同時にハードワイヤしましたが, このとき$f(x^*)$を計算する手間は考えていません ($x^*$を固定したら一意に定まるから).

2.3. 2ビット伸ばす (続)

2.2節では$2n$ビットのランダム文字列を受け取って$2n+2$ビットの擬似ランダム文字列を出力する擬似ランダム生成器を紹介しました. ここでは, 次の章のために別の擬似ランダム生成機$G\colon \{0,1\}^{2n-d} \to \{0,1\}^{2n-d+2}$を紹介します ($d$はパラメータ).

まず, $2n-d$ビットの入力$z\in\{0,1\}^{2n-d}$の前半$n$ビットを$x$, 後半$n$ビットを$y$とします. 関数$G(z)$は$(z,f(x),f(y))$を出力します.

$d=0$のときは2.2節と同じになりますが, ここでは$x$と$y$の取り方にオーバーラップを許している点が異なります. このように構成された$G''$も$d$が小さければ擬似ランダム生成器になることが示せます:

定理3.

関数$f\colon\{0,1\}^n\to\{0,1\}$がサイズ$s$に対して$(1/2-\epsilon/2)$-困難であるならば,上記で定義された関数$G$はサイズ$s-2^{O(d)}$に対して$\epsilon$-擬似ランダム生成器である.

証明する前にまず, そもそも2.2節の議論で示せないか考えてみましょう. 2.2節の議論では, 二つの分布$(x,f(x),y,f(y))$と$(x,b,y,c)\sim U_{2n+2}$が識別できるならばうまく$(y,c)\in\{0,1\}^{n+1}$をハードワイヤすることで$(x,f(x))$と$U_{n+1}$を識別する回路が作れて定理1に反するという方針でした. つまり, 入力を部分的に固定することで$(x,f(x))$と$U_{n+1}$を識別する回路が作れてしまうというのが2.2節の議論のミソでした (下図).

2.2節の議論で構成した回路$C'$ (二つ目のケースを図示).

今回の$G''$にこの議論を適用してみましょう. つまり, $(z,f(x),f(y))$と$(z,b,c)$を識別する回路$C$が作れたとします. 本来であれば$(y,c)$をうまくハードワイヤして得られた回路$C'$は$(x,f(x))$と$U_{n+1}$を識別することを言いたいのですが, $x$と$y$にはサイズ$d$のオーバーラップがあるので, $y$に該当する$n$ビットを固定してしまうと$x$の最後の$d$ビットも巻き込まれてハードワイヤされてしまいます. 従って, $(y,c)$をハードワイヤして得られる回路は$C'\colon \{0,1\}^{n-d+1}\to\{0,1\}$となっており, そもそも入力として$(x,f(x))$を受付けてくれません.

単純なアイデアですが, この問題点は$x$とオーバーラップしていない部分をハードワイヤすることによって解決できます. 

命題2の証明.

ビット列$w\in\{0,1\}^\ell$および$1\leq a\leq b\leq \ell$に対して$w[a:b]$を$w$の第$a$番目から$b$番目までの部分文字列とする.

$G(U_{2n-d})$と$U_{2n-d+2}$をアドバンテージ$>\epsilon$で識別する回路を$C$とする. 与えられた$z\in\{0,1\}^{2n-d}$に対し, 前の$n$ビットを$x=z[1:n]$, 後ろの$n$ビットを$y=z[n-d,2n-d]$とする. 定義より, $b,c\sim U_1$とすると,

\begin{align*}
\mathbf{E}[C(z,f(x),f(y)) - C(z,b,c) > \epsilon.
\end{align*}

この式の左辺は

\begin{align*}
(\mathrm{LHS}) &= \mathbf{E}[C(z,f(x),f(y))] - \mathbf{E}[C(z,f(x),c)] \\
&\hspace{1em}+\mathbf{E}[C(z,f(x),c)]-\mathbf{E}[C(z,b.c)] > \epsilon
\end{align*}

より,

\begin{align*} &\mathbf{E}[C(z,f(x),f(y))] - \mathbf{E}[C(z,f(x),c)] > \epsilon/2 \\&\hspace{10em}\text{ or }\\&\mathbf{E}[C(z,f(x),c)]-\mathbf{E}[C(z,b,c)] > \epsilon/2\end{align*}

を得る. 

(i). 前者が成り立つ場合, $x$の前から$n-d$ビット$x[1:n-d]$をある$w^*\in\{0,1\}^{n-d}$にハードワイヤする. このとき, $x$は$w^*$と$y[1:d]$を結合した文字列となるので, $f(x)=f(w^*,y[1:d])$の形で書くことができる. $y$が変数ならばこの値は$d$個の変数にしか依存しない値なので, サイズ$2^{O(d)}$の回路で計算できる (つまり, 固定した$w^*$に対して関数$(w^*,y[1:d])\mapsto f(w^*,y[1:d])$を計算するサイズ$2^{O(d)}$が存在する). この回路を$C$の$f(x)$を受け取る部分にくっつけます(下図).

このようにして得られた回路を$D(y,c)$とすると, $D$のサイズは$s'+2^{O(d)}$となり, $(y,f(y))$と$(y,U_1)$をアドバンテージ$>\epsilon/2$で識別する.

(ii). 後者が成り立つ場合も同様にして$(x,f(x))$と$(x,U_1)$をアドバンテージ$>\epsilon/2$で識別する回路を構成できる. こちらは単純に$y$の後ろ$n-d$ビットと$c$をハードワイヤすればよい.

ケース(i),(ii)どちらにしても所望の回路が構成できたので, 主張を得る.

(証明終)

3. Nisan-Wigderson生成器

ここまで定義した擬似ランダム生成機は2ビット程度しか伸ばさない, 少々心許ないものでしたが, 実は次数的に伸ばせることが知られています. NisanとWigdersonによるとても格好良いタイトルの論文「Hardness vs Randomness」は, 非常に困難な関数$f$を使って擬似ランダム生成器を構成する手法を提案しています. この手法によって構成された擬似ランダム生成器はNisan-Wigderson生成器と呼ばれ, 非常に強力なツールとして知られています.

2.2節と2.3節で紹介した擬似ランダム生成器$G$はどれも入力$z$から$n$ビットの文字列$x,y$を二つ取り出し, $(z,f(x),f(y))$を出力するというものでした. また, $x$と$y$のオーバーラップの長さ$d$が小さくてもサイズ$2^{O(d)}$の回路をくっつければ$G$の擬似ランダム性を示せることを2.3節で示しました. ここで, そもそも取り出す文字列は二つでなく三つ以上でも同様の証明が機能するという点に着目します. これをもとに設計されたのがNisan-Wigderson生成器です.

3.1. Combinatorial Design

定義4.

台集合$[m]$上の部分集合族$\mathcal{S}=\{S_1,\dots,S_\ell\}$が以下を満たすとき, $(m,n,d)$-デザインと呼ぶ:

(1). 各$S_i$は$|S_i|=n$.

(2). 全ての$1\leq i<j\leq \ell$に対し, $|S_i\cap S_j|\leq d$.

$(m,n,d)$-デザインは2.3節で考えた部分文字列の取り出し方を一般化したものになっています.

定理5 (Nisan-Wigderson生成器).

$\mathcal{S}=\{S_1,\dots,S_\ell\}$を$(m,n,d)$-デザインとし, $f\colon\{0,1\}^n\to\{0,1\}$を$(1/2-\epsilon/\ell)$-困難であるとする. 関数$G^f_{\mathcal{S}}\colon \{0,1\}^m\to\{0,1\}^\ell$を

\begin{align*}
G^f_\mathcal{S}(x) = (f(x|_{S_1}), \dots, f(x|_{S_\ell}))
\end{align*}

で定義する ($x|_S\in\{0,1\}^{|S|}$は$x$の$S$への制限. このとき, $G$はサイズ$s-\ell 2^{O(d)}$に対し$\epsilon$-擬似ランダム生成器である.

証明は定理3と同様なので, 概略だけ記します.

証明概略. $G^f_{\mathcal{S}}(U_m)$と$U_\ell$をアドバンテージ$>\epsilon$で識別する回路を$C$とします. 簡単のため, $x_i=x|_{S_i}$と表します. $b_1,\dots,b_\ell\sim U_1$とします. 定義より

\begin{align*}
\mathbf{E}[C(f(x_1),\dots,f(x_\ell))] - \mathbf{E}[C(b_1,\dots,b_\ell)]>\epsilon.
\end{align*}

ハイブリッド議論を見据えて式変形しましょう. $D_i=(f(x_1),\dots,f(x_i),b_{i+1},\dots,U_\ell)$とすると, $D_0=(b_1,\dots,b_\ell)$かつ$D_\ell=(f(x_1),\dots,f(x_\ell))$なので

\begin{align*}(\mathrm{LHS})&= \mathbf{E}[C(D_\ell)]-\mathbf{E}[C(D_0)] \\&=\sum_{i=1}^\ell\mathbf{E}[C(D_i)-C(D_{i-1})] > \epsilon\end{align*}

より, ある$i\in[\ell]$に対して

\begin{align*}
&\mathbf{E}[C(f(x_1),\dots,f(x_{i-1}),f(x_i),b_{i+1},\dots,b_\ell)] - \\
&\mathbf{E}[C(f(x_1),\dots,f(x_{i-1}),b_i,b_{i+1},\dots,b_\ell)] > \epsilon/\ell
\end{align*}

です. $C$の引数は$i$番目だけ異なっていることに注意してください. 変数名を$x_i=y$と変えて, $y$に対応する部分以外全てのビットをハードワイヤします (つまり$x|_{[m]\setminus S_i}=w^*$と固定する). さらに, $b_{i+1},\dots,b_\ell$もハードワイヤします. すると, $f(x_1),\dots,f(x_{i-1})$はそれぞれ, $y\in\{0,1\}^n$のうち高々$d$ビットにしか依存しません ($\mathcal{S}$が$(m,n,d)$-デザインだから). よってこれらはサイズ$2^{O(d)}$の回路で計算できるので, これらを$C$にくっつけることによって$(y,f(y))$と$(y,U_1)$をアドバンテージ$>\epsilon/\ell$で識別する回路を得ました.

(証明終).

3.2. デザインの存在性

以前の記事で証明しましたが, パラメータ$n,d\in\mathbb{N}$に対し, $\ell=n^{d+1}$個の集合からなる$(n^2,n,d)$-デザイン$\mathcal{S}=\{S_1,\dots,S_\ell\}$が存在します. このデザインを使うとNisan-Wigderson生成器は

\begin{align*}
G\colon \{0,1\}^{n^2}\to \{0,1\}^{n^{d+1}}
\end{align*}

となります.

4. Hardness vs Randomness

ここまでの定理では

$\exists $平均的に非常に困難な関数 $\Rightarrow$ $\exists$擬似ランダム生成器

という形の結果を証明しました. このように, 関数の困難性を利用して擬似ランダムネスを生み出す枠組みはHardness vs Randomnessと呼ばれ, 平均時計算量の理論で近年も活発に研究されています.

関数の平均時困難性と分布の識別不可能性

1. 関数の平均時困難性

平均時計算量の理論ではランダムな入力に対する問題の計算複雑性を議論します. 具体的には, 関数$f\colon\{0,1\}^k\to\{0,1\}$が任意のサイズ$s$の回路$C$に対して

\begin{align*}
\Pr_{x\sim\{0,1\}^k}[C(x)=f(x)]\leq 1-\delta
\end{align*}

を満たすとき, $f$はサイズ$s$に対して$\delta$-困難であるといいます. つまり効率的に$f(x)$を計算できる入力$x$の量によってその問題$f$の複雑性を評価します (回路の代わりに効率的なアルゴリズムを考えても似たような定義を与えることができます). 回路$C$が正解する入力の割合を成功確率と呼ぶことにします. すなわち$C$の$f$に対する成功確率は$$\Pr_{x\sim\{0,1\}^k}[C(x)=f(x)]$$

で与えられます.

$f$がBoolean関数ならば, 「常に$0$を出力する回路」もしくは「常に$1$を出力する回路」の少なくとも一方は成功確率$1/2$以上になります. 従って関数$f$は$\delta$-困難であるといった場合は基本的には$\delta\leq 1/2$を仮定し, $\delta$が$1/2$に近いほど$f$の困難性は強いということになります. 

コメント.

非常に細かいことですが, 入力長ごとに「常に0を出力すべきか」「常に1を出力すべきか」が変わりうるので, 決定的アルゴリズムを用いて困難性を定義した場合は$\delta\leq 1/2$は一般には言えません. このように入力長ごとに違うアルゴリズムを採用する場合は非一様モデル(=回路)で議論した方が良いと思います (一概には言えませんが).

2. 分布の識別不可能性

2.1. 統計的な識別不可能性

一方で, 平均時計算量の理論では分布のランダムっぽさ(擬似ランダム性)が計算量の概念を使って定義されています.

 確率論や機械学習などの文脈では分布の近さを統計距離(total variation distance)で評価し, 一様分布に近い分布を「ランダムっぽい」分布とみなすことができます. この文脈でいうと, 「分布$D$はランダムっぽい」という主張は(統計距離の定義に基づいて考えると)「分布$D$と一様分布を識別できる事象は存在しない」ことを意味します. もう少しフォーマルに述べます. 分布$D$を有限集合$\Omega$上の分布だと仮定します. ある関数$E\colon\Omega\to\{0,1\}$が存在して

\begin{align*}
|\mathbf{E}_{x\sim D}[E(x)] - \mathbf{E}_{x\sim \Omega}[E(x)]| > \epsilon
\end{align*}

を満たすとき, 分布$D$は一様分布から(統計距離の意味で)$\epsilon$だけ離れているといいます (ここで$x\sim\Omega$は$x$が$\Omega$上の一様分布に従って選ばれることを意味する). 従って, 関数$E$を使って$D$を一様分布から$\epsilon$のアドバンテージで識別することができます. このことを統計的に識別できるといいます. 逆に, そのような$E$が存在しないとき, 分布$D$はいかなる事象でも一様分布と区別がつきません.

2.2. 識別不可能性の恩恵: 暗号

あるメッセージを暗号化して送信するとしましょう. 暗号化された文は敵対者に対してその内容がわからないようになっている必要があります. 文の構造に何かしらの特徴があるとそこから何かしらの情報が引き出されてしまうため, 暗号文は何も特徴を持たないものであることが望ましいです. もしも暗号文は敵対者にとって「ランダム文字列」と識別できないという性質を持つならばこの課題はクリアされます (完全にランダムな文字列からは長さ意外の情報を何も抜き出せないいため). 例えば長さ$n$の文字列$x\in\{0,1\}^n$に対して, 長さ$n$の一様ランダムな文字列$r\in\{0,1\}^n$を生成して$x\oplus r$を暗号文としてみましょう ($x\oplus r$は各ビットごとにXORをとって得られる文字列). $r$が一様ランダムなので$x\oplus r$も一様ランダムとなり, もし敵対者が$r$を知らないとするとこの暗号化は条件をクリアしています.

しかし受信者は$n$ビットの文字列$r$をあらかじめ知っている必要があり, そもそも$r$を敵対者に知られずに共有できるならば$x$そのものを共有すれば良いことになるので, この手法は用途が非常に限られてしまいます. 実は, 統計距離を用いた識別不可能性を満たす暗号を構成するにはメッセージと同じ長さのランダムネスが必要となることが知られており, この問題点は解消できません.

2.3. 計算論的な識別不可能性

このような統計距離に基づく識別不可能性の現実味を削ぐ要因の一つには, 任意の識別者(=関数$E$)を考えるという点にあります. 実際には, 敵対者の計算能力は無限ではない(例えば多項式時間アルゴリズム)を想定すれば良いです. 従って分布の識別可能性を

ある効率的に計算できる関数$E\colon\Omega\to\{0,1\}$が存在して

\begin{align*}
|\mathbf{E}_{x\sim D}[E(x)] - \mathbf{E}_{x\sim \Omega}[E(x)]| > \epsilon
\end{align*}

によって定義すれば異なる結果が期待されます. このことを計算論的に識別できるといい, 計算論的に一様分布と区別できない分布を擬似ランダムであるといいます.

もう少しフォーマルに述べるしょう. 空間として$\Omega=\{0,1\}^k$を考え, $\{0,1\}^k$上の一様分布に従って選ばれた確率変数を$U_k$とします. 分布$D$と回路$C\colon\{0,1\}^k\to\{0,1\}$が

\begin{align*}|\mathbf{E}[C(D)-C(U_k)]|>\epsilon\end{align*}

を満たすとき, $C$はアドバンテージ$\epsilon$で$D$と$U_k$を識別するといいます. また, そのような回路であってサイズ$s$であるものが存在しないとき, $D$はサイズ$s$に対して$\epsilon$-擬似ランダムであるといいます.

3. 平均時困難性と識別不可能性の関係

統計的な識別不可能性から計算論的な識別不可能性への転換は, 本質的には敵対者(=識別者$E$)の範囲を限定するということに他なりません. しかしながらこの単純な転換が実に多くの(この記事に書ききれないほど)非自明な定理を生み出します.

実はこの両者の概念はBoolean関数においてはある意味で等価であるという結果が知られており, 今回はYaoのnext-bit predictorと呼ばれる結果を紹介します.

定理 ([Yao, 1982]).

関数$f\colon \{0,1\}^k\to\{0,1\}$がサイズ$s$に対して$(1/2-\epsilon)$-困難であるとする. このとき, $z=U_k$に対して分布$(z,f(z))$はサイズ$s-O(1)$に対して$\epsilon$-擬似ランダムである.

コメント1. 逆方向 ($(z,f(z))$が擬似ランダムならば$f$は$(1/2-\epsilon)$-困難)は簡単に示せます. 実際, $f$を成功確率$1/2+\epsilon$で計算するサイズ$s$の回路を$C$とすると, 「与えられた入力$(z,b)$に対して$b\oplus f(z)$を出力する回路を考えれば$(z,b)=(z,f(z))$か$(z,b)=(z,U_1)$かどうかを$\epsilon$のアドバンテージで識別することができます.

コメント2. 興味深いことに, 関数$G\colon z\mapsto (z,f(z))$を考えると, 定理よりこの関数はランダムな$k$ビットを受け取り, 擬似ランダムな$k+1$ビットを返す関数になっています. このように, 短いランダム文字列を受け取り長い擬似ランダム文字列を返す関数を擬似乱数生成器といいます (フォーマルな定義は本記事では割愛). これは統計的な識別不可能性に基づく枠組みでは不可能です. 実際, $G$は決定的な関数なので$G(z)$のランダムネス(=エントロピー)は高々$k$ビットであり, 統計的な意味ではランダムネスを増やすことはできないからです. 計算論的な識別不可能性を考えるとある意味で「エントロピーを増やす」ことができるのが重要な利点であり, 乱択アルゴリズムの脱乱択化や弱い仮定に基づく安全な暗号プリミティブの構成に応用されています. 再度述べますが, 敵対者を効率的なアルゴリズムに限定したからこそこのようなことが可能になっているのです.

定理の証明.

対偶を示します. $(z,f(z))$と$U_{k+1}$をアドバンテージ$\epsilon$で識別するサイズ$s'$の回路を$C\colon\{0,1\}^{k+1}\to\{0,1\}$とします. 識別するので

\begin{align*}
\mathbf{E}_{z,U_1}[C(z,f(z))-C(z,U_1)] > \epsilon
\end{align*}

です (必要があれば出力ビットを反転することにより絶対値を外すことができます). 特に$U_1$は$z$とは独立な確率変数なので, 確率$1/2$で$U_1=f(z)$になったときは差が$0$になります. 従って上式を書き換えると

\begin{align*}
\mathbf{E}_z[C(z,f(z))] - \mathbf{E}_z[C(z,\overline{f(z)})] > 2\epsilon
\end{align*}

を得ます ($\overline{b}=1\oplus b$はビットの反転).

回路$P(z,r)$を$P(z,r)=C(z,r)\oplus r \oplus 1$とすると, 以下で示すように$\Pr_{z,r\sim U_1}[P(z,r)=f(z)]> 1/2+\epsilon$を得ます. これを得ると$P(z,0)$と$P(z,1)$の少なくとも一方が$f$を成功確率$>1/2+\epsilon$で計算するサイズ$s'+O(1)$の回路になっており, 証明が完了します.

$r\sim U_1$より, 確率$1/2$で$r=f(z)$となります. したがって

\begin{align*}
\Pr_{z,r}[P(z,r)=f(z)] &= \mathbf{E}_{z,r}[P(z,r)\oplus f(z)\oplus 1] \\
&= \mathbf{E}_{z,r}[C(z,r)\oplus r \oplus f(z)] \\
&= \frac{1}{2}\mathbf{E}_z[C(z,f(z))] + \frac{1}{2}\mathbf{E}_z[1-D(z,\overline{f(z)})] \\
&> \frac{1}{2}+\epsilon
\end{align*}

を得ます (3番目の等式では$r=f(z)$と$r=\overline{f(z)}$の場合分けを行っています).

(証明終)

高次元エクスパンダー: マトロイドの局所エクスパンダー性

今回も高次元エクスパンダーに関する記事となります。前回の記事では単体複体の局所エクスパンダー性を定義し、Oppenheimのトリクルダウン定理を紹介しました。今回の記事ではその応用として以下の前回の記事でも紹介した以下の系を証明したいと思います。

系2.

マトロイド$(V,\mathcal{F})$は局所$0$-エクスパンダーである。

軽く定義を復習しましょう。考えるマトロイドを$X=(V,\mathcal{F})$とし、そのランクを$d$とします。したがって$X(d-2)$は要素数$d-2$の独立集合の全体です。独立集合$\sigma\in X(d-2)$を一つ固定し、そのリンク$X_\sigma$の1-スケルトン$G_\sigma$を考えます。このグラフ$G_\sigma=(V\setminus \sigma,E)$は次で与えられます:

$$\{u,v\}\in V \iff \sigma\cup \{u,v\} \in \mathcal{F}.$$

$G_\sigma$上の単純ランダムウォーク(隣人を一様ランダムに選んで遷移するランダムウォーク)の遷移確率行列を$P_\sigma$とし、$\lambda_2(P_\sigma)$をその2番目に大きい固有値とします。

マトロイドの基の交換を繰り返せば任意の二つの基の間を行き来することができます（詳細は例えばこちらのページの定理1を参照）。同様の議論により、マトロイドはトリクルダウン定理の条件(1-スケルトングラフの連結性)を満たし、トリクルダウン定理の系1より、$\mu_{d-2} = \max_{\sigma\in X(d-2)}\lambda_2(P_\sigma)\leq 0$を示せば冒頭の系2が得られます。

マトロイドに対する$G_\sigma$はどのようなグラフなのでしょうか。実は非常に特徴的な構造を持つことがわかります:

補題1.

任意の$\sigma\in X(d-2)$に対して$G_\sigma$の補グラフの全ての連結成分はクリークである。

証明:

$G_\sigma=(W,E)$とします。$\{u,v\},\{v,w\}\not\in E$ならば$\{u,w\}\not\in E$を背理法を使って示します。まず$\{u,w\}\in E$を仮定します。$G_\sigma$の定義より$S_1:=\sigma\cup \{u,w\}\in \mathcal{F}$です。また、$v$は$G_\sigma$の頂点なので$S_2:=\sigma\cup\{v\}\in\mathcal{F}$も成り立ちます。$S_1,S_2$に対して独立集合族の公理を適用すると$S_2\cup \{u\}\in \mathcal{F}$または$S_2\cup \{w\}\in\mathcal{F}$の少なくとも一方が成り立ちます。しかしこれは$\{u,v\},\{v,w\}\not\in E$に矛盾します。

（証明終）

$G_\sigma$の補グラフの各連結成分を$C_1,\dots,C_\ell\subseteq V$とします。$C_1,\dots,C_\ell$は、補グラフにおける孤立点(次数0の頂点)に対応する連結成分も含みます (例えば$C_1=\{v_1\}$にもなりえるということです)。各$C_i$の指示ベクトルを$v_i$として全ての要素が1の行列を$J$とすると、$G_\sigma$の隣接行列$A$は

\begin{align*} A = J - \sum_{i=1}^\ell v_iv_i^\top\end{align*}

と表せます。したがってCauchyのinterlacing定理より$\lambda_2(A)\leq 0$を得ます。

定理 (Cauchyのinterlacing定理).

対称行列$A\in\mathbb{R}^{n\times n}$の固有値を$\alpha_1\geq \dots \geq \alpha_n$とする。ベクトル$v\in\mathbb{R}^n$に対し、行列$A-vv^{\top}$の固有値を$\beta_1\geq \dots \geq \beta_n$とする。このとき

\[ \alpha_1 \geq \beta_1 \geq \dots \geq \alpha_n \geq \beta_n.\]

特に, $\lambda_2(A-vv^{\top})\leq \lambda_2(A)$.

さて、$G_\sigma$の次数行列$D$と隣接行列$A$を用いて$P_\sigma=D^{-1}A$と表せます。さらに$\lambda_2(A)\leq 0$です。また、$\lambda_2(P_\sigma)=\lambda_2(D^{-1/2}AD^{-1/2})$およびSylvesterの慣性法則により$D^{-1/2}AD^{-1/2}$と$A$の正の固有値の個数は一致するため、$\lambda_2(P_\sigma)\leq 0$を得ます。

定理 (Sylvesterの慣性法則)

対称行列$A\in\mathbb{R}^{n\times n}$と正則行列$S$に対して、$A$と$SAS^\top$の①正の固有値の個数、②負の固有値の個数、③ゼロ固有値の個数は全て一致する。

高次元エクスパンダー: 局所エクスパンダー性の定義とOppenheimのトリクルダウン定理

前回に引き続き高次元エクスパンダーの導入をします。前回の記事では単体複体に関する基本的な用語を定義しました。今回の記事では(純粋な)単体複体に対してエクスパンダー性という性質を定義します。

グラフのエクスパンダー性

元来「エクスパンダー性」という用語はグラフに対して定義される用語です。本記事ではグラフのエクスパンダー性の最低限の定義を述べます。詳しく知りたい方は私が以前mathlogで執筆したこちらの記事をご覧ください。

本記事でグラフと言えば有限集合$V$と2元部分集合族$E\subseteq\binom{V}{2}$の組$(V,E)$で定義されます. 関数$w\colon E\to\mathbb{R}_{\geq 0}$を辺重みと呼び、三つ組$(V,E,w)$を重み付きグラフ (または辺重み付きグラフ) と呼びます。辺の向き、多重辺、自己ループは考えません。

重み付きグラフ$(V,E,w)$に対して重み付き隣接行列$A\in\mathbb{R}_{\geq 0}^{V\times V}$を

\begin{align*} A(u,v) = \begin{cases} 0 & \text{if $\{u,v\}\not\in E$},\\ w(\{u,v\}) & \text{ if $\{u,v\}\in E$} \end{cases} \end{align*}

と定義します。重み付き次数行列$D\in\mathbb{R}_{\geq 0}^{V\times V}$を

\begin{align*} D(u,v) = \begin{cases} 0 & \text{if $u\neq v$},\\ \sum_{w\in V} A(u,w) & \text{ if $u=v$} \end{cases} \end{align*}

とします。最後に遷移確率行列$P$を

\begin{align*} P=D^{-1}A \end{align*}

とします。直感的には頂点$u$からスタートして辺重みに比例した確率で隣接点$v$に移動するランダムウォークを考えたとき、$P(u,v)$の値は頂点$u$から$v$に遷移する確率と等しくなります。なお、$w$を正の定数倍をしても行列$P$は不変です。

$P$は確率行列(各行和が1)なので全ての頂点$u\in V$に対して$\sum_{v\in V}P(u,v)=1$となります。これを行列の形で書くと$P\mathbb{1}=\mathbb{1}$です ($\mathbb{1}\in\mathbb{R}^V$は全ての成分が$1$のベクトル)。すなわち$P$は固有値$1$を持ち、対応する固有ベクトルは$\mathbb{1}$です。この記事の命題1から$P$の他の固有値も全て実数になることが示せます。これらを大きい順に並べて$1=\lambda_1\geq \lambda_2\geq\dots\geq\lambda_{|V|}$とし、これらを第一固有値、第二固有値、などと呼びます。$\lambda_2\leq\lambda$を満たすような重み付きグラフ$G=(V,E,w)$を$\lambda$-エクスパンダーといいます(注)。行列$P$の第二固有値を$\lambda_2(P)$と表します。

注：本来はエクスパンダー性は$\max\{\lambda_2,|\lambda_{|V|}\}\leq\lambda$を満たすグラフとして定義されますことが多いです。ここでは非自明な固有値が絶対値の意味でバウンドされていることを要請しています。しかし単体複体上のランダムウォークの文脈では片側だけのバウンドで事足りるので、ここでは$\lambda_2$の上界のみを考えます。とりあえず$\lambda_2$が小さければ小さいほど良いエクスパンダーであると思ってください。

基本的に考えるグラフは連結であるとします。非連結なグラフの場合、各連結成分の指示ベクトルが固有ベクトルとなり固有値1の多重度が2以上になるからです。

例: 完全グラフ

$G=(V,E,w)$をunit weightの$n$頂点の完全グラフとします。すなわち$|V|=n$で$E=\binom{V}{2}$であり、さらに$w(\{u,v\})=1$とします。全ての成分が$1$の行列を$J$、単に行列を$I$と表すと、$G$の隣接行列は$J-I$と表せます。この行列の第二以降の固有値は全て$-1$なので、遷移確率行列は$\lambda_2=\dots=\lambda_n=-\frac{1}{n-1}$となるので、$G$は$\left(-\frac{1}{n-1}\right)$-エクスパンダーです。

単体複体のエクスパンダー性 (局所エクスパンダー)

重み$w$を持つ純粋な$d$次元単体複体$X=(V,\mathcal{F})$を考えます。次元$k$以下の面全体からなる単体複体$X_k=(V,\mathcal{F}_k)$を$k$-スケルトン ($k$-skelton) といいます。元の単体複体$X$が重み付きならば$k$-スケルトンも同じ重みを考えて重み付きとみなします。

特に$1$-スケルトン$X_1=(V,\mathcal{F}_1)$はグラフ$(V,X(1))$とみなせます。$X$が重み付きならば辺重みを$w_1\colon X(1)\to\mathbb{R}_{\geq 0}$とすることで重み付きグラフ$(V,X(1),w_1)$を考えることができます。これを$X$の$1$-スケルトングラフと呼ぶことにします。

面$\sigma\in\mathcal{F}$のリンク$X_\sigma$に対してその$1$-スケルトングラフを$G_\sigma$とします ($\dim\sigma \leq d-2$とします)。これの遷移確率行列を$P_\sigma$とします。全ての$G_\sigma$が$\lambda$-エクスパンダーであるとき、$X$は局所$\lambda$-エクスパンダーであるといいます。基本的に全ての$G_\sigma$は連結であるとします。

特に、$X$の重み$w_d\colon X(d)\to\mathbb{R}_{\geq 0}$が非ゼロの定数関数ならば、各面$\sigma\in X(d-2)$のリンク$X_\sigma$がなす$1$-スケルトングラフの辺重みは全て同じ値になる (つまり正規化すれば重みなしグラフとみなせる) ことに注意してください。

例: 完全単体複体

各$-1\leq k\leq d$に対して$X(k)=\binom{V}{k+1}$を満たす単体複体を$d$次の完全単体複体と呼びます。これは完全グラフを単体複体に拡張したものになっています。unit weightを考えます (すなわち$w_d(\sigma)=1 (\forall \sigma\in X(d))$で重みづけする)。$\sigma\in X(k)$に対しグラフ$G_\sigma$は$|V|-|\sigma|$頂点の完全グラフとなり、辺重みは一様なので、$\left(-\frac{1}{|V|-|\sigma|-1}\right)$-エクスパンダーです。

Oppenheimのトリクルダウン定理

重み付き単体複体を考えたとき、再帰的に定義された面の重みで定まる行列の固有値を計算することはとても難しく、定義通りにやろうとすると完全単体複体など簡単なものでしかなかなかできないとおもいます。Oppenheimのトリクルダウン(tricling down)定理は次元$k$の面のエクスパンダー性を次元$k+1$の面のエクスパンダー性に帰着する定理です。

$X$を純粋な$d$次元単体複体とします。各$-1\leq k\leq d-2$に対して

\begin{align*} \mu_k = \max_{\sigma\in X(k)} \lambda_2(P_\sigma) \end{align*}

とします。

定理 (Oppenheimのトリクルダウン定理; [1]).

全ての$G_\sigma$が連結であるならば、各$-1\leq k< d-2$に対して\[\mu_k \leq \frac{\mu_{k+1}}{1-\mu_{k+1}}.\]

trickling downとはあえて和訳すると「浸透」という意味です。経済学には「trickle-down」(トリクルダウン)という用語があるらしく、経済活動の活性化が富裕層から下級層に浸透していくみたいな意味があるらしいです。この定理は高次元リンクのエクスパンダー性が低次元リンクに「トリクルダウン」することを主張しています。2018年に証明された定理ですが高次元エクスパンダーの文脈ではOppenheim's Trickling Down Theoremと呼ばれています。知名度の高い和訳はまだないと思いますが、これに倣って私も脳内で「トリクルダウン定理」と呼んでいます。

系1.

$\mu_{d-2}\leq 0$ならば$X$は局所$0$-エクスパンダーである。

すなわち、局所エクスパンダー性を示すには次元$d-2$の面だけ考えれば良いということになります。完全単体複体の例の直前の段落でも述べましたが次元$d-2$の面であれば重み関数も簡単な形になるので局所エクスパンダー性の確認が容易になります。特に、トリクルダウン定理を使うと以下を証明することができます。

系2.

マトロイド$(V,\mathcal{F})$は局所$0$-エクスパンダーである。

端的に言えば系2は「マトロイドはエクスパンダーである」ことを主張しています。グラフエクスパンダーの文脈ではエクスパンダー性はランダムウォークのrapid mixingに直結するのですが似たようなことが単体複体にも成り立ちます。

次回の記事ではトリクルダウン定理を用いて系2の証明を行います。その次の記事でトリクルダウン定理の証明を行います。

文献

[1]. Oppenheim, Izhar. 2018. “Local Spectral Expansion Approach to High Dimensional Expanders Part I: Descent of Spectral Gaps.” Discrete & Computational Geometry 59 (2): 293–330. https://doi.org/10.1007/s00454-017-9948-x.