双対の概念は最適化の文脈で語られることが多いですが、他にもグラフ理論をはじめとした色んな文脈でも登場します。グラフ理論では平面グラフの双対性、木幅と茨の双対性などが知られています。本記事では確率過程の分野で知られる
・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.
0 件のコメント:
コメントを投稿