ランダムウォーク — 酔っ払いの千鳥足から PageRank まで

はじめに — 酔っ払いの帰還問題

街灯の下に酔っ払いがいる。一歩ごとに等確率で左か右に進む。彼は最終的に元の位置に戻ってこられるだろうか？

この問題は 1905 年にカール・ピアソンが Nature 誌に投稿した短い手紙に端を発する。ピアソンは、ランダムな方向へ何度も飛ぶ蚊が最終的にどれだけずれるかをモデル化しようとしていた。ほどなくしてレイリー卿が回答を寄せ、このやり取りによってランダムウォーク (random walk) という用語が広まった。同じ 1905 年には、アインシュタインのブラウン運動の理論でも同じ極限モデルが中心的な役割を果たしており、統計と物理の双方から近いアイデアが現れている。

答えは「戻る」だ。1 次元と 2 次元では確率 1 で出発点に戻るが、3 次元以上では二度と戻らない確率が正になる。第 1 章ではこの違いを、原点にいる確率が減衰する速さから導く。第 2 章では同じ歩き方を任意のグラフに広げ、ウォーカーが各ノードにいる確率が定常分布に落ち着くことを示す。第 3 章では、この定常分布をウェブのリンク構造に当てはめたものが Google の PageRank であることを説明する。

動画で読む4:18合成音声ナレーション・字幕付き

文字起こしを表示

街灯の下の酔っ払いは、左か右へランダムに歩きます。彼はいつか出発点へ戻れるのでしょうか。この素朴な問いから、グラフ上のマルコフ連鎖、そしてPageRankまでたどります。

1次元では、各ステップは確率2分の1で+1、確率2分の1で-1です。nステップ後の位置S_nは、独立なステップX_iの和として書けます。期待値は0ですが、分散はn、標準偏差は√nです。平均は動かず、広がりだけが拡散します。

2nステップ後に原点にいるには、+1と-1が同じ回数だけ必要です。その確率は中心二項係数から計算でき、スターリング近似で約1/√(πn)になります。小さくはなりますが、1/√nを無限に足すと発散します。だから1次元では確率1で無限回戻ります。

ただし、いつ初めて帰るかは別問題です。初到達確率はおおよそ1/n^(3/2)で減り、期待初到達時間は無限大になります。確率1で帰るのに、帰るまでの平均時間は無限大です。これが零再帰です。

ポリアは1921年に、次元で帰還の性質が変わることを示しました。1次元と2次元では再帰的で、確率1で出発点へ戻ります。3次元以上では非再帰的です。3次元の帰還確率は約0.3405で、約66%は二度と戻りません。

数直線をグラフと見れば、1次元ランダムウォークは無限パスグラフ上の歩行です。任意のグラフでも、今いるノードの隣接ノードから一様ランダムに次を選べます。これはマルコフ連鎖で、時刻tの確率ベクトルに遷移行列Pを掛けると、次の時刻の確率ベクトルになります。

有限連結グラフには、π = πPを満たす一意な定常分布があります。無向グラフでは、定常分布はπ_i = deg(i) / 2|E|です。次数が大きいほどよく訪問されます。隣り合う2点の確率の流れが釣り合う、詳細釣り合いが、この式を支えます。

非周期的な連鎖では、分布そのものも定常分布へ近づきます。収束の速さは、絶対値が2番目に大きい固有値で決まり、その絶対値と1との差、スペクトルギャップが大きいほど速くなります。完全グラフは数ステップで混合し、パスグラフはO(n^2)、エクスパンダーはO(log n)です。

この発想は、ウェブ検索のランキングにもつながります。1976年にピンスキーは、引用ネットワークで学術雑誌を評価する考えを提案しました。1998年、ラリー・ペイジとセルゲイ・ブリンは、ウェブを有向グラフとして見ました。重要なページからリンクされるページは重要だ、という再帰的な考えがPageRankです。

PageRankのランダムサーファーは、通常はリンクをたどります。ただし確率1-dで飽きて、ランダムなページへテレポートします。dは通常0.85です。リンクのないダングリングノードでは必ずジャンプします。ジャンプがあるので、吸収状態にも閉じ込められません。

PageRankベクトルは、ダンピング付き遷移行列Mの定常分布です。一様分布から始めて、べき乗法でスコアを何度も更新します。Mが原始行列なので、ペロン・フロベニウスの定理が一意性と収束を保証します。d = 0.85なら、誤差の上限は反復ごとに0.85倍され、50回では約2.96×10^-4倍になります。

ランダムウォークは、モンテカルロ法、MCMC、クラスタリング、推薦、GNNにも広がります。記事では、1次元、グラフ、PageRankのデモを動かしながら、この流れを確かめられます。

第 1 章 — 1 次元ランダムウォーク

最もシンプルなモデル

数直線上の原点にいるとする。毎ステップ、確率 $1/2$ で $+1$ に、確率 $1/2$ で $-1$ に動く。 $n$ ステップ後の位置を $S_n$ とすると

$S_n = X_1 + X_2 + \cdots + X_n$

ここで各 $X_i$ は独立に $+1$ または $-1$ を取る確率変数だ。 $X_i$ のことをステップと呼ぶ。

このモデルは、極限を取るとブラウン運動（ウィーナー過程）に収束する。ステップ幅を $1/\sqrt{n}$ に縮めてステップ数を無限大にすると、連続な確率過程が得られる。その意味で、1 次元ランダムウォークは「離散時間のブラウン運動」と見なせる。金融工学のブラック・ショールズモデルも、この連続版の上に構築されている。

期待値と分散

対称性から、期待値は 0 になる。各ステップの期待値が $E[X_i] = (1/2)(+1) + (1/2)(-1) = 0$ なので

$E[S_n] = \sum_{i=1}^{n} E[X_i] = 0$

分散はどうか。各ステップの分散は $\mathrm{Var}(X_i) = E[X_i^2] - (E[X_i])^2 = 1 - 0 = 1$ だ。 $X_i$ たちが独立なので分散は加法的になる。

$\mathrm{Var}(S_n) = \sum_{i=1}^{n} \mathrm{Var}(X_i) = n$

標準偏差は $\sqrt{n}$ だ。平均位置はどれだけ歩いても 0 のままだが、ばらつきは $\sqrt{n}$ のオーダーで広がる。100 歩後の位置の標準偏差は 10、10,000 歩後は 100 で、歩数を 100 倍にしても広がりは 10 倍にしかならない。広がりが歩数の平方根に比例するこの振る舞いを拡散と呼ぶ。

下のデモでは 5 本の独立なランダムウォークを同時に走らせている。個々のパスはまちまちで、5 本から求めた分散は、理論値 $n$ の前後で揺れながら歩数とともに大きくなる。

1 次元ランダムウォーク

5 本の独立したランダムウォークと、その平均位置（太い破線）。期待値は常に 0 だが、分散は時間とともに拡大する

ステップ: 0平均位置: 0.0分散: 0.0(理論値: 0)

再帰性 — 原点への帰還

1 次元ランダムウォークは確率 1 で原点に戻る。

これを示すために、まず $2n$ ステップ後に原点にいる確率を計算する。 $S_{2n} = 0$ となるには、 $+1$ が $n$ 回、 $-1$ が $n$ 回出る必要がある。 $2n$ 回の試行から $n$ 回を選ぶ組み合わせは $\binom{2n}{n}$ 通りで、各列の確率は $(1/2)^{2n}$ なので

$P(S_{2n} = 0) = \binom{2n}{n} \left(\frac{1}{2}\right)^{2n}$

スターリングの近似 $n! \approx \sqrt{2\pi n} \, (n/e)^n$ を使うと

$\binom{2n}{n} = \frac{(2n)!}{(n!)^2} \approx \frac{4^n}{\sqrt{\pi n}}$

したがって

$P(S_{2n} = 0) \approx \frac{4^n}{\sqrt{\pi n}} \cdot \frac{1}{4^n} = \frac{1}{\sqrt{\pi n}}$

この確率は $n$ とともに 0 に減衰するが、その減衰は遅い。原点に戻る回数（再帰回数）の期待値を求めると、次のようになる。

$E[\text{再帰回数}] = \sum_{n=1}^{\infty} P(S_{2n} = 0) \approx \sum_{n=1}^{\infty} \frac{1}{\sqrt{\pi n}} = \infty$

$1/\sqrt{n}$ の級数は発散する（積分 $\int_1^\infty x^{-1/2}\,dx = \infty$ と比較すれば分かる）。再帰回数の期待値が無限大なので、ウォーカーは確率 1 で無限回原点に戻る。この性質を再帰的 (recurrent) という。

$1/\sqrt{n}$ は小さいが、無限に足し上げると発散する程度には大きい。後述する 3 次元ランダムウォークでは、原点にいる確率が $1/n^{3/2}$ 程度で減衰し、その級数が収束するため、帰還が保証されなくなる。

初到達時間の分布

ウォーカーは必ず原点に戻るが、戻るまでの時間（初到達時間）の期待値は無限大になる。

$2n$ ステップ目に初めて原点に戻る確率を $f_{2n}$ とすると

$f_{2n} = \frac{1}{2n - 1} P(S_{2n} = 0) \approx \frac{1}{2n - 1} \cdot \frac{1}{\sqrt{\pi n}} \sim \frac{1}{n^{3/2}}$

初到達時間の期待値は

$E[\text{初到達時間}] = \sum_{n=1}^{\infty} 2n \cdot f_{2n} \sim \sum_{n=1}^{\infty} \frac{1}{\sqrt{n}} = \infty$

確率 1 で帰還するのに、帰還までの時間の期待値は無限大になる。この性質を零再帰 (null recurrent) という。有限の連結グラフ上のランダムウォークでは期待帰還時間は有限で、第 2 章の定常分布 $\pi_i$ を使うと、ノード $i$ への期待帰還時間は $1/\pi_i$ になる。

ポリアの定理 — 次元と再帰性

再帰するかどうかは次元によって変わる。

2 次元ランダムウォークでは、各ステップで上下左右の 4 方向に等確率で動く。 $2n$ ステップ後に原点にいる確率は

$P(S_{2n} = \mathbf{0}) \approx \frac{1}{\pi n}$

再帰回数の期待値は $\sum 1/(\pi n)$ で、調和級数と同じく発散する。したがって 2 次元でも再帰的だ。

3 次元ではどうか。各ステップで 6 方向（前後左右上下）に等確率で動く。 $2n$ ステップ後に原点にいる確率は

$P(S_{2n} = \mathbf{0}) \approx 2\left(\frac{3}{4\pi n}\right)^{3/2}$

再帰回数の期待値は $\sum n^{-3/2}$ に比例し、これは収束する。原点に帰還する回数の期待値が有限なので、正の確率で二度と帰らない。ジョージ・ポリアは 1921 年に、次元ごとの結果を次のようにまとめて証明した。

1 次元: 再帰的（確率 1 で帰還する）
2 次元: 再帰的（確率 1 で帰還する）
3 次元以上: 非再帰的（正の確率で二度と帰らない）

3 次元での帰還確率はワトソンの三重積分として知られる値から計算でき、約 0.3405 だ。3 次元のランダムウォーカーは、約 66% の確率で出発点に二度と戻らない。次元が上がると $n$ ステップ後の位置が散らばる範囲が広がり、原点にいる確率が $n^{-d/2}$ （ $d$ は次元）のように速く減衰するためだ。

角谷静夫はポリアの定理をこう表現した。「酔っ払いは必ず家に帰れる。しかし酔った鳥は永遠に迷子になるかもしれない。」

この違いは格子上の拡散にも現れる。2 次元格子では 1 つの粒子が確率 1 ですべてのサイトを訪問するが、3 次元では訪問しないサイトが残る。

第 2 章 — グラフ上のランダムウォーク

直線からグラフへ

数直線をグラフとして見ると、各整数をノードとし、隣り合う整数間にエッジを張った無限パスグラフになる。1 次元ランダムウォークは、このパスグラフ上のランダムウォークだ。

「ノードにいて、隣のノードに移る」という操作は、ソーシャルネットワーク、路線図、分子の結合構造など、どんなグラフでも定義できる。そこで、任意のグラフの上で同じ歩き方を考える。

遷移ルール

現在いるノードの隣接ノードの中から、一様ランダムに次のノードを選ぶ。ノード $i$ にいるとき、次にノード $j$ に移る確率は

$P(i \to j) = \frac{1}{\deg(i)} \quad \text{($j$ が $i$ の隣接ノードのとき)}$

次数の大きいノードからは各隣接ノードへの遷移確率が小さく、次数の小さいノードからは各隣接ノードへの遷移確率が大きい。酔っ払いが大きな交差点にいると、各道への確率が薄まるイメージだ。

マルコフ連鎖としての定式化

この過程はマルコフ連鎖だ。次の状態は現在の状態のみに依存し、過去の履歴には依存しない（マルコフ性、もしくは「記憶なし性」）。

遷移確率行列 $P$ を、次の成分を持つ $|V| \times |V|$ 行列として定義する。

$P_{ij} = \begin{cases} 1/\deg(i) & \text{$i$ と $j$ が隣接のとき} \\ 0 & \text{それ以外} \end{cases}$

確率ベクトル $\mathbf{p}^{(t)}$ （時刻 $t$ に各ノードにいる確率を並べた行ベクトル）の時間発展は

$\mathbf{p}^{(t+1)} = \mathbf{p}^{(t)} P$

と書ける。 $t$ ステップ後の確率分布は初期分布に $P^t$ を掛けるだけだ。

定常分布

有限連結グラフ上のランダムウォークには、一意な定常分布 $\pi$ が存在する。 $\pi$ は $\pi = \pi P$ を満たす確率分布（すべての成分が非負で合計 1）で、遷移行列の固有値 1 に対応する左固有ベクトルにあたる。任意の初期分布から時刻ごとの分布そのものが $\pi$ に収束するには、さらに非周期性が必要になる。自己ループのない単純な無向グラフでは、二部グラフでなければ非周期的だ。連結な二部グラフでも定常分布は存在し、長期的な訪問頻度は収束するが、時刻ごとの確率分布は偶数ステップと奇数ステップで振動する。

有限連結無向グラフでは、定常分布は閉じた式で表される。

$\pi_i = \frac{\deg(i)}{2|E|}$

ここで $|E|$ はエッジの本数だ。分母の $2|E|$ は全ノードの次数の合計に等しい（各エッジは両端のノードの次数に 1 ずつ寄与する、ハンドシェーキング補題）。

次数の大きいノード（多くのエッジを持つノード）ほどよく訪問される。入り口の多いノードには、多くの方向から歩いてくるからだ。

例えば、5 本のエッジを持つグラフでノード $A$ の次数が 3 なら、 $\pi_A = 3/10 = 0.3$ だ。ウォーカーは長期的に時間の 30% をノード $A$ で過ごす。

下のデモでは、6 ノードのグラフ上でランダムウォーカーを歩かせている。訪問頻度は、理論的な定常分布 $\pi_i = \deg(i) / 2|E|$ に収束していく。

グラフ上のランダムウォーク → 定常分布

ランダムウォーカーの訪問頻度が定常分布 π_i = deg(i) / 2|E| に収束する様子。ノード下の数字は訪問回数

ノード	deg	π	実測	誤差
A	2	0.111	—	—
B	4	0.222	—	—
C	4	0.222	—	—
D	2	0.111	—	—
E	4	0.222	—	—
F	2	0.111	—	—

合計ステップ: 0

なぜ定常分布が存在するのか — 詳細釣り合い

$\pi$ が $\pi = \pi P$ を満たすことは、詳細釣り合い条件 (detailed balance) を使うと簡単に示せる。

$\pi_i P_{ij} = \pi_j P_{ji}$

この条件は、「 $i$ から $j$ へ流れる確率の量と、 $j$ から $i$ へ流れる確率の量が等しい」ことを意味する。すべてのペアで流入と流出が釣り合っていれば、どのノードの確率も変化しない。

$\pi_i = \deg(i) / 2|E|$ と $P_{ij} = 1 / \deg(i)$ を代入すると、隣接するペア $(i, j)$ について

$\frac{\deg(i)}{2|E|} \cdot \frac{1}{\deg(i)} = \frac{1}{2|E|} = \frac{\deg(j)}{2|E|} \cdot \frac{1}{\deg(j)}$

左右が等しいので詳細釣り合いが成り立つ。詳細釣り合いを満たす分布は必ず定常分布なので（ $\pi P$ の $j$ 成分を各 $i$ について足すと $\pi_j$ に戻ることが確認できる）、証明は完了する。

詳細釣り合いを満たすマルコフ連鎖を可逆 (reversible) と呼ぶ。有限無向グラフ上のランダムウォークは、この定常分布に関して（各連結成分内で）可逆だが、一般の有向グラフ上のマルコフ連鎖は可逆とは限らない。第 3 章の PageRank が扱うウェブは有向グラフなので、 $\pi_i = \deg(i)/2|E|$ のように次数だけで決まる閉じた式は一般に使えず、定常分布を反復計算で求める。

収束速度 — ミキシングタイム

非周期的な連鎖は定常分布に収束するが、その速さも問題になる。可逆連鎖では、収束の速さは、遷移行列の固有値の絶対値のうち 2 番目に大きい値 $\lambda_* = \max_{i \ge 2} |\lambda_i|$ で決まる。

$\|\mathbf{p}^{(t)} - \pi\|_{\text{TV}} \leq C \cdot \lambda_*^t$

$\lambda_*$ が 1 に近いほど収束が遅く、0 に近いほど速い。ミキシングに効くスペクトルギャップ (spectral gap) は $1 - \lambda_*$ だ（lazy な連鎖やスペクトルが非負の連鎖では、これは $1 - \lambda_2$ と一致する）。

ミキシングタイム $t_{\text{mix}}$ は、確率分布が定常分布に「十分近づく」までに必要なステップ数だ。目標精度や最小定常確率に依存する対数因子を除けば、おおよそ $1/(1 - \lambda_*)$ のオーダーになる。周期性を避けるため、各ステップで確率 1/2 でその場に留まる lazy 版のランダムウォークで比べると、グラフの形によって次のように差が出る。

完全グラフ（ $K_n$ ）: スペクトルギャップが大きく、数ステップで混合する
パスグラフ（一直線のグラフ）: スペクトルギャップが小さく、 $O(n^2)$ ステップ必要
エクスパンダーグラフ: スペクトルギャップが定数のため、 $O(\log n)$ ステップで混合する

第 4 章で扱う MCMC でも、ミキシングタイムが収束の速さを左右する。

ヒッティングタイムとカバータイム

ランダムウォークがグラフをどれだけ速く探索するかは、次の 2 つの指標でも測れる。

ヒッティングタイム $h(u, v)$ : ノード $u$ から出発してノード $v$ に初めて到達するまでの期待ステップ数
カバータイム $C(G)$ : あるノードから出発してグラフのすべてのノードを少なくとも 1 度訪れるまでの期待ステップ数

$n$ ノードの連結グラフのカバータイムは $O(n^3)$ 以下であることが知られている。これは最悪の場合の上界で、多くのグラフではもっと速い。完全グラフのカバータイムは $\Theta(n \log n)$ で、クーポンコレクター問題（ $n$ 種類のクーポンをランダムに集めてすべて揃えるまでの期待回数）と同じ構造をしている。

第 3 章 — PageRank の発明

学術論文の引用ネットワークから

ウェブ以前にも、引用関係から学術雑誌を評価する研究があった。Impact Factor は被引用回数に基づく単純な指標で、「質の高い論文からの引用」と「質の低い論文からの引用」を区別しない。

ガブリエル・ピンスキーとフランシス・ナリンは 1976 年に、引用のネットワーク構造を使って学術雑誌をランキングする方法を提案した。引用元の雑誌の影響力で引用に重みを付けるこの方法は、定義が PageRank とよく似ており、その先駆けにあたる。

ウェブという巨大な有向グラフ

スタンフォード大学の大学院生だった Larry Page と Sergey Brin は、ウェブのリンク構造に注目し、1998 年に PageRank を発表した。当時のウェブ検索エンジン（AltaVista、Lycos など）はキーワード頻度に基づくランキングを使っていたため、スパムに弱く、検索結果の質に問題があった。

各ウェブページはノード、ハイパーリンクは有向エッジだ。彼らの問いはこうだった。

「あるページの"重要度"をリンク構造だけから計算できないだろうか？」

彼らは重要度を再帰的に定義した。「重要なページからリンクされているページは重要だ」。重要度を定義するのに重要度を使うので循環しているように見えるが、この定義は固有ベクトルを求める問題として定式化できる。

ランダムサーファーモデル

この重要度は、グラフ上のランダムウォークで表せる。想像上の「ランダムサーファー」が次のようにウェブを歩く。

現在のページのリンクの中から一様ランダムに 1 つ選んでクリックする
ただし、確率 $1 - d$ でサーフィンに飽きてランダムなページにジャンプする

ダンピングファクター $d$ は通常 $0.85$ に設定される。この場合、85% の確率でリンクをたどり、15% の確率でランダムなページにジャンプする。

ジャンプは 2 つの技術的問題を解決する。

ダングリングノード: リンクを 1 本も持たないページ（PDF や画像ページ）に到達するとウォークが止まってしまう。実装上はまず、その行をテレポーテーション分布に置き換える
吸収状態: 相互にリンクし合う小さなページ群がウォーカーを閉じ込めてしまう可能性がある。正の確率でテレポートすると、最終的な遷移行列は全要素が正になる。したがって原始的 (primitive) で、どのノードからでもすべてのノードを訪問できる

ダングリング行を補正して $P$ を行確率行列にしたうえで、ジャンプ付きの遷移行列 $M$ は次のように書ける。

$M = d \cdot P + (1 - d) \cdot \frac{\mathbf{1}\mathbf{1}^T}{N}$

ここで $P$ はリンクに基づく遷移行列、 $\mathbf{1}\mathbf{1}^T/N$ は任意のノードから全ノードに均等に遷移する行列（テレポーテーション行列）だ。

べき乗法

PageRank ベクトル $\mathbf{r}$ は $\pi M = \pi$ を満たす定常分布で、次の反復（べき乗法、power iteration）で計算する。

$r_j^{(t+1)} = \frac{1-d}{N} + d \sum_{i \to j,\,\text{out}(i)>0} \frac{r_i^{(t)}}{\text{out}(i)} + \frac{d}{N}\sum_{i:\,\text{out}(i)=0} r_i^{(t)}$

初期値を一様分布 $r_i^{(0)} = 1/N$ として、この式を繰り返し適用する。 $M$ は原始行列なので、ペロン・フロベニウスの定理により固有値 1 に対応する固有ベクトルは一意に定まる。他の固有値の絶対値が $d$ 以下になることも、Haveliwala と Kamvar（2003）が示している。そのため誤差は $d^t$ に比例して幾何級数的に小さくなる。

$\|\mathbf{r}^{(t)} - \pi\| \leq C \cdot d^t$

$d = 0.85$ なら、50 回の反復でダンピング由来の係数は $0.85^{50} \approx 2.96 \times 10^{-4}$ まで小さくなる。実際に何回で止めるかは、許容誤差やグラフ構造で決まる。1998 年の論文で扱われた数千万ページ規模のウェブでも、この単純な反復で実用的な速度でランキングを計算できた。

下のデモでは、6 ページの小さなウェブグラフで PageRank のべき乗法を実行できる。反復を重ねるごとに、スコアが一定の値に落ち着いていく。

PageRank シミュレーション

ランダムサーファーモデルの PageRank をべき乗法で計算する。ノードが大きいほどスコアが高い

ページ	PR(t)	収束値	誤差
A	0.1667	0.2186	0.0519
B	0.1667	0.1569	0.0098
C	0.1667	0.2470	0.0804
D	0.1667	0.0917	0.0750
E	0.1667	0.1339	0.0327
F	0.1667	0.1519	0.0147

反復回数 t: 0 / 40d = 0.85

PageRank の数学的意味

PageRank は、ダンピング付きランダムウォークの定常分布だ。

$d = 1$ （ジャンプなし）なら、有向グラフ上の純粋なランダムウォークになる。ダングリングノードや非連結成分があると、定常分布が一意に定まらない
$d < 1$ のジャンプを入れると、遷移行列のすべての要素が正になる。ペロン・フロベニウスの定理により、固有値 1 に対する左固有ベクトルが一意に存在し、任意の初期分布から収束する

第 2 章の「ランダムウォークの訪問頻度は定常分布に収束する」という性質が、PageRank の計算が一意な答えに収束することを保証している。

PageRank の限界と影響

PageRank は初期の Google 検索のランキングの中核だったが、現代のウェブ検索では、リンク構造に加えて数百の要素（テキストの関連性、ユーザー行動、ページの品質指標など）が組み合わされている。また PageRank はリンクファーム（相互リンクを大量に生成してスコアを操作する手法）に対して脆弱だ。

それでも、ランダムウォークの定常分布を使ってネットワーク内の重要度を計算するという PageRank の考え方は、ソーシャルネットワーク分析、バイオインフォマティクスの遺伝子ネットワーク解析、金融ネットワークのシステミックリスク評価など、幅広い分野で今も使われている。

第 4 章 — ランダムウォークの応用の広がり

モンテカルロ法

乱数を使って数値計算する手法群をモンテカルロ法と呼ぶ。名前はカジノの街モンテカルロに由来する。フォン・ノイマンとスタニスワフ・ウラムが 1940 年代のマンハッタン計画で中性子の拡散シミュレーションに使ったのが先駆けだ。

最も有名な例は円周率の推定だ。単位正方形 $[0,1]^2$ にランダムに点を打ち、原点からの距離が 1 以下の点の割合を $p$ とすると、 $\pi \approx 4p$ となる。投点数を $N$ とすると、推定の誤差は $O(1/\sqrt{N})$ で、この収束の速さは次元に依存しない。シンプソン則などの従来の数値積分法は次元が上がると精度が急速に悪化する（次元の呪い）ので、高次元の積分ではモンテカルロ法が有利になる。

MCMC（マルコフ連鎖モンテカルロ法）

ここまでのモンテカルロ法は、一様分布からサンプリングできることを前提としていた。しかし現実の問題では、事後分布や統計力学のボルツマン分布のような複雑な確率分布からサンプリングしたい場面が多い。

MCMC は、目標の確率分布を定常分布とするマルコフ連鎖を構成し、ランダムウォークでサンプルを生成する手法で、第 2 章の理論がそのまま適用される。

Metropolis-Hastings 法 (1953/1970): 提案分布 $q(x'|x)$ から候補 $x'$ を生成し、受理確率 $\alpha = \min(1, \frac{\pi(x') q(x|x')}{\pi(x) q(x'|x)})$ で受理/棄却する。受理確率をこの形にすると詳細釣り合い条件が成り立ち、 $\pi$ が定常分布になる。目標分布 $\pi$ の正規化定数を知らなくても使えるので、ベイズ統計で事後分布からのサンプリングに広く使われる
ギブスサンプリング (1984): 多次元分布の各変数を、他の変数を固定した条件付き分布から順番にサンプリングする。Metropolis-Hastings 法の特殊ケースと見なせる。画像処理（マルコフ確率場）や潜在変数モデル（LDA トピックモデルなど）で標準的な手法

MCMC は、ミキシングタイム（定常分布に実質的に収束するまでのステップ数）が小さいほど効率的だ。ミキシングタイムは第 2 章で見たスペクトルギャップで決まるので、ランダムウォークの理論がそのまま効率の分析に使える。

グラフクラスタリング

ランダムウォーカーは同じコミュニティー内に長く留まり、コミュニティー間の橋渡しエッジを渡りにくい。この性質を利用すると、グラフのコミュニティー構造を検出できる。

Markov Clustering (MCL): 遷移行列の拡張 (expansion; $P^2$ を計算) と膨張 (inflation; 各要素を $r$ 乗して列を正規化) を交互に繰り返す。拡張はランダムウォークの 2 ステップに対応し、クラスター間のフローを生み出す。膨張は強いフローをさらに強め、弱いフローを消す。これを繰り返すと、クラスター構造が浮かび上がる。タンパク質の相互作用ネットワークの解析で広く使われている
Personalized PageRank: 通常の PageRank は全ノードに均等にジャンプするが、Personalized PageRank はテレポーテーション先を特定のノード $v$ に固定し、確率 $1-d$ で $v$ に戻る。その結果、 $v$ から見た「近さ」のスコアが各ノードに割り当てられる。Twitter のユーザー推薦サービス Who to Follow は、Personalized PageRank に似たランダムウォークでユーザーごとに近いユーザーの集合（circle of trust）を求め、推薦の土台にしていた（Gupta ら, WWW 2013）

グラフニューラルネットワークとの接点

グラフニューラルネットワーク (GNN) とその周辺のグラフ表現学習でも、ランダムウォークの発想が使われている。

DeepWalk (2014): グラフ上でランダムウォークを行い、得られたノード訪問列を「文」と見なして Word2Vec の SkipGram で学習する。ランダムウォーク列上の共起がノードの類似性を捉える
Node2Vec (2016): DeepWalk を拡張し、BFS 的探索（局所構造を捉える）と DFS 的探索（コミュニティー構造を捉える）の比重を決めるバイアスパラメーター $p, q$ を導入した
GCN（Graph Convolutional Network）: スペクトルグラフ畳み込みは、チェビシェフ多項式などの多項式フィルターで近似できる。一般的な一次の GCN 層は自己ループ付きの対称正規化隣接行列を使う。これはランダムウォークの遷移行列そのものではないが、近傍の情報をランダムウォークのように拡散する操作と見なせる

まとめ — 数直線から PageRank へ

1 次元ランダムウォーク: 期待値 0、分散 $n$ で、広がりは $\sqrt{n}$ に比例する。1 次元と 2 次元では再帰的（確率 1 で帰還）、3 次元以上では非再帰的（ポリアの定理）。1 次元では、必ず帰還するのに期待帰還時間が無限大になる（零再帰）
グラフ上のランダムウォーク: マルコフ連鎖として定式化できる。有限連結無向グラフでは、定常分布は $\pi_i = \deg(i) / 2|E|$ で、詳細釣り合いから導ける。収束の速さ（ミキシングタイム）はスペクトルギャップで決まる
PageRank: ダンピング付きランダムウォークの定常分布として、ウェブページの重要度を求める。べき乗法で計算でき、ペロン・フロベニウスの定理が一意な解への収束を保証する
応用: モンテカルロ法、MCMC、グラフクラスタリング、推薦システム、GNN

数直線上で見た再帰性と拡散は、グラフ上では定常分布と収束速度の問題になる。PageRank や MCMC は、この 2 つの性質をそのまま計算に使っている。