マルコフ連鎖
Markov Chain ・ まるこふれんさ
次の状態が現在だけで決まる確率過程。時間発展するランダムさの基本モデル
✦ 30秒で試す — 航海晴れから始めても雨から始めても、いずれ同じ割合に落ち着く晴れの日の割合は、両者でどうなる？予想してみる概要
マルコフ連鎖は、時間とともに状態が確率的に移り変わっていく仕組み（確率過程）のうち、「次にどの状態へ移るかが現在の状態だけで決まり、それ以前の履歴には依存しない」という性質を持つものです。この性質をマルコフ性と呼びます。たとえば「今日晴れなら明日も晴れる確率は0.8、今日雨なら明日晴れる確率は0.4」という天気のモデルは、一昨日以前の天気を一切参照しないマルコフ連鎖です。
サイコロを繰り返し振るような、各回が独立な試行の列とは違い、マルコフ連鎖では「今の状態」が「次」に影響します。かといって全履歴を引きずるわけでもない。この「直前だけを覚えている」中間的な設定が絶妙で、天気、顧客の継続と解約、Webページ間の回遊、文章中の単語のつながり、待ち行列の長さといった現象を、扱える複雑さのままモデル化できます。
そしてマルコフ連鎖には、長く走らせるとどこから始めても同じ割合に落ち着くという著しい性質があります。Googleの初期の検索順位を支えたPageRankはこの「落ち着き先」を計算したものですし、ベイズ統計の計算を実用化したマルコフ連鎖モンテカルロ法は、その落ち着き先を「狙った分布」になるよう設計して使う技術です。
なぜ生まれたか
19世紀までの確率論の主要な成果——大数の法則や中心極限定理——は、試行どうしが独立であることを前提に組み立てられていました。しかし現実の系列データの多くは独立ではありません。今日の天気は昨日の影響を受け、文章の次の文字は直前の文字に依存します。「依存があるなら確率論の法則は成り立たないのではないか」という疑問に、当時の理論は答えを持っていませんでした。実際、ロシアの数学者ネクラーソフは「大数の法則が成り立つには独立性が必要だ」と主張していました。
これに反論したのがアンドレイ・マルコフです。1906年、彼は「依存はあるが、依存の仕方が単純な（直前だけに依存する）」試行の列を定式化し、そのような列でも大数の法則が成り立つことを証明しました。独立性は法則の必須条件ではなかったのです。1913年には理論をプーシキンの韻文『エフゲニー・オネーギン』の2万文字に適用し、母音・子音の並びを2状態の連鎖として数えてみせました。これは系列データの統計モデリングの出発点であり、のちの待ち行列理論、情報理論、そして音声認識や言語モデルにつながる系譜の源流になりました。
詳細
状態・遷移確率・遷移行列
マルコフ連鎖は「状態の集合」と「遷移確率」で定義されます。遷移確率は条件付き確率そのもので、「現在の状態がAであるという条件のもとで、次に状態Bへ移る確率」を各ペアについて与えたものです。各時点の状態は確率変数であり、その列がマルコフ性という規則で連結されています。
遷移確率を「行 = いまの状態、列 = 次の状態」の表に並べたものが遷移行列です。上の例なら1行目が（晴→晴 0.8, 晴→雨 0.2）、2行目が（雨→晴 0.4, 雨→雨 0.6）で、各行の合計は必ず1になります。遷移行列の便利さは、行列の掛け算がそのまま時間の前進に対応することです。「今日の状態の確率分布」を表す横ベクトルに遷移行列を1回掛ければ明日の分布、2回掛ければ明後日の分布が得られます。今日確実に晴なら (1, 0) → 明日 (0.8, 0.2) → 明後日 (0.72, 0.28) → … と、n 日後の予測が行列の n 乗という機械的な計算に落ちます。
定常分布 — 長く走らせるとどこに落ち着くか
この計算を続けると、晴の確率は 0.8 → 0.72 → 0.688 → 0.675 → … と縮みながら、0.667 に近づいて止まります。雨から始めても 0.4 → 0.56 → 0.624 → … と下から同じ値に近づきます。遷移させても変わらなくなったこの分布が定常分布です。止まる理由は「流れ」の釣り合いで考えると分かります。晴から雨へ流れ出す量（晴の割合 × 0.2）と、雨から晴へ流れ込む量（雨の割合 × 0.4）が等しくなると、晴の割合はもう動きません。晴 : 雨 = 0.4 : 0.2 = 2 : 1、つまり晴 2/3 です。
下の部品は3状態（晴・曇・雨）の連鎖です。「1000人の分布」で全員を1つの天気に置いて1日ずつ進めると、人の流れが矢印に沿って分かれ、数日で晴 39%・曇 36%・雨 25%（正確には 24/61, 22/61, 15/61）に落ち着きます。スタートを変えても行き着く先は同じです。
1000人全員が「晴」にいます。「1日進める」を押すと、全員が矢印の確率どおりに分かれて移ります。光の量（人の割合）がどこに落ち着くか見てください。
矢印の太さ = 遷移確率（その天気の翌日にどこへ移るか）。破線 = 定常分布
初期状態の影響が消えて同じ分布に落ち着くことは、どの状態からもほかの状態へいつか到達でき（既約性）、決まった周期で行き来するだけの構造に閉じ込められていない（非周期性）有限の連鎖で保証されます。どちらかが崩れると話が変わります。たとえば「晴の翌日は必ず雨、雨の翌日は必ず晴」という連鎖は、晴から始めれば偶数日は必ず晴で、分布はいつまでも交互に振動して収束しません。抜け出せない状態（解約した顧客のような「吸収状態」）がある連鎖では、長期的には全員がそこに溜まります。
エルゴード性 — 1人の長い旅と大勢の1日
定常分布にはもう1つの顔があります。部品の「1人の旅」で1人を長く歩かせると、各天気に滞在した日数の割合が、やはり定常分布に近づいていきます。これがエルゴード定理で、マルコフ連鎖版の大数の法則です。「大勢を1日だけ見たときの割合」と「1人を長い期間追ったときの時間の割合」が一致する——マルコフが1906年に示したかったのは、まさにこの「独立でなくても平均は落ち着く」ことでした。
ただし1人の旅の収束は、大勢の分布の収束よりずっと遅く、揺れも大きくなります。連続する日は独立ではなく、晴が続くと滞在割合がしばらく晴に偏るからです。部品で「天気が長続きする」を選ぶと、大勢の分布が定常分布に着くまでの日数（混合時間）も、1人の割合の揺れも目に見えて大きくなります。
PageRankはこの解釈を使っています。「リンクをランダムにたどり続けるユーザーが、長期的に各ページに滞在する割合」を定常分布として求め、ページの重要度としました。行き止まりのページや閉じたリンクの輪があると既約性が崩れるため、「一定の確率でランダムなページへ飛ぶ」という操作を加えて、どこからでもどこへでも行ける連鎖に直しています。
応用と拡張
実務では、顧客が「無料会員・有料会員・解約」の間を月ごとに遷移するモデルからLTV（顧客生涯価値）を見積もる、機械が「正常・劣化・故障」を遷移する信頼性モデルで保守計画を立てる、といった使い方が典型です。状態が直接観測できず、状態から確率的に出る信号だけが見える設定に拡張したものが隠れマルコフモデルで、音声認識や遺伝子配列解析の土台になりました。「行動の選択」を加えたマルコフ決定過程は、強化学習の標準的な問題設定です。
統計学における最大の応用がマルコフ連鎖モンテカルロ法です。これは発想の逆転で、ふつうは「与えられた連鎖の定常分布を求める」のに対し、MCMCでは「狙った分布（たとえばベイズ推論の事後分布）が定常分布になるような連鎖を設計」し、それを長く走らせます。エルゴード定理により、1本の連鎖が訪れた点の割合は狙った分布に近づくので、その点をモンテカルロ法の標本として使えるのです。最初のうちの初期値の影響が残る部分を捨てる（burn-in）、連続する標本が似ているぶん情報が少ないことを割り引く、といったMCMCの作法は、どれもこの節で見た「収束には時間がかかる」「隣どうしは独立でない」という性質から来ています。
落とし穴 — マルコフ性は仮定である
注意したいのは、マルコフ性はあくまでモデルの仮定だということです。現実には「直前より前」が効く現象も多く、自然な文章は直前の1単語だけでは決まりませんし、顧客の解約は直近の1か月だけでなく利用歴全体に左右されます。その場合は、直近 k 個の状態をまとめて1つの状態とみなす高次のマルコフ連鎖で対応できますが、状態数が k 乗で増えて推定に必要なデータが爆発するというトレードオフがあります。データから遷移確率を推定するときも、めったに起きない遷移ほど推定が不安定で、観測されなかった遷移を確率0と置くと「一度入ったら出られない」偽の構造を作りかねません。モデルの単純さと現実の依存構造のバランスを見極めることが、マルコフ連鎖を使ううえでの設計判断です。
試問
晴・曇・雨の3つの天気があり、翌日の天気は今日の天気だけで決まります（矢印の太さと数字が、翌日にどの天気へ移るかの確率＝遷移確率）。「1000人の分布」では1000人を同じ天気から一斉に出発させて日を進め、「1人の旅」では1人がこの連鎖を歩き続けて、各天気で過ごした日の割合を数えます。破線は、この連鎖が最終的に落ち着く割合（定常分布）です。見るもの・スタート・進め方を切り替えて、命題を確かめてください（遷移確率を切り替えると、確かめ直しになります）。
1000人全員が「晴」にいます。「1日進める」を押すと、全員が矢印の確率どおりに分かれて移ります。光の量（人の割合）がどこに落ち着くか見てください。
矢印の太さ = 遷移確率（その天気の翌日にどこへ移るか）。破線 = 定常分布