数理解析研究所講究録1093 巻 1999 年 236-241236

グラフ上の局所多数決問題の確率的アプローチ
福岡教育大学・教育中田寿夫

九州大学工九州大学. システム情報

今林裕
山下雅史

(Toshio NAKATA)(Hiroshi IMAHAYASHI)(Masafumi YAMASHITA)

概要

Motivated by the study of deterministic local majority polling game by Peleg et al.,this article investigates a repetitive probabilistic local majority polling game on a finite
graph by formulating it as a Markov chain.

1

はじめに

多数決は分散コンピューティングにおいて不一致性を解消をするためによく用いられている手段である。 もし重要なデータの冗長な複製を維持する間に失敗が起こったとすると、作動しているプロセッサで投票が行なわれ多数のプロセッサが示した値を正しいデータとして対応することにより、失敗によって引きおこされるダメージに対処するように設定されているわけである。今日の信頼性の高い技術では、与えられた時間のうちの失敗の回数は少なく、その要求レベルは限られたものである。多数決の方法が最も実用的となる自然なセッティングは局所分散データであり、多数決をとる回数や、そのプロセッサのデータを含めた多数決が、局所的に少数のプロセッサで制限されたものである。 これは、その操作に係わるコストを小さくしょうとする実用的考えからそのように望まれているわけである。
上記のものを定式化したものが局所多数決である。すなわち、「(多重辺を許さない、無向、有限) グラフについて各頂点に 0,1 を配置し、各頂点の “近傍” の頂点が参加する多数決で、その頂点の値が になるか 1 になるかを決定する。」というものである。 もちろん、 “近傍’ の意$0$

味や多数決の方法などで種々の問題設定が行えるが、最も単純な設定として以下のように考える:『“近傍” とは [自分自身とそれに繋がっている頂点」とし、各頂点での多数決を「近傍の頂点のうち過半数が 1 であれば 1 に、 そうでなければ に」なるように各頂点について同期的に行う』。 この設定の下で次のような問題が調べられた。「頂点数が $N$ のグラフについて、少数の 1 が多数の を支配する 1 (局所的な多数決で全ての頂点が 1 になってしまう) にはどれくらいの 1 が必要か ? 上その答えは、「\Omega ( $\sqrt$N) 個は必要で、実際に $O(\sqrt{N})$ 個かかる例が存在する」 (Linial 他 [6]) というものであった。また、 “近傍 7 を -近傍 $(r\geq 2)$ にするなどして、種々の設定の下で Peleg らによって盛んに研究されている ([2], [9])。これらは–度の多数決に$0$$0$$r$

より少数の頂点でどれだけの多数の頂点に影響を与える事ができるか、その評価と、最大を達成するようなグラフの例を挙げることを研究の目標としている。 このような局所多数決の研究の結果は、 Peleg の$\triangleright \text{ビ_{}\mathrm{I}^{-}}[8]$においてまとめられている。

また、そのレビュ一には、数回多数決を行い、その後に全ての頂点が同じ値になるようなセッ(これは、分散合意形成問題のモデルにティングを考える研究も紹介されている$[8, \S 8 \mathrm{P}.19\sim]$なっている)。 これは、有限集合の力学系の研究に他ならないわけであるが、その有限性ゆえに、それは最終的には周期状態や種々の定常状態におちこむことがわかる。それゆえ、ほとんどの場合がシステムとして合意されず (すなわち、すべて やすべて 1 である定常状態に落着く$0$

1 全体を支配する頂点の集合のことを Monopoly という237とは限らない)、その意味では合意形成問題に対しては適しているとは言えない。上記の問題を回避するためにここでは、確率論的な制御を施した局所多数決問題についてを導入する。すな
わち、確率的な局所多数決を繰り返すことによって周期的な状態など合意に至らない状態を排除するわけである。 もちろん、場合によってはすべてが間違った方に合意してしまう恐れもあるが、得られた定理によってその確率は簡単に計算できる。確率的な多数決としては [8, \S 8.1.5」 といP.24] で、わずかに紹介されているが、 引用してある論文等がみられず、 ilittle isうことであるので、 この確率的問題について少し定式化しておく必要がある。
$\mathrm{k}\mathrm{n}\mathrm{o}\mathrm{w}\mathrm{n}$2準備与えられたグラフ $G=(V, E)$ にっいて、各頂点のコンフィギ n レーションをあらわす集合
を三 $=\{0,1\}^{V}$ として、$\Gamma(n)$$=$$\{i\in V:\{i, n\}\in E\}\cup\{n\}$$N_{\xi}(n, \epsilon)$$=$$|\{i\in V : \xi_{i}=\epsilon, i\in\Gamma(n)\}|$

for$\epsilon\in\{0,1\}$とする。すなわち、とは頂点 からの 1-近傍の頂点の集合 (頂点 からの距離が 1 以下のものでとは $\xi\in---$ について頂点自身も含む)、とその近傍の中に含まれる の個数である。
$\Gamma(n)$

$n$

$n$

$N_{\xi}(n, \epsilon)$

$n$

$n$

$\epsilon$

定義 2.1 (確率的多数決) 状態 $\xi=(\xi_{1}, \xi_{2}, \cdots, \xi|V|)\in---$ について、それが状態に (確率的に) 推移するとする。各頂点の状態が’ に推移する確率を$—$$\eta=(\eta_{1}, \eta_{2}, \cdots, \eta|V|)\in$$q_{\xi}(i, \eta_{i})$$\xi_{i}$$\eta_{i}$と定める。

ただし、$q_{\xi}(i, 1)= \frac{N_{\xi}(i,1)}{|\Gamma(i)|}$である。 また、状態 が状態
以下のように定める :$\xi$$\eta$$t_{\xi,\eta}$$q_{\xi}(i, 0)= \frac{N_{\xi}(i,0)}{|\Gamma(i)|}$に推移する確率を各頂点の推移がそれぞれ独立であるとして、$\prod_{i\in V}q_{\xi}(i, \eta i)$

補題 21 行列,は次をみたす :$t_{\xi,\eta}\geq 0$

これにより、は確率行列であるので、率空間について、である。 -町確率過程
を$- t_{\xi_{:}\eta}$,$t_{\xi,\eta}$($=t_{\xi,\eta}$とおく)$\Sigma_{\eta\in_{-}^{-}}-t_{\xi},=1\eta$を推移行列とする Markov 連鎖が導入される : 確とする。ただし、
三, $n=0,1,$ ,として、定義 21 より、推移確率を$\Omega=-^{\mathrm{N}\cup}--\{0\}\ni\xi^{arrow}=(\xi^{0}, \xi^{1}, \cdots)$$(\Omega, P)$$—$$\{X_{n}\}_{n=0},1,\cdots$$\xi^{n}\in$$X_{n}(\xi)arrow=\xi^{n}$$t_{\xi,\eta}= \prod_{i\in V}q_{\xi}(.i, \eta i)=P(X_{n+}1=\eta|X_{n}=\xi)$とする定常な Markov 連鎖が導入される。

. 例 2.1 グラフが 3 頂点からなる線グラフの場合、$\Xi=${(000), (001), (010), (011), (100), (101), (110), (111)}$*\cdot$

238
であ$\text{り_{、}}$

推移行列は$(00^{0)}(0\iota(00(1\mathrm{o}_{1}\mathrm{o})(01(1(110)(1010)1)1)1))(1/11/1/31/30\mathrm{o}^{6}\mathrm{o}12$3$1/1/1/610_{3}000/612$$1/1/1/1/0\mathrm{o}_{6}\mathrm{o}^{6}\mathrm{o}126$$1/121/1/31/000066$$1/1/1/1/\mathrm{o}_{12}\mathrm{o}_{6}00^{6}3$$1/121/611000^{6}0//6$$1/11/11/3000_{6}0/62$$1/1/1/1/\cdot 6000^{3}1132)$

結果
任意の有限連結グラフ $G$ について、上で導入した Markov 連鎖について以下のことが言える。

(i) 状態、 1 状態はそれぞれ他の状態に到達する確率は である。
状態 ‘ 1 状態でない{ 状態、 1 状態} については任意の状態に到達可能で定理 3.1(ii)

$0$

$0$

$0$

$\xi\in-=\underline{\underline{\wedge}}---\backslash$$0$ある。

これを証明するために次の補題を用いる。とについて $d(\xi, \eta)=1$ であるならば補題 310 状態でも 1 状態でもないとする。に到達可能である。ただし、距離 ?J ハミング距離$\xi\in-\underline{\underline{\wedge}}$$\eta\in---$

$d$

$\xi$

は$\eta$$d( \xi, \eta)=\sum_{i}\in V|\xi_{i^{-}}\eta_{i}|$補題 31 の証明は–回自明のように思えるが、 きちんと証明しようとするとかなり手間がかかる。定理 3.1 の (i) は自明であり、 (ii) の証明は補題が言えれば比較的簡単に証明することができる。

系 3.1 周期的な状態は 状態 (すべての頂点が となる状態) と 1 状態 (すべての頂点が 1 となる状態) に限定され、他の状態の集合倉は (Markov 連鎖の意味で) 推移的であり、 状態と 1状態のどちらかに有限時間内に確率 1 で吸収される。
$0$$0$$0$

系 3.1 を見れば分かることだが、 吸収壁をもった Markov 連鎖と解釈することができる。すな
わち、 この問題を古典確率論的には「破産の問題」 2 ([5, P.113]) の異なったバージョンと捉えることもできる 3とし、その列を(P\xi )\xi \in 三と状態 から出発して最終的に 状態に吸収される確率を。

$0$

$\xi$

$p\xi$$\mathrm{p}=$する。 これは次の斉次型の差分方程式の境界値問題の解としてあらわすことができる。

補題 32
(1)

$T\mathrm{p}=\tilde{\mathrm{p}}$ドルの資産を持っており、 コイン投げをして、表が出れば A が に 1 ド
22 人の賭博師 A,B がそれぞれルを裏が出れば が A に 1 ドルを払うゲームを繰り返し、 どちらかが破産するまで続ける問題。すなわち、 2 つの吸収壁をもつランダムウォークの問題と解釈することができる。
3 破産の問題はランダムウォーク (独立同分布の確率変数の和) で表現することができる。 しかし、 ここでの問題は Markov 連鎖とはなっているが、 ランダムウォークではない。
$\mathrm{B}$$\mathrm{N}/2$$\mathrm{B}$239
ただし、$T=(t_{\xi,\eta})\xi,\eta\in_{-}--$

であり、$\tilde{\mathrm{p}}=(\tilde{p}_{\xi})\epsilon\in\underline{=}$1$0$$\tilde{p}_{\xi_{\lrcorner}}=\{$$p_{\xi}$

逆に (1) をみたす$\mathrm{P}$について( は 状態)(\xi は 1 状態)
(その他)
$\xi$

$0$

(2)

は–意的に存在する。

証明は [5, 定理 331(P.88)] を少し変形すれば容易にできる。補題 32 について解がみつかり吸収確率が次のように計算できる。
定理 32 状態$\xi$

から出発して状態に吸収される吸収確率は以下のとおりである 4 :$0$$p_{\xi}= \frac{\Sigma_{i\in V:\xi}i=0|\Gamma(i)|}{\Sigma_{k\in V}|\mathrm{r}(k)|}$(3)(証明) (2) をみたすことをチェックすれば十分である。すなわち$\sum_{\eta\in_{-}^{-}}t_{\xi,p=\tilde{p}}-\eta\eta\epsilon$を示せばよい。 ここで、$\xi$が状態、 1 状態のときには簡単に証明できる。 よって、

$0$$\eta\in_{-}^{-}\sum_{-}(\prod_{i\in V}.\frac{N_{\xi}(i,\eta_{i})}{|\mathrm{r}(i)|})(_{\eta_{J}}\sum_{-,-0}|\Gamma(j)|)=\sum_{\xi_{\mathrm{i}}=0}|\Gamma(i)|$(4)であることを示せば十分である。左辺を (LHS) とおくと(LHS)

$=$

...

$\sum$$\sum_{\eta_{\mathrm{I}V1^{\in\{0,1\}}}}(_{i\in V\backslash \{\}}\prod_{1}\frac{N_{\xi}(i,\eta_{i})}{|\Gamma(i)|}\mathrm{I}\frac{N_{\xi}(1,\eta_{1})}{|\Gamma(1)|}\sum_{j\in V\backslash \mathrm{f}1\}\eta J^{-}-0}|\mathrm{r}(j)|$$\eta_{1}\in\{0,1\}$$=$$\cdot$$( \frac{N_{\xi}(1,1)}{|\mathrm{r}(1)|})\sum_{\eta_{2\in}\{01\}}$..

$\eta_{|V|}\in\sum_{\{0,.1\}}(\prod_{i\in V\backslash \{1\}}\frac{N_{\xi}(i,\eta_{i})}{|\mathrm{r}(i)|})j\in V\backslash \{\}\eta_{j}=0|\sum_{1}\Gamma(j)|$,$+$$( \frac{N_{\xi}(1,0)}{|\mathrm{r}(1)|}\mathrm{I}\eta 2\in\{01\}\eta V|\in\sum\sum_{1\{0,1\}},\cdots(_{i\in V\backslash \{\}}\prod_{1}.\frac{N_{\xi}(i,\eta_{i})}{|\Gamma(i)|}\mathrm{I}(\{\sum_{j\in V\backslash 1\}\eta j=0}|\Gamma(j)|+|\Gamma(0)|)$$\cdot$$= \sum_{\eta_{2\in\{\}}01}$..

$\sum_{\eta_{\mathrm{I}V|\in}\{0,1\}}(_{i\in V\backslash \{\}}.\prod_{1}\frac{N_{\xi}(i,\eta_{i})}{|\mathrm{r}(i)|}\mathrm{I}(_{j\in V}\{\sum_{\backslash 1\}\eta j=1}|\mathrm{r}(j)|)$

,..

$+$

$\eta_{|V|\in\{1\}}\sum_{0},(_{i\in V\backslash \{\}}\prod_{1}\frac{N_{\xi}(i,\eta_{i})}{|\Gamma(i)|}\mathrm{I}$$N_{\xi}(1,0) \sum_{0\eta 2\in\{1\}},\cdot$

補題 2.1 の計算の途中の式により$\sum_{\eta_{2\in\{\}}01},\cdot$..

$\sum_{\eta_{|V|\in}\{0,1\}}(_{i\in V\backslash \{\}}\prod_{1}\frac{N_{\xi}(i,\eta_{i})}{|\mathrm{r}(i)|}\mathrm{I}=1$

4 統計力学の見地から言うと、 この分布は Gibbs 分布と呼ばれている分布の形になっており、非常に興味深いものである。

240
であることがわかるので、上の計算を再帰的に計算すると、(LHS)$= \sum_{i\in V}N_{\xi}(i, 0)=\sum_{\xi_{i}=0}|\Gamma(i)|$となり証明がおわる。 1

紙面の都合上、具体的なグラフについての定理 32 の応用を示すことができないが、 [7] に図を使って説明してあるので参照されたい。定理 32 の設定 ( という状態かは始めること) は初$\xi$のみに台をもつ Dirac 分布として捉えることが期分布が $\delta_{\xi}=(0, \cdots, 0,1, 0, \cdots, 0\xi)$ というでき、 確率的多数決を十分に行った後の極限分布は$\{\xi\}$1$\mathrm{k}\backslash \text{態_{}\backslash }$$\lim_{karrow\infty}\delta_{\xi}T^{k}=(p\xi 0\backslash \mathrm{R}\text{態}, 0, \cdots, 0, ]-p_{\xi})$.

すなわち、 { 状態, 1 状態} の 2 点に台をもつ分布で、その値がそれぞれ$0$$p_{\xi},$$1-p\xi$であることを言っている。初期分布を–般の分布とすると、次のこともわかる。
を与えたときには系 32 任意の初期分布
布についての平均となる。 すなわち、$\pi=(\pi_{\xi})_{\xi-}\in--$$p_{\pi}= \sum_{--}\xi\in^{-}\pi_{\xi F}\xi$$0$状態への吸収確率$p_{\pi}$

は (3) の初期分.

系 3.2 によって、失敗やすいプロセッサの様子をあらわす確率分布がわかっておれば、それを初期分布とすることによって 状態に合意する確率が計算できるわけである。
$0$

注意 3.1 定理 32 により$0$状態への吸収確率は である頂点の数とともに増加し、同数の 1 を$0$配置するときには、なるべく次数の低い頂点に配置すると吸収確率も大きくなることがわかる。
例 3.1 例 21 か年導かれる$0$

状態 (000) への吸収確率は$(p(000),p_{(0}01),P(010),p(011),p(100),p(101),p(110),p_{(1}11))=(1,$4$\frac{5}{7},$$\frac{4}{7},$$\frac{2}{7},$$\frac{5}{7},$$\frac{3}{7},$$\frac{2}{7}.0)$

まとめと今後の課題
これまで確率的多数決を定式化して、$0$状態、 1 状態への吸収確率の求め方を議論したわけであるが、吸収されるまでにどれだけのステップ数がかかったか気になるところである。実は、平均吸収時間についても平均吸収確率と同様に補題 32 によく似た差分方程式の境界値問
題を解けばよい 5 。また、平均再帰時間を求める方法と似た方法を用いて、平均吸収時間を (2の頂点乗のサイズの) ある行列の逆行列を求める問題に帰着することができる。 しかし、結果的には上記の 2 つは同じ計算をすることに帰着され、明示的にその解を書き下すことは (筆者と、 回目の多数決の後の分布にとっては) 困難な事である。そこで、定常分布を評価して平均吸収時間を評価することを考の距離についてえる 6 また、 Perron-Frobenius の定理 ([10] を参照) を用いると、その距離$\theta=(\theta_{\xi})_{\xi}\in---$$\theta^{n}=(\theta_{\xi}^{n})\xi\in\Xi$$n$$D(\theta, \theta^{n})=\Sigma\xi\in--\cdot|\theta_{\xi}-\theta_{\xi}^{n}|/2$$D(\theta, \theta^{n})$$\dot{\mathrm{Q}}$

5 補題 32 は斉次型であったが、平均吸収時間については非斉次型の方程式である。
6 (平均吸収時間)となり上から評価できることが Markov 連鎖の 般論よりわかる。これは ‘ その状態が再帰的である時において平均再帰時間の計算方法とほぼ同じ方法で行うことができる。
$\leq\sum_{n}D(\theta, \theta^{n})$241$C>0,0<\lambda<1$ が存在して$D(\theta, \theta^{n})\leq C\lambda^{n}$をみたし、指数のオーダ$\lambda$は推移行列の第 2 固有値の絶対値、すなわち、絶対値が 1 より小さい最大の固有値の絶対値となっていることが分かる。 この設定において、 グラフの形状との関係が気になるところであるが、現在のところ何も分かっていない。また、その係数 まで評価するのは困難である。 しかし、 Markov 連鎖のうちでも有限集合上での特殊なランダムウォ クの場合であれば、 Aldous [1], Diaconis [3]$\lambda$$C$–

らによって、その係数は有限群上でのフーリエ変換の手法を用いてある程度評価されている 7

我々の設定では、その方法を直接使うことは不可能であるが、類似の方法が使えないか思案中である。

参考文献[1] D. Aldous; Random walks on finite groups and rapidly mixinig Markov chains, Lecture
Note in Math. 986, 243-297, Springer (1983).

[2] J-C.Bermond and D. Peleg; The Power of Small Coalitions in Graphs. Proc. 2nd Colloq.
on Structual Information Communication Complexity, Olympia, Greece, June 1995,
Carleton Univ. Press, 173-184.
$\xi y$[3] P. Diaconis; Applications of Non-Commutative Fourier

nalysis to Probability Problems, Lecture Note in Math. 1362, 51-100, Springer (1988).
$\dot{\mathrm{A}}$[4] E..Goles and J. Olivos; Periodic behaviour of generalized threshold functions, DiscreteMath. 30, 187-189, 1980.

[5] 小和田正; マルコフ連鎖, 現代数学全書 5, 白日社, 1973.
[6] N. Linial, D. Peleg, Y. Rabinovich and M. Saks, “Sphere packing and local majorities in graphs,” Proc. 2nd Israel Symposium on Theoretical Computer $Science_{f}$ IEEE

Computer Soc. Press, 141-149, 1993.
[7] 中田, 今林, 山下; グラフ上の局所多数決問題の確率的アプローチ、 1999 年冬の LA シンポジウム予稿集, pp. 45-1.
[8] D. Peleg; Local Majority Voting, Small Coalitions and Controlling Monopolies in
Graphs: A Review, Technical Report (1996). wisdom. weizmann.
http:. html.
$//\mathrm{w}\mathrm{w}\mathrm{w}$$\mathrm{a}\mathrm{c}.\mathrm{i}\mathrm{l}/\mathrm{P}\mathrm{a}\mathrm{p}\mathrm{e}r\mathrm{S}/\mathrm{t}\mathrm{r}\mathrm{S}/\mathrm{C}\mathrm{s}96-12/\mathrm{a}\mathrm{b}\mathrm{S}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{t}$[9] D. Peleg; Graph Immunity$\mathrm{A}\dot{\mathrm{g}}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{s}\mathrm{t}$Local Influence, Technical Report (1996).

[10] E. Seneta; Non-negative Matrices and Markov Chains, Second Edition, Springer Seriesin Statistics, (1981)

7 ラフに言うとその分布にフーリエ変換(の類似) を施して、そこで各々の確率変数の独立性と同分布性を使ってそれを評価する。その後に逆変換して、定常分布までの近さを評価している。 この手法は「トランプを何回シャッフルすれば–様分布に近づけることができるか ? 「ルーピックキューブをランダムに動かしたときに何回くらいで–様分布に十分近づけることができるか ? 」などを究明する上で興味深い考察がなされてある。詳しくは [1]$\lrcorner_{\text{、}}$を参照のこと。