マルコフ連鎖と定常分布

Q: マルコフ連鎖と定常分布とは何ですか？

状態空間 S=\{s_1,\dots,s_n\} 上の確率過程 \{X_t\} が「マルコフ性」を持つとは、次の条件を満たすことをいう。 P(X_{t+1}=s_j \mid X_t=s_i, X_{t-1}, \dots, X_0) = P(X_{t+1}=s_j \mid X_t=s_i) この条件付き確率 p_{ij} = P(X_{t+1}=s_j\mid X_t=s_i) を並べた行列 P=(p_{ij}) を「推移確率行列」と呼び、各行の和は必ず1になる（\sum_j p_{ij}=1）。状態確率を横ベクトル \pi_t で表すと、時間発展は \pi_{t+1} = \pi_t P で与えられる。

Q: マルコフ連鎖と定常分布は社会やプログラミングでどのように使われていますか？

PageRank によるWebページ重要度スコアリング: Webページ集合をマルコフ連鎖の状態とみなし、ページ間のハイパーリンクを推移確率とすることで、ランダムにリンクをたどり続けた場合に「どのページに長く滞在しやすいか」を表す定常分布を計算する。これがPageRankの中核であり、レコメンドエンジンのアイテム間遷移グラフにも同じ手法が応用される。

「今の状態」だけが未来を決める確率過程と、時間が経つと収束する一定の分布

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: マルコフ連鎖とは「次の状態が、現在の状態だけに依存し、過去の履歴には依存しない」確率過程（マルコフ性）のこと
2: 状態間の推移確率を行列にまとめた「推移確率行列」を確率ベクトルに繰り返し掛けていくと、多くの場合、初期状態によらず一定の分布「定常分布」に収束する
3: Googleの PageRank アルゴリズムは、Webページ間のリンク構造をマルコフ連鎖とみなし、その定常分布をページの重要度スコアとして利用している

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

マルコフ連鎖とは「次の状態が、現在の状態だけに依存し、過去の履歴には依存しない」確率過程（マルコフ性）のこと

身につく武器・思考力

状態間の推移確率を行列にまとめた「推移確率行列」を確率ベクトルに繰り返し掛けていくと、多くの場合、初期状態によらず一定の分布「定常分布」に収束する

実社会・ITでの活躍現場

•PageRank によるWebページ重要度スコアリング
•ITシステム・アルゴリズム実装における論理設計
•データ分析やシミュレーションにおける数理モデリング

Layer 1 — 直感・シミュレーター

「晴れ」と「雨」の2状態間の推移確率をスライダーで自由に設定してみよう。初期分布（例：晴れ100%）から「1ステップ進める」ボタンを押すたびに確率ベクトルが更新され、棒グラフが変化する様子を観察できる。何度も押し続けると、推移確率がどんな値でも、やがて特定の一定比率（定常分布）に収束していくことが体感できる。

推移確率行列 P を設定:

晴れ → 晴れ: 0.80（晴れ→雨: 0.20）雨 → 晴れ: 0.40（雨→雨: 0.60）

t = 0

時刻 t = 0 における状態確率分布

\pi_t

☀️ 晴れ

100.0%

🌧️ 雨

0.0%

定常分布（理論値・十分ステップ後に収束する値）:

晴れ: 66.7% / 雨: 33.3%

「1ステップ進める」を繰り返し押すと、初期分布（晴れ100%）によらずこの定常分布に近づいていく様子が確認できる。

直感チェック！ミニクイズ

晴れの日の翌日に晴れる確率が0.8、雨の翌日に晴れる確率が0.4のとき、今日が「雨」だとすると明日「晴れ」になる確率はいくつか？

Layer 2 — 定義・受験・証明

定義

状態空間 $S=\{s_1,\dots,s_n\}$ 上の確率過程 $\{X_t\}$ が「マルコフ性」を持つとは、次の条件を満たすことをいう。

P(X_{t+1}=s_j \mid X_t=s_i, X_{t-1}, \dots, X_0) = P(X_{t+1}=s_j \mid X_t=s_i)

この条件付き確率 $p_{ij} = P(X_{t+1}=s_j\mid X_t=s_i)$ を並べた行列 $P=(p_{ij})$ を「推移確率行列」と呼び、各行の和は必ず1になる（ $\sum_j p_{ij}=1$ ）。状態確率を横ベクトル $\pi_t$ で表すと、時間発展は $\pi_{t+1} = \pi_t P$ で与えられる。

公式・数理モデル

\pi_{t+1} = \pi_t P, \qquad \pi_t = \pi_0 P^t, \qquad \pi^\ast = \pi^\ast P \ (定常分布の条件)

証明・導出

定常分布への収束（既約・非周期・有限状態の場合）：推移行列 $P$ が既約（どの状態からどの状態へも到達可能）かつ非周期的であるとき、ペロン・フロベニウスの定理より $P$ は固有値 $1$ をただ一つ最大の絶対値として持ち、対応する左固有ベクトル $\pi^\ast$ （ $\pi^\ast P = \pi^\ast$ 、 $\sum_i \pi^\ast_i = 1$ ）が一意に存在する。 $\pi_0$ を任意の初期分布とし、 $P$ を固有ベクトルで対角化的に展開すると、 $\pi_0 = \pi^\ast + (\text{他の固有値方向の成分})$ と分解できる。 $t$ ステップ後は $\pi_t = \pi_0 P^t = \pi^\ast + (\text{他の固有値})^t \times (\text{その成分})$ となるが、 $1$ 以外の固有値の絶対値はすべて $1$ 未満であるため、 $t\to\infty$ でその項は $0$ に減衰する。したがって初期分布 $\pi_0$ によらず $\pi_t \to \pi^\ast$ となり、定常分布へ収束することが示される。

押さえておきたいポイント

マルコフ性の本質は「未来は現在にのみ依存し、過去の経路は無関係」という記憶の消失（無記憶性）
定常分布 $\pi^\ast$ は連立方程式 $\pi^\ast P = \pi^\ast$ （固有値1の左固有ベクトル）を解くことでも直接求まる
既約性（すべての状態が互いに到達可能）と非周期性が満たされないと、定常分布に収束しない、または複数存在しうる
PageRankは「ランダムサーファーモデル」＝Webのリンク構造上をランダムに移動し続けるマルコフ連鎖の定常分布をページの重要度として使う

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

PageRank によるWebページ重要度スコアリング

Webページ集合をマルコフ連鎖の状態とみなし、ページ間のハイパーリンクを推移確率とすることで、ランダムにリンクをたどり続けた場合に「どのページに長く滞在しやすいか」を表す定常分布を計算する。これがPageRankの中核であり、レコメンドエンジンのアイテム間遷移グラフにも同じ手法が応用される。

1// 推移確率行列（状態数 n × n）とダンピングファクターによるPageRank
2function pageRank(
3  transitionMatrix: number[][],
4  dampingFactor = 0.85,
5  iterations = 100
6): number[] {
7  const n = transitionMatrix.length;
8  let rank: number[] = new Array(n).fill(1 / n); // 初期分布は一様
9
10  for (let iter = 0; iter < iterations; iter++) {
11    const nextRank = new Array(n).fill((1 - dampingFactor) / n);
12
13    for (let i = 0; i < n; i++) {
14      for (let j = 0; j < n; j++) {
15        // i から j への推移確率 × 現在の i の重要度
16        nextRank[j] += dampingFactor * rank[i] * transitionMatrix[i][j];
17      }
18    }
19    rank = nextRank;
20  }
21  return rank;
22}
23
24// 例: 3ページ A, B, C のリンク構造（行 = 遷移元、列 = 遷移先の確率）
25const transitionMatrix = [
26  [0.0, 0.5, 0.5], // A -> B, C に半々でリンク
27  [0.0, 0.0, 1.0], // B -> C のみリンク
28  [1.0, 0.0, 0.0], // C -> A のみリンク
29];
30
31const ranks = pageRank(transitionMatrix);
32console.log(ranks.map((r) => r.toFixed(4)));
33// 定常分布に近い値が出力される（例: [0.388, 0.215, 0.397] 程度）