グラフ上での確率過程の双対性

前回の記事に引き続き、今回の記事でも双対性について紹介します(?)

双対の概念は最適化の文脈で語られることが多いですが、他にもグラフ理論をはじめとした色んな文脈でも登場します。グラフ理論では平面グラフの双対性、木幅と茨の双対性などが知られています。本記事では確率過程の分野で知られる
・Coalescing Random Walk
・(synchronous) Pull Voting
の双対性を紹介します。

この記事では、$G=(V,E)$ を無向グラフとし、その頂点数を $n=|V|$ で表します。

Coalescing Random Walk (CRW) とはグラフ上の離散時間ランダムウォークの一種です。まず全頂点上にトークンが一つずつ乗っています。そして、各時刻で全てのトークンはそのグラフ上でランダムウォーク（隣接点を一様ランダムに選び、そこにトークンを移動させる）を同時にします。すると同じ頂点に複数のトークンが乗ることがあります。このとき、それらのトークンは合体 (coalesce) して一つのトークンになります。ここまでの流れを1ステップと捉え、トークンが一つになるまでこのステップを繰り返すというのが CRW になります。

CRWのシミュレーション。

赤い頂点にトークンが乗っています。

下の動画はグラフを大きくして高速再生しています。

最後の2,3個のトークンが合体するまでが長いですね。

Pull Voting (PV) ではまず初期状態として、各頂点 $v\in V$ が意見 $o_v\in \{1,\ldots,n\}$ を持ちます。そして各時刻で全ての頂点が同時に隣接点を一つランダムに選びます。その後、自分の持つ意見を、選んだ頂点の持つ意見に同時に更新します。これを全ての頂点が同じ意見になるまで繰り返します。このように、各頂点が合意に至るまで意見を更新し続ける過程を voting process や voting model と呼んだりします。PV は voting process の一つです。以前の記事では別の voting process として Best-of-Two と Best-of-Three を紹介しています。voting process の解析は、ネットワーク上での意見形成 (opinion forming) や、分散コンピューティングにおける合意問題を解決する有効なアプローチとして注目されています。例えば、分散ネットワークシステムでリーダーを決めたいということが多々あります。このときに、PVを行い最終的に合意した色を最初に持っていた頂点をリーダーとすればいいですよね。下の動画はpull votingのシミュレーションです。

　　　  

　　　　 

     

Pull Votingのシミュレーション。色は意見を表します。

最初の数ステップで一気に意見が減ります。

最後の2,3意見が消えるまでが長いですね。

これらの過程を研究する上での興味は、その過程が終わるまでにかかるステップ数です。PVではリーダー選出などを行う際、高速に合意することが望ましいですよね。CRW において全トークンが一つに合体するまでにかかるステップ数を coalescing time と呼び、$T_{\mathrm{coal}}$ と書きます。PVで全頂点が同じ意見に収束するまでにかかる時間を consensus time と呼び、$T_{\mathrm{cons}}$ と書くことにします。

この記事で説明するのは、同じグラフ上での CRW と PV を考えたときに成り立つ

$$T_{\mathrm{cons}} \geq T_{\mathrm{coal}}$$

という不等式です(*)。これの証明は（あとで説明しますが）PV の時間発展を逆再生すると CRW が出てくるという事実を使います。これはある意味で双対になっていて、もう少し一般的な確率過程に対して双対性を使って色んな結果を得たという論文もあります。

(*) 厳密にいうと、$T_{\mathrm{cons}} \leq T_{\mathrm{coal}}$ を満たす coalescing random walk と pull voting のカップリングが存在するという主張です。

まず、以下のグラフ上でのpull voting の時間発展を考えます。説明の都合上、各頂点は自己ループを持つと思ってください（なので、ランダム選択したときに自分自身を選ぶこともありえます）。

図1. グラフ (色は意見を表す)

図2. pull voting の時間発展。矢印は参照関係を表していて、

例えば時刻0で緑は青を選び、オレンジは赤を選びその意見を引っ張る。

最終時刻以外の時刻では全頂点の入次数=1となっています。

次に、図2の各辺の始点と終点を下図のように反転させ、逆再生したものを考えます (隣接した二列の役割が入れ替わった感じです）。

図3. 図2の辺の向きを入れ替え、逆再生した（赤に接続する辺だけ書いた）。

全部の辺をちゃんと書くと初期時刻以外の全頂点の出次数=1になります。

図3を見ると、CRWを再現することができます。図3における$t=0$をCRWの初期状態だと思うと（つまり全頂点にトークンが乗ってる）、トークンの移動を矢印で表現した図と解釈できます。このことは、次の図をみながら考えれば分かると思います。

図4. 一つの頂点に着目したときのPVとCRWの振る舞いの比較.

図4上では、PVのある時刻 $t$ において青頂点がランダム隣人として赤頂点を選択し、その意見を引っ張り時刻 $t+1$ では赤になった様子を表します。図4下では、トークンが乗った赤頂点がランダムに隣人を選択し、そこにトークンを移す様子が図示されています。つまり、「意見を引っ張って赤になった」ことと「トークンを渡して青になった」が逆再生すると全く同じになります。

一方で図3の$t=1$ (右から2番目の列) の一番下の頂点は赤いですが、この解釈でいうとトークンは乗っていません。ですので、「赤頂点＝トークンを持つ頂点」は成り立ちません。しかし、「赤頂点 $\supseteq$ トークンを持つ頂点」は成り立ちます。CRWが終わるまでの時間 $T_{\mathrm{coal}}$ を考えていましたが、これはトークンが一つになるまでの時間でしたので、図2や3から分かるように、PVが合意するまでにかかった時間 $T_{\mathrm{cons}}$ で上から抑えることができます。

厳密な証明ではないですが、このようにPVを逆再生するとCRWが出てくるという性質はとても面白いですよね。

実は$T_{\mathrm{coal}}=T_{\mathrm{cons}}$が成り立つカップリングが構成できます [1].

[1] Petra Berenbrink, Andrea Clementi, Robert Elsässer, and Peter Kling, Ignore or Comply?: On Breaking Symmetry in Consensus, PODC17.

計算量理論におけるuniform/nonuniform

計算量理論は色んな仮定の下で様々な帰結を導出するということをしています。その仮定の中には
・$E\not\subseteq \mathrm{SIZE}[2^{\Omega(n)}]$ (脱乱択化におけるPRG構成の文脈)
・$NP \not \subseteq \mathrm{coNP/poly}$ (FPTのカーネル化の文脈)
・$NEXP \not \subseteq \mathrm{P}/\mathrm{poly}$ (PITの脱乱択化の文脈)
といったものがあります。既存結果の下界はどのような仮定の下で成り立つのかを把握する際にもこれらはどのようなクラスなのかを知っておく必要があります。「/poly」という概念は問題がuniform/nonuniformに解けるということを表します。ここではuniform/nonuniformに解けるとはどういうことかを説明します。

計算量理論には回路計算量というトピックがあります。これはある判定問題に対してそれを解く回路のうち最小サイズがどの程度になるかということを考えます。P$\neq$NP予想は「NP問題のうち多項式時間で解けないものが存在する」ことを意味しますが、同様に NP$\neq$P/poly という予想があります。これは「NP問題のうち多項式サイズの回路で解けないものが存在する」ことを意味します。

それでは、「多項式時間で解ける」ことと「多項式サイズの回路で解ける」ことは異なるのでしょうか？

回路とはどのようなものかを思い出すと、and/or/notゲートとinputゲートからなるDAGであって、$n$変数の回路$C_n$が関数$f:\{0,1\}^n\to\{0,1\}$を計算するというのは

$\forall x\in\{0,1\}^n:C_n(x)=f(x)$

が成り立つことをいいます。判定問題$L$が回路族$\{C_n\}_n$で解けるというのは

$\forall n\in \mathbb{N}$, $C_n$が$L_n$を解く ($L_n$は$L$の入力長$n$への制限)

が成り立つことをいいます。

結論からいうと問題$L$に対してそれが
・uniformに解ける ＝ $L$を解くあるチューリング機械$M$が存在する
・nonuniformに解ける = $L$を解くある回路族$\{C_n\}_n$が存在する
ことをいいます。言い換えると、uniformに解けるといった場合は一つの機械があれば全ての入力に対応できることを意味しており、nonuniformに解けるといった場合は入力長$n$毎に異なる回路を用意できれば解けることを意味します。P/polyは多項式サイズの回路で解ける問題クラスです。

任意のアルゴリズムは少ないオーバーヘッドで回路に変換できる（c.f. Cook-Levinの定理: 3SATのNP困難性の証明) ので、uniformに解けるならばnonuniformで解けます。一方でnonuniformで解けるからといってuniformでも解けるとは限りません。
例えば以下の問題を考えます：

停止性判定問題
入力: $x\in\{0,1\}^*$
出力: Yes iff $x=1^n$ かつ 「$n$を二進表記した文字列が表すチューリング機械が任意の入力に対し有限時間で停止する」

この問題は入力が特別なフォーマットにしたものと捉えることができますが本質的には停止性判定問題を解かなきゃいけないのでuniformには解けません。一方でnonuniformに解くことはできます。回路$\{C_n\}_n$を各$n$ に対し、$x=1^n$ かつ「$n$を二進表記した文字列が表すチューリング機械が任意の入力に対し有限時間で停止する」ような $n$ ならば $C_n(x)=x_1\land x_2\land \cdots \land x_n$ とし, そうでないならば恒等的に0 (例えば $C_n(x)=x_1\land \overline {x_1}$) とすれば、実際に正しい答えを出力しています。

少しいじわるな例だったかもしれませんが、nonuniformに解けるといったときには $n$毎に回路 $C_n$ は外から用意されているから $n$ に問題の本質的な情報を埋め込まれたようなフォーマットの問題に対してはnonuniform と uniform の間にギャップが誕生してしまいます。

一方で、nonuniformに解けるかつ解く回路が構成できるならばuniformに解けます。