マルコフ連鎖

概要

マルコフ連鎖は、時間とともに状態が確率的に移り変わっていく仕組み（確率過程）のうち、「次にどの状態へ移るかが、現在の状態だけで決まり、それ以前の履歴には依存しない」という性質を持つものです。この性質をマルコフ性と呼びます。たとえば「今日晴れなら明日も晴れる確率は0.8、今日雨なら明日晴れる確率は0.4」という天気のモデルは、一昨日以前の天気を一切参照しないマルコフ連鎖です。

サイコロを繰り返し振るような、各回が独立な試行の列とは違い、マルコフ連鎖では「今の状態」が「次」に影響します。かといって全履歴を引きずるわけでもない。この「直前だけを覚えている」中間的な設定が絶妙で、現実の多くの現象 — 天気、顧客のサブスク継続と解約、Webページ間の回遊、文章中の単語のつながり、待ち行列の長さ — を、扱える複雑さのままモデル化できます。

マルコフ連鎖は応用の裾野が非常に広い概念です。Googleの初期の検索順位を支えたPageRankは「リンクをランダムにたどるマルコフ連鎖」の分析ですし、ベイズ統計の計算を実用化したマルコフ連鎖モンテカルロ法は、その名のとおりマルコフ連鎖をエンジンとして使います。

なぜ生まれたか

19世紀までの確率論の主要な成果 — 大数の法則や中心極限定理 — は、試行どうしが独立であることを前提に組み立てられていました。しかし現実の系列データの多くは独立ではありません。今日の天気は昨日の影響を受け、文章の次の文字は直前の文字に依存します。「依存があるなら確率論の法則は成り立たないのではないか」という疑問に、当時の理論は答えを持っていませんでした。

ロシアの数学者アンドレイ・マルコフは1906年頃、「依存はあるが、依存の仕方が単純な（直前だけに依存する）」試行の列を定式化し、そのような列でも大数の法則が成り立つことを証明しました。独立性は法則の必須条件ではなかったのです。マルコフはこの理論をプーシキンの韻文『エフゲニー・オネーギン』の文字列に適用し、母音・子音の並びを2状態の連鎖として分析してみせました。これは系列データの統計モデリングの出発点であり、のちの待ち行列理論、情報理論、そして現代の音声認識や言語モデルにつながる系譜の源流になりました。

詳細

状態・遷移確率・遷移行列

マルコフ連鎖は「状態の集合」と「遷移確率」で定義されます。遷移確率は条件付き確率そのもので、「現在の状態がAであるという条件のもとで、次に状態Bへ移る確率」を各ペアについて与えたものです。各時点の状態は確率変数であり、その列がマルコフ性という規則で連結されています。

遷移確率を行列に並べたものが遷移行列です。遷移行列の便利さは、行列の掛け算がそのまま時間の前進に対応することにあります。「今日の状態の確率分布」を表すベクトルに遷移行列を1回掛ければ明日の分布、2回掛ければ明後日の分布が得られます。nステップ後の予測が行列のn乗という機械的な計算に落ちるのです。

定常分布 — 長く走らせるとどこに落ち着くか

マルコフ連鎖の理論で最も重要な概念が定常分布です。多くの連鎖では、遷移を何度も繰り返すうちに状態の確率分布が特定の分布に収束し、それ以上遷移させても変化しなくなります。上の天気の例なら、初日が晴でも雨でも、十分先の日の晴の確率は約0.667に落ち着きます。初期状態の影響が薄れて消える — この性質は、どの状態からも他の状態へ到達でき（既約性）、周期的な行き来に閉じ込められない（非周期性）連鎖で保証されます。

定常分布は「その連鎖を長時間走らせたとき、各状態に滞在する時間の割合」とも解釈できます。PageRankはまさにこの解釈で、「リンクをランダムにたどり続けるユーザーが、長期的に各ページに滞在する割合」を定常分布として求め、ページの重要度としました。

応用と拡張

マルコフ連鎖のモデリングは実務のあちこちに現れます。顧客が「無料会員・有料会員・解約」の間を月ごとに遷移するモデルからLTV（顧客生涯価値）を見積もる、機械が「正常・劣化・故障」を遷移する信頼性モデルで保守計画を立てる、といった使い方が典型です。状態が直接観測できず、状態から確率的に出力される信号だけが見える設定に拡張したものが隠れマルコフモデルで、音声認識や遺伝子配列解析の土台になりました。さらに「行動の選択」を加えたマルコフ決定過程は、強化学習の標準的な問題設定です。

そして統計学における最大の応用がマルコフ連鎖モンテカルロ法です。これは発想の逆転で、通常は「与えられた連鎖の定常分布を求める」のに対し、MCMCでは「狙った分布が定常分布になるような連鎖を設計」し、走らせることでその分布からのサンプルを得ます。マルコフ連鎖を理解しておくことは、この現代ベイズ統計の中核技術を理解するための直接の足場になります。

注意点としては、マルコフ性はあくまで仮定だということです。現実には「直前より前」が効く現象も多く（たとえば自然な文章は直前の1単語だけでは決まりません）、その場合は直近k個の状態をまとめて1つの状態とみなす高次のマルコフ連鎖などで対応しますが、状態数が爆発しやすいというトレードオフがあります。モデルの単純さと現実の依存構造のバランスを見極めることが、マルコフ連鎖を使う上での設計判断になります。