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

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

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

この問題は 1905 年にカール・ピアソンが Nature 誌に投稿した短い手紙に端を発する。ピアソンは蚊の移動パターンをモデル化しようとしていた。ほどなくしてレイリー卿が回答を寄せ、これが ランダムウォーク (random walk) という概念の公式な出発点となった。しかし、同じモデルはアインシュタインのブラウン運動の理論（1905 年）にも暗黙のうちに含まれていた。偶然にも同じ年に、物理学と純粋数学の双方からランダムウォークの理論が生まれたのだ。

この素朴な問いの答えは驚くほど深く、確率論・グラフ理論・情報検索にまで繋がっていく。この記事では、1 次元の直線上の話から始め、グラフ上のマルコフ連鎖を経て、Google の 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}$ だ。つまり「平均的にはどこにも行かないが、ばらつきは $\sqrt{n}$ のオーダーで広がる」。100 歩歩いても平均位置は 0 だが、位置の標準偏差は 10 だ。10,000 歩歩いても平均は 0 だが、標準偏差は 100 まで広がる。歩数を 100 倍に増やしても、広がりは 10 倍にしかならない。これが拡散の本質であり、ランダムウォークの基本的な振る舞いだ。

下のデモでは 5 本の独立なランダムウォークを同時に走らせている。個々のパスはまちまちだが、分散の実測値が理論値 $n$ に近づくのを確認してほしい。

1D ランダムウォーク

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}$ は小さいが、無限に足し上げると発散するほどには大きい」のだ。これと対照的に、 $1/n^2$ の級数は収束する。後述する 3 次元ランダムウォークでは原点からの復帰確率が $1/n^{3/2}$ 程度に減衰し、級数が収束するため、帰還が保証されなくなる。

初到達時間の分布

原点に「帰還する」とは分かったが、どのくらい時間がかかるのだろうか？答えは驚くべきことに、初到達時間の期待値は無限大だ。

$n$ ステップ目に初めて原点に戻る確率を $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$

つまり「必ず帰れるが、平均的にはいつ帰れるか分からない」という奇妙な状況だ。これは確率論に特有のパラドックスで、「ほぼ確実に帰還するが期待帰還時間は無限大」となる状態を零再帰 (null recurrent) という。有限グラフ上のランダムウォークでは、この問題は起きず、期待帰還時間は有限になる。これは次章への重要な伏線だ。

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

自然な疑問が湧く。「2 次元、3 次元でも同じか？」

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% の確率で出発点に二度と戻らない。次元が上がると空間が「広すぎて」戻れなくなるのだ。

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

この結果は物理学にも深い影響を持つ。2 次元の格子上の拡散は再帰的なので、1 つの粒子が格子のすべてのサイトを（確率 1 で）訪問する。しかし 3 次元では訪問しないサイトが残る。これは相転移や結晶成長の理論で重要な役割を果たす。

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

直線からグラフへ

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

ここで発想を拡張する。任意のグラフの上でランダムウォークできないだろうか？ ソーシャルネットワーク、路線図、分子の結合構造 — どんなネットワークでも「ノードにいて、隣のノードに移る」という操作は定義できる。

遷移ルール

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

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

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

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

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

遷移確率行列 $P$ を定義しよう。 $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_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) と呼ぶ。グラフ上のランダムウォークは常に可逆だが、一般の有向グラフ上のマルコフ連鎖は可逆とは限らない。これが次章の PageRank で重要になる。

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

定常分布に収束するのは良いが、「どのくらいの速さで収束するのか」も重要だ。この速度は遷移行列の第 2 固有値 $\lambda_2$ で決まる。

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

$\lambda_2$ が 1 に近いほど収束が遅く、0 に近いほど速い。 $\lambda_2$ と 1 の差 $1 - \lambda_2$ をスペクトルギャップ (spectral gap) と呼ぶ。

ミキシングタイム $t_{\text{mix}}$ は、確率分布が定常分布に「十分近づく」までに必要なステップ数で、おおよそ $t_{\text{mix}} \sim 1/(1 - \lambda_2)$ と表される。

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

このミキシングタイムの概念は、MCMC の収束診断やアルゴリズムの解析で中心的な役割を果たす。

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

ランダムウォークの性能をはかる別の指標がある。

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

有名な結果として、 $n$ ノードの連結グラフのカバータイムは $O(n^3)$ 以下であることが知られている（ただし実際にはもっと速いことが多い）。完全グラフのカバータイムは $\Theta(n \log n)$ で、これは有名なクーポンコレクター問題（ $n$ 種類のクーポンをランダムに集めてすべて揃えるまでの期待回数）と同値だ。

第 3 章 — PageRank の発明

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

ウェブ以前に、ランダムウォークの発想は学術論文のランキングに使われていた。Impact Factor は論文の引用回数に基づく単純な指標だが、「質の高い論文からの引用」と「質の低い論文からの引用」を区別しない。

ガブリエル・ピンスキーは 1976 年に、学術雑誌のランキングに引用のネットワーク構造を活用するアイデアを提案した。これは PageRank の直接的な先駆けだ。

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

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

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

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

彼らの核心的な洞察は再帰的だった。「重要なページからリンクされているページは重要だ」。しかし「重要なページ」自体を定義するのに「重要度」が必要だ。鶏と卵の問題に見えるが、これはまさに固有値問題として定式化できる。

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

彼らの発想は、グラフ上のランダムウォークそのものだった。想像上の「ランダムサーファー」がウェブを歩く。

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

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

ジャンプのメカニズムは 2 つの技術的問題を解決する。

ダングリングノード: リンクを 1 本も持たないページ（PDF や画像ページ）に到達するとウォークが止まってしまう。ランダムジャンプがあれば脱出できる
吸収状態: 相互にリンクし合う小さなページ群がウォーカーを閉じ込めてしまう可能性がある。ジャンプにより、遷移行列は原始的 (primitive) になり、すべてのノードを訪問できることが保証される

遷移行列で表現すると、ジャンプ付きの行列 $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} \frac{r_i^{(t)}}{\text{out}(i)}$

初期値を一様分布 $r_i^{(0)} = 1/N$ として、この式を繰り返し適用する。 $M$ が原始行列であるため、ペロン・フロベニウスの定理により固有値 1 に対応する固有ベクトルは一意であり、他の固有値の絶対値は $d$ 以下だ。したがって収束率は幾何的に速く

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

$d = 0.85$ なら、50 回程度の反復で十分な精度に収束する。1998 年当時のウェブ（数億ページ）でも、この単純な反復で実用的な速度でランキングを計算できた。

下のデモでは、6 ページの小さなウェブグラフで PageRank のべき乗法を実行できる。反復ごとにスコアが収束していく様子を確認しよう。

PageRank シミュレーション

ランダムサーファーモデルに基づく PageRank のべき乗法。ノードの大きさがスコアに比例

ページ	PR(n)	収束値	差
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

反復回数: 0 / 40d = 0.85

PageRank の数学的意味

ここまでの章を踏まえると、PageRank の本質が見えてくる。

PageRank は、ダンピング付きランダムウォークの定常分布に他ならない。

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

つまり、前章で学んだ「ランダムウォークの訪問頻度は定常分布に収束する」という原理が、そのまま PageRank のアルゴリズムの正しさを保証しているのだ。

PageRank の限界と後継

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

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

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

モンテカルロ法

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

最も有名な例は円周率の推定だ。単位正方形 $[0,1]^2$ にランダムに点を打って、原点からの距離が 1 以下の点の割合を $p$ とすると、 $\pi \approx 4p$ 。投点数を $N$ とすると、推定の誤差は $O(1/\sqrt{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 のミキシングタイム（定常分布への実質的な収束に必要なステップ数）が小さいほど効率的だ。これはまさに前章のスペクトルギャップの問題であり、ランダムウォーク理論が直接応用される。

グラフクラスタリング

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

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

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

近年のグラフニューラルネットワーク (GNN) にも、ランダムウォークの発想が深く関わっている。

DeepWalk (2014): グラフ上でランダムウォークを行い、得られたノード訪問列を「文」と見なして Word2Vec の SkipGram で学習する。ランダムウォーク列上の共起がノードの類似性を捉える
Node2Vec (2016): DeepWalk を拡張し、BFS 的探索（局所構造を捉える）と DFS 的探索（コミュニティ構造を捉える）のバイアスパラメータ $p, q$ を導入。探索戦略のトレードオフを制御できる
GCN（Graph Convolutional Network）: 実はグラフ上の畳み込みは、ランダムウォーク遷移行列の多項式フィルタ（チェビシェフ多項式近似）と数学的に等価だ。つまり GCN の各層は、ランダムウォーク的な情報の拡散を行っているとも解釈できる

まとめ — 一本の線から世界の構造へ

この記事を振り返ろう。

1 次元ランダムウォーク: 期待値 0、分散 $n$ 、 $\sqrt{n}$ の拡散。1D と 2D では再帰的（確率 1 で帰還）、3D 以上は非再帰的（ポリアの定理）。零再帰という興味深い現象がある
グラフ上のランダムウォーク: マルコフ連鎖として定式化。定常分布 $\pi_i = \deg(i) / 2|E|$ に収束し、詳細釣り合いで証明できる。ミキシングタイムはスペクトルギャップで決まる
PageRank: ダンピング付きランダムウォークの定常分布として、ウェブページの重要度を算出。べき乗法で効率的に計算でき、ペロン・フロベニウスの定理が収束を保証する
広がる応用: モンテカルロ法、MCMC、グラフクラスタリング、推薦システム、GNN

酔っ払いの千鳥足という素朴なモデルが、ウェブ検索エンジンのコアアルゴリズムから最先端のグラフニューラルネットワークまで繋がっている。数直線という最もシンプルな構造の上で発見された再帰性と拡散の性質が、グラフ理論を経由して、現代の情報技術の基盤を支えているのだ。