A Random Walk Proof of Kirchhoff's Matrix Tree Theorem

smly • 2016-11-20

Kirchhoff の行列木定理をランダムウォークで証明する論文が面白かったので整理する。

Determinants, their applications to Markov processes, and a random walk proof of Kirchhoff's matrix tree theorem

Kirchhoff's matrix tree theorem is a well-known result that gives a formula for the number of spanning trees in a finite, connected graph in terms of the graph Laplacian matrix. A closely related ...

arxiv.org

ランダムウォークから行列木定理を証明する

行列木定理は，連結グラフにおける全域木の数に関する定理である。よく知られている証明方法は純粋な代数学と Cauchy-Binet の公式によって導くものである。一方で，arXiv:1306.2059 における証明方法はとてもユニークで「ランダムウォークによってすべての全域木を等確率で生成する Wilson’s Algorithm 」を使う。すべての全域木を等確率で生成するのだから，その確率の逆数がグラフにおける全域木の総数と一致する。なので全域木の数を求める問題が「Wilson’s Algorithm における全域木 (uniform spanning tree; UST) の生成確率を求める問題」に変わるわけである。この視点の転換は非常にユニーク。よく知られる証明方法と違い，この証明に必要なものはランダムウォークを扱うためのマルコフ連鎖とほんの少しの代数学的な操作（Cramer の公式から導き出される等式）である。

おさらい

頂点集合 $V = {y_{1}, y_{2}, \dots, y_{n + 1}}$ ，辺集合 $E$ の無向連結グラフ $Γ = (V, E)$ について考える．グラフラプラシアン行列を $L = D - A$ と定義する． $D$ は対角成分がグラフの次数となる次数行列， $A$ は隣接行列である． $L^{{k}}$ を $L$ から $k$ 行 $k$ 列を取り除いた部分行列とする．

定理: Kirchhoff の行列木定理

$Ω = {spanning trees of Γ}$ としたとき，

∣ Ω ∣ = det [L^{{1}}] = \dots = det [L^{{n + 1}}]

が成立する。

すなわち，グラフラプラシアンに対して任意の要素に対する行と列を削除し，その部分行列の determinant が全域木の数と一致する。以降では Wilson’s Algorithm を紹介して，ランダムウォークを用いた行列木定理の証明過程を紹介する。

Loop-erased Random Walk (LERW) & Wilson’s algorithm

普通の単純ランダムウォーク (SRW) をグラフ上で実行した場合，そのパスはループ（閉路や多重辺）を生成する可能性がある。これに対して，ループ除去ランダムウォーク (LERW) は SRW からループが発生した時系列順にループを除去することで，ループのないパスを生成する。

Figure: 左図は単純ランダムウォーク (Simple Random Walk; SRW)、右図はループ除去ランダムウォーク (Loop-erased Random Walk; LERW) の例

$λ = (y_{1}, y_{2}, \dots, y_{j})$ を無向連結グラフ $Γ = (V, E)$ のパスとする． $L E (λ)$ を SRW でループが発生した時系列順にループを除去したパスとする（LE は loop-erasure の略）． $L E ({S_{k}, k = 0, \dots})$ をループ除去ランダムウォーク (Loop-erased Random Walk; LERW) と呼ぶ．

Wilson’s Algorithm

Wilson’s Algorithm は LERW によって得た loop-erasure のパスを branch として，これまでに生成した部分木に追加していくことで全域木を生成する。

初期の branch を生成: 頂点 $y_{0}, y_{1}$ を選択し， $y_{0}$ から $y_{1}$ まで LERW を実行する．得たパスを $Δ_{1}$ とする．
branch の追加: $Δ_{k}$ が与えられたとき，頂点 $y_{k + 1} \in V ∖ Δ_{k}$ を選択する． $y_{k + 1}$ から $Δ_{k}$ までの LERW と $Δ_{k}$ の和集合をとり $Δ_{k + 1}$ とする．
繰り返し: $Δ_{k}$ が頂点集合 VV と一致するまで (2) を繰り返す．

全域木の生成過程を D3.js で可視化した例を見ると明らかであるが，全域木を生成するためのアルゴリズムとして実行速度という面では非効率的な方法である。UST を生成するという特異な性質は注目に値するが，いままでに探索した頂点への再訪を許すアルゴリズムとなっているので， $Δ_{k}$ から遠ざかる方向にランダムウォークするとなかなか木が生成されない。

グラフの定義

Wilson’s Algorithm における全域木の生成確率を導出するために，グラフ上のランダムウォークと行列を用意する．グラフ $Γ$ 上の SRW を ${S_{k}, k = 0, 1, \dots}$ と表記する．このときの遷移確率を以下のように定義する．

P {S_{1} = y_{j} ∣ S_{0} = y_{i}} = p (i, j)

ただし

p (i, j) = \frac{1}{de g ( y _{i} )} if y_{i} is connected to y_{j}

p (i, j) = 0 if y_{i} is not connected to y_{j}

とする。

$p (i, j)$ を $i, j$ 成分に持つ transition matrix を $P$ と表記する． $D$ は対角行列であるため，その逆数を使い $P = D^{- 1} A$ が成り立つ．

おさらいの節でグラフラプラシアン行列を $L = D - A$ で定義したことを思い出す．定義からグラフラプラシアン行列は以下のように式変形できる．

L = D (I - D^{- 1} A) = D (I - P)

ここで $Δ \subset V, Δ \neq = \emptyset$ としたとき，任意の行列 $M$ から $Δ$ に対応する行と列を削除して得られる行列を $M^{Δ}$ と表記する．このとき，

L^{Δ} = D^{Δ} (I^{Δ} - P^{Δ})

が成り立つ。加えて，生成確率の導出の準備として２つの重要な役割を果たす Fact を導出する。

Fact1: グリーン関数

$S_{0} \equiv x$ としたときのマルコフ連鎖の確率分布を $P_{x}$ ，その期待値を $E_{x}$ と表記する．最初に $Δ$ に到着する時間を $ξ^{Δ} \equiv in f {n \geq 0 : S_{n} \in Δ}$ と定義する．ランダムウォークで $Δ$ に到達するまでにある頂点 $y$ に到達する回数の期待値 $G_{Δ} (x, y)$ を考える．

G_{Δ} (x, y) = E_{x} [n = 0 \sum ξ^{Δ} 1_{{y}} (S_{n})] = n = 0 \sum \infty P_{x} (S_{n} = y and ξ^{Δ} > n)

2番目の項は「時間 $n$ に頂点 $y$ にいる」ことを示す指示関数 $1_{{y}} (S_{n})$ を使い期待値で表記している．3番目の項は確率の和によって期待値との等式が成立している．

$y \in / Δ$ であるため，右辺の確率分布 $P_{x}$ は $Δ$ に対応する行と列を取り除いた遷移行列の部分行列 $P^{Δ}$ で置き換えることができる．すなわち，

n = 0 \sum \infty P_{x} (S_{n} = y and ξ^{Δ} > n) = n = 0 \sum \infty (P^{Δ})_{x y}^{n}

右辺の無限級数は，線形代数の初等的な結果から逆数の項への式変形ができる．

n = 0 \sum \infty (P^{Δ})_{x y}^{n} = ((I - P)^{Δ})_{x y}^{- 1}

これは，

(I - P^{Δ}) n = 0 \sum \infty (P^{Δ})^{n}

= (I - P^{Δ}) ((P^{Δ})^{0} + (P^{Δ})^{1} + \dots) = (I + P^{Δ} + (P^{Δ})^{2} + \dots) - (P^{Δ} + (P^{Δ})^{2} + \dots) = I

に対して，両辺に左から $((I - P)^{Δ})^{- 1}$ をかけることで得ることができる．

これらの結果から「ランダムウォークで $Δ$ に到達するまでにある頂点 $y$ に到達する回数の期待値」を成分に持つ行列を $G^{Δ} = [G_{Δ} (x, y)]_{x, y \in V ∖ Δ}$ としたとき，

G^{Δ} = (I^{Δ} - P^{Δ})^{- 1}

また， $r_{Δ} (x)$ を $x$ から SRW をはじめて， $Δ$ に到達する前に $x$ に戻る確率 $r_{Δ} (x) \equiv P_{x} (τ_{x}^{(1)} < ξ^{Δ})$ としたとき，

G_{Δ} (x, x) = k = 0 \sum \infty r_{Δ} (x)^{k} = \frac{1}{1 - r _{Δ} ( x )}

Fact2: Cramer の公式

Cramer の公式は，

(M^{- 1})_{i i} = \frac{det [ M ^{{i}} ]}{det [ M ]}

ここから帰納法を用いたことで，以下の等式が導かれる．

det [M]^{- 1} = det [M^{- 1}] = j = 1 \prod N (M^{Δ_{j}})_{σ (j) σ (j)}^{- 1}

(なお $(σ (1), \dots, σ (N))$ は $(1, \dots, N)$ の permutation. 任意の順番で削除できるため)

Wilson’s Algorithm によって全域木を生成する確率

$Δ \subset V, Δ \neq = \emptyset$ とする．いま $V ∖ Δ$ の連結した distinct element を $x_{1}, \dots, x_{K}$ とし， $x_{j} \sim x_{j + 1} for j = 1, \dots, K$ とする． $x_{K + 1} \in Δ$ とする．頂点 $x_{1}$ からグラフ $Γ$ 上を LERW することを考える．

差集合 $V ∖ Δ$ のすべての頂点に訪問し， $K + 1$ で $Δ$ に到達するようなパスを考える．LERW によって特定の経路を遷移する確率を以下のように表記する．

P^{Δ} (x_{1}, \dots, x_{K}, x_{K + 1})

: = P {L E ({S_{j}, j = 0, \dots, ξ^{Δ}}) = [x_{1}, \dots, x_{K}, x_{K + 1}]}

$[x_{1}, \dots, x_{K}, x_{K + 1}]$ は Loop-erasure によるパスであることから，明らかにループのないパスとなっている． $Δ$ まで LERW するという操作は，Wilson’s Algorithm の branch を追加する操作に対応する．この手続きを分解すると，以下のようになる：

$x_{1}$ から 0 回以上 $x_{1}$ へ loop back ( $x_{1}$ に戻る回数を $m_{1}$ とする)
$x_{1}$ から $x_{2}$ へ $p (x_{1}, x_{2})$ で遷移
$x_{2}$ から 0 回以上 $x_{2}$ へ loop back ( $x_{2}$ に戻る回数を $m_{2}$ とする)
$x_{2}$ から $x_{3}$ へ $p (x_{2}, x_{3})$ で遷移
以下，同様の手続きを $K + 1$ に到達するまで繰り返す

この手順を定式化すると $P^{Δ} (x_{1}, \dots, x_{K}, x_{K + 1})$ は以下のように書ける．

P^{Δ} (x_{1}, \dots, x_{K + 1}) = m_{1}, \dots, m_{K} = 0 \sum \infty r_{Δ} (x_{1})^{m_{1}} p (x_{1}, x_{2}) r_{Δ \cup {x_{1}}} (x_{2})^{m_{2}} p (x_{2}, x_{3}) \dots

\dots r_{Δ \cup {x_{1}, \dots, x_{K - 1}}} (x_{K})^{m_{K}} p (x_{K}, x_{K + 1})

loop back する回数は $m_{j}$ とおき，すべての loop back 回数の組み合わせで確率を計算し，その和をとっている．

表記を簡略化するために $Δ (1) = Δ$ であり $j = 2, \dots, K$ に対して $Δ (j) = Δ \cup {x_{1}, \dots, x_{j - 1}}$ であるとする．すると $r_{Δ \cup {x_{1}}}$ を $r_{Δ (1)}$ と記述できるようになるので，上式は以下のように変形できる．

= j = 1 \prod K [\frac{1}{d e g ( x _{j} )} s u m_{m_{j} = 0}^{\infty} r_{Δ (j)} (x_{j})^{m_{j}}]

= j = 1 \prod K \frac{1}{d e g ( x _{j} )} \frac{1}{1 - r _{Δ (j)} ( x _{j} )}

= j = 1 \prod K \frac{1}{d e g ( x _{j} )} G_{Δ (j)} (x_{j}, x_{j})

先に述べたとおり， $P^{Δ} (x_{1}, \dots, x_{K + 1})$ は branch を追加する操作に他ならない．これを各 branch に対しても同様に計算し，積をとることで全域木の生成確率を求めることができる．したがって，Wilson’s Algorithm が tree $T$ を生成する確率は，

P (T is generated by Wilson’s algorithm)

= l = 1 \prod L P^{Δ^{l}} (x_{l, 1}, \dots, x_{l, k_{l}})

= l = 1 \prod L j = 1 \prod k_{l} - 1 \frac{G _{Δ^{l} (j)} ( x _{l, j} , x _{l, j} )}{de g ( x _{l, j} )}

この等式は Lawler によって証明された結果である[1]。この確率は先に用意した Fact を使い，さらに簡潔にできる。

Determinant を使った式に変形

先に述べた $G^{Δ} = (I^{Δ} - P^{Δ})^{- 1}$ と $L^{Δ} = D^{Δ} (I^{Δ} - P^{Δ})$ を思い出す．線形代数の結果 (Fact2) から，

det [G^{{v}}] = l = 1 \prod L j = 1 \prod k_{l} - 1 G_{Δ^{l} (j)} (x_{l, j}, x_{l, j})

det [D^{{v}}] = l = 1 \prod L j = 1 \prod k_{l} - 1 de g (x_{l, j})

P (T is generated by Wilson’s algorithm)

= \frac{det [ G ^{{v}} ]}{det [ D ^{{v}} ]} = \frac{1}{det [ D ^{{v}} ] det [ I ^{{v}} - P ^{{v}} ]} = det [L^{{v}}]^{- 1}

最初の等式で Lawler の結果と直前の式，次に $G^{Δ}$ の式と行列式の乗法性，最後に $L^{Δ}$ の式と行列式の乗法性を使う．生成される全域木は UST であることから，生成確率は全域木の数の逆数となる．したがって，

P (T is generated by Wilson’s algorithm)

= det [L^{{v}}]^{- 1} = \frac{1}{∣ Ω ∣}

得られた結果は任意の頂点からスタートして成立するため，行列木定理は $v$ に各頂点をあてはめることで即座に得ることができる．

Reference

Random Walk Proof に関わる話は arxiv にアップされた論文 [2] の著者のスライド [3] を参考にして構成している。基本的には原文と同様の式展開をするが，個人的にわかりづらかった部分はいくらか補足や変更を加えている（グリーン関数，LERW を使った説明，記号の整理）。元の論文と異なり，確率分布には $P_{x}$ を使い，遷移確率には $P$ を使い，マルコフ連鎖の状態を $S_{k}$ に統一している．

[1] G. F. Lawler and V. Limic, Random Walk: A Modern Introduction. Cambridge University Press, 2010.
[2] Michael J. Kozdron, Larissa M. Richards and Daniel W. Stroock, Determinants, their applications to Markov processes, and a random walk proof of Kirchhoff’s matrix tree theorem, Preprint, 2013. Available online at arXiv:1306.2059.
[3] A random walk proof of Kirchhoff’s matrix tree theorem