← 戻る ライブラリ › 確率と統計 › 現代確率論 確率と統計
確率過程とマルコフ連鎖 時間とともに変化するランダムな状態の列で、マルコフ連鎖は現在の状態のみに依存する。
直観 もし明日が今日のことしか気にしないなら、どこまで未来を予測できるだろうか? 池の蓮の葉を飛び移るカエル、マス目を一つずつ進むボードゲームの駒、晴れと雨の間で切り替わる明日の天気を思い浮かべてほしい。いずれの場合も、時計が刻まれるたびに変化する状態 (どの葉か、どのマス目か、どの天気か)があり、その変化はあらかじめ決まっているのではなく——ランダムである。確率過程 とは、単に時間 n = 0 , 1 , 2 , … n=0,1,2,\dots n = 0 , 1 , 2 , … X n ∈ S X_n \in S X n ∈ S マルコフ連鎖 とは、カエルが物忘れをする特別で非常に有用な場合であり、次の跳躍の確率は現在 座っている蓮の葉だけに依存し、そこに至るまでの曲がりくねった経路には決して依存しない。
有向の状態図:各ノードが状態であり、ラベル付きの矢印がそれぞれ遷移確率を表す。ハイライトされたノードを切り替えて見ると、現在どの状態にいても、そこから出る矢印だけが次にどこへ行くかを決めており、それより前の経路は一切関係ないことが分かる。 大学 マルコフ性、遷移行列、定常分布 定義: マルコフ連鎖
可算な状態集合を S S S n = 0 , 1 , 2 , … n=0,1,2,\dots n = 0 , 1 , 2 , … S S S X n ∈ S X_n \in S X n ∈ S マルコフ連鎖 であるとは、マルコフ性 、すなわちどの状態の選び方、どの n n n P ( X n + 1 ∣ X n , … , X 0 ) = P ( X n + 1 ∣ X n ) P(X_{n+1}\mid X_n,\dots,X_0)=P(X_{n+1}\mid X_n) P ( X n + 1 ∣ X n , … , X 0 ) = P ( X n + 1 ∣ X n ) X n X_n X n X 0 , … , X n − 1 X_0,\dots,X_{n-1} X 0 , … , X n − 1 X n + 1 X_{n+1} X n + 1
P ( X n + 1 ∣ X n , … , X 0 ) = P ( X n + 1 ∣ X n ) P(X_{n+1}\mid X_n,\dots,X_0)=P(X_{n+1}\mid X_n) P ( X n + 1 ∣ X n , … , X 0 ) = P ( X n + 1 ∣ X n ) 状態空間が有限(または可算)で連鎖が時間斉次であるとき、このランダム性はすべて単一の遷移行列 P P P P i j = P ( X n + 1 = j ∣ X n = i ) P_{ij}=P(X_{n+1}=j\mid X_n=i) P ij = P ( X n + 1 = j ∣ X n = i ) i i i j j j どこかへ 行かなければならないため、P P P ∑ j ∈ S P i j = 1 \sum_{j\in S} P_{ij}=1 ∑ j ∈ S P ij = 1 行確率的 と呼ぶ。n n n m m m チャップマン–コルモゴロフ方程式 P ( n + m ) = P ( n ) P ( m ) P^{(n+m)}=P^{(n)}P^{(m)} P ( n + m ) = P ( n ) P ( m ) μ 0 \mu_0 μ 0 n n n μ 0 P n \mu_0 P^n μ 0 P n
P i j = P ( X n + 1 = j ∣ X n = i ) P_{ij}=P(X_{n+1}=j\mid X_n=i) P ij = P ( X n + 1 = j ∣ X n = i ) S S S π \pi π 定常 であるとは、この力学の不動点であること、すなわち π P = π \pi P=\pi π P = π ∑ i ∈ S π i = 1 \sum_{i\in S}\pi_i=1 ∑ i ∈ S π i = 1 π i ≥ 0 \pi_i\ge0 π i ≥ 0 π \pi π π \pi π π \pi π
マルコフ連鎖を分類する主要な性質 性質 定義 帰結 既約 任意の状態から他の任意の状態へ正の確率で到達できる 連鎖は(高々)一つの定常分布を持つ 非周期的 ある状態への可能な帰還時刻の最大公約数が1である P n P^n P n 再帰的 状態 i i i i i i 有限既約連鎖ではこれは常に自動的に成り立つ
有限状態空間 S S S π P = π \pi P=\pi π P = π π i > 0 \pi_i>0 π i > 0 π \pi π lim n → ∞ P n = 1 π \lim_{n\to\infty}P^n=\mathbf 1\,\pi lim n → ∞ P n = 1 π P n P^n P n n → ∞ n\to\infty n → ∞ π \pi π
なぜ正しいのか? これこそがマルコフ連鎖がそもそも有用である理由である:ランダムに進化する系の長期的な振る舞いは、出発点を忘れて単一の予測可能なパターンに落ち着くこと、そしてそのパターンが何であるか(遷移ダイナミクスの唯一の不動点)を正確に教えてくれる。
証明 存在性と一意性。P P P P P P π \pi π π P = π \pi P=\pi π P = π P P P
収束性。非周期性と既約性を合わせると、P P P 他の すべての固有値 λ \lambda λ ∣ λ ∣ < 1 |\lambda|<1 ∣ λ ∣ < 1 − 1 -1 − 1 μ 0 \mu_0 μ 0 P P P π \pi π n n n λ n \lambda^n λ n
この二つのステップを合わせると、μ 0 P n \mu_0 P^n μ 0 P n π \pi π μ 0 \mu_0 μ 0 P n P^n P n π \pi π
J J J N × N N\times N N × N N N N P P P i i i d ∈ ( 0 , 1 ) d\in(0,1) d ∈ ( 0 , 1 ) Google行列 G = d P + ( 1 − d ) 1 N J G=dP+(1-d)\tfrac1N J G = d P + ( 1 − d ) N 1 J π = π ( d P + ( 1 − d ) 1 N J ) \pi=\pi\Big(dP+(1-d)\tfrac1N J\Big) π = π ( d P + ( 1 − d ) N 1 J ) π \pi π π \pi π π k + 1 = π k G \pi_{k+1}=\pi_k G π k + 1 = π k G
なぜ正しいのか? これにより、「重要なページは他の重要なページからリンクされる」という曖昧な考えが、一意の解が保証された明確な不動点問題へと変わり、「リンクに沿ってランクを広げる」ことを単に繰り返すべき乗法がなぜ振動したり発散したりせず確実にうまくいくのかが説明される。
証明 既約性。1 − d > 0 1-d>0 1 − d > 0 G G G G i j ≥ ( 1 − d ) / N > 0 G_{ij}\ge(1-d)/N>0 G ij ≥ ( 1 − d ) / N > 0 G G G
非周期性。どの状態からも(G i i > 0 G_{ii}>0 G ii > 0 1 , 2 , 3 , … 1,2,3,\dots 1 , 2 , 3 , … G G G
存在性・一意性・収束性。G G G P P P J / N J/N J / N d P + ( 1 − d ) 1 N J dP+(1-d)\tfrac1N J d P + ( 1 − d ) N 1 J π = π ( d P + ( 1 − d ) 1 N J ) \pi=\pi\Big(dP+(1-d)\tfrac1N J\Big) π = π ( d P + ( 1 − d ) N 1 J ) π \pi π G n G^n G n π \pi π
べき乗法。任意の出発分布 π 0 \pi_0 π 0 π k = π 0 G k \pi_k=\pi_0G^k π k = π 0 G k G k G^k G k k → ∞ k\to\infty k → ∞ π \pi π π 0 G k \pi_0G^k π 0 G k π \pi π π k + 1 = π k G \pi_{k+1}=\pi_k G π k + 1 = π k G
大学 実世界での応用と具体例 マルコフ連鎖は、「現在が分かれば過去を忘れる」ことが妥当な近似となる非常に幅広い系をモデル化する。Googleの元祖 ページランク アルゴリズムは、リンクをクリックするランダムサーファーの定常分布(上で証明した)によってウェブページを順位付けする。生物学では、DNA配列やタンパク質の折り畳み経路がヌクレオチドやコンフォメーションに関するマルコフ連鎖としてモデル化される。金融やオペレーションズ・リサーチでは、待ち行列システム(レジで待つ客)や在庫水準がマルコフ連鎖として追跡され、長期的な待ち時間や欠品確率が計算される。音声認識や自然言語処理では、隠れマルコフモデルが音素や品詞タグの列をつなぎ合わせる。そしてコンピュータ科学では、MCMC(マルコフ連鎖モンテカルロ)アルゴリズムが、サンプリングが難しい目標分布を定常分布とするマルコフ連鎖を構築し、それをシミュレートして近似サンプルを得る。
例: 天気の定常分布
単純化した天気モデルには晴れと雨の2状態があり、遷移行列は P = ( 0.9 0.1 0.5 0.5 ) P=\begin{pmatrix}0.9&0.1\\0.5&0.5\end{pmatrix} P = ( 0.9 0.5 0.1 0.5 ) 0.9 0.9 0.9 0.1 0.1 0.1 π = ( π 1 , π 2 ) \pi=(\pi_1,\pi_2) π = ( π 1 , π 2 )
解答 定常方程式は π P = π \pi P=\pi π P = π 0.9 π 1 + 0.5 π 2 = π 1 0.9\pi_1+0.5\pi_2=\pi_1 0.9 π 1 + 0.5 π 2 = π 1 0.1 π 1 + 0.5 π 2 = π 2 0.1\pi_1+0.5\pi_2=\pi_2 0.1 π 1 + 0.5 π 2 = π 2 π 1 + π 2 = 1 \pi_1+\pi_2=1 π 1 + π 2 = 1
第一式は 0.5 π 2 = 0.1 π 1 0.5\pi_2=0.1\pi_1 0.5 π 2 = 0.1 π 1 π 2 = 0.2 π 1 \pi_2=0.2\pi_1 π 2 = 0.2 π 1 π P − π \pi P-\pi π P − π
正規化に代入すると π 1 + 0.2 π 1 = 1 \pi_1+0.2\pi_1=1 π 1 + 0.2 π 1 = 1 1.2 π 1 = 1 1.2\pi_1=1 1.2 π 1 = 1 π 1 = 5 / 6 \pi_1=5/6 π 1 = 5/6 π 2 = 1 / 6 \pi_2=1/6 π 2 = 1/6
よって π = ( 5 / 6 , 1 / 6 ) \pi=(5/6,\,1/6) π = ( 5/6 , 1/6 ) 5 / 6 5/6 5/6 0.5 0.5 0.5 0.9 0.9 0.9
例: 3ページのウェブのページランク
3つのページ A , B , C A,B,C A , B , C A A A B B B C C C B B B C C C C C C A A A P ( A → B ) = P ( A → C ) = 1 2 , P ( B → C ) = 1 , P ( C → A ) = 1 P(A\to B)=P(A\to C)=\tfrac12,\quad P(B\to C)=1,\quad P(C\to A)=1 P ( A → B ) = P ( A → C ) = 2 1 , P ( B → C ) = 1 , P ( C → A ) = 1 { A , B , C } \{A,B,C\} { A , B , C } π \pi π
解答 まず連鎖が既約かつ非周期的であることを確認する:どのページからも他の任意のページへ到達でき(A → B → C → A A\to B\to C\to A A → B → C → A A → C → A A\to C\to A A → C → A A → B → C → A A\to B\to C\to A A → B → C → A π \pi π
各列ごとに釣り合いの方程式を書く:π A \pi_A π A C C C π B \pi_B π B A A A π C \pi_C π C A A A B B B π A = π C , π B = 1 2 π A , π C = 1 2 π A + π B \pi_A=\pi_C,\quad \pi_B=\tfrac12\pi_A,\quad \pi_C=\tfrac12\pi_A+\pi_B π A = π C , π B = 2 1 π A , π C = 2 1 π A + π B
最初の2つの式から直接 π A = π C \pi_A=\pi_C π A = π C π B = 1 2 π A \pi_B=\tfrac12\pi_A π B = 2 1 π A π A + π B + π C = 1 \pi_A+\pi_B+\pi_C=1 π A + π B + π C = 1 π A + 1 2 π A + π A = 1 \pi_A+\tfrac12\pi_A+\pi_A=1 π A + 2 1 π A + π A = 1 5 2 π A = 1 \tfrac52\pi_A=1 2 5 π A = 1
これを解いて π A = 2 / 5 \pi_A=2/5 π A = 2/5 π = ( π A , π B , π C ) = ( 2 / 5 , 1 / 5 , 2 / 5 ) \pi=(\pi_A,\pi_B,\pi_C)=(2/5,\,1/5,\,2/5) π = ( π A , π B , π C ) = ( 2/5 , 1/5 , 2/5 ) A A A C C C
よくある誤り. 常に繰り返される誤りが2つある。第一に、マルコフ性を完全な独立性と混同すること:マルコフ連鎖の未来は一般に過去と独立ではない ——それは現在の状態が与えられたもとで 過去と独立なのであり、これはずっと弱い(そしてずっと有用な)主張である。第二に、定常分布が存在していても連鎖がそれに収束するとは限らないことを忘れること:周期的な連鎖(例えば決定的に A → B → A → B A\to B\to A\to B A → B → A → B π P = π \pi P=\pi π P = π P n P^n P n π P = π \pi P=\pi π P = π 歴史的ノート
アンドレイ・マルコフは1906年、プーシキンの詩『エヴゲニー・オネーギン』における母音と子音の交替を分析する論文の中で、彼の名を冠する連鎖を導入した——これは一部、大数の法則が成り立つには独立性が必要であるという当時の主張に反論するためのものであり、従属していても物忘れをする列が同様の極限法則に従うことを示した。この理論は、アンドレイ・コルモゴロフが1931年に発表した確率論における解析的手法に関する論文が、連続時間・連続状態版を含む一般のマルコフ過程を厳密な測度論的基盤の上に置き、それらを微分方程式(コルモゴロフの前進・後退方程式)と結びつけ、今日用いられている確率過程の一般理論への道を開くまで、主に組合せ論的なものにとどまっていた。
アンドレイ・コルモゴロフ
研究の最前線 2026年時点
マルコフ連鎖は、その古典的用途をはるかに超えて今なお活発な研究分野である。マルコフ連鎖モンテカルロ(MCMC)はベイズ統計学と統計物理学の計算基盤であり、中心的な未解決問題の一つは混合時間 ——連鎖が定常分布に近づくまでに必要なステップ数——を、現実的な高次元モデルから生じる連鎖について評価することである。スペクトルギャップやカップリング技法は一部の連鎖(カードシャッフル、群上のランダムウォーク)には鋭い答えを与えるが、複雑なベイズ事後分布や相転移近傍のイジング模型のような分布からサンプリングする、実務で使われる多くの連鎖については依然として困難である。マルコフ連鎖に制御可能な行動を加えたマルコフ決定過程は、現代の強化学習の基盤をなす。巨大な、あるいは連続な状態空間上で動作するRLアルゴリズムのサンプル複雑度と収束保証を理解することは、確率論、最適化、機械学習を結びつける活発な研究領域である。応用面では、元のページランクの定式化をはるかに超えて、より洗練されたランダムサーファーモデルや拡散モデルが、ランキングやレコメンデーションシステム向けに開発され続けている。
マルコフ性とは、現在の状態 X n X_n X n X n + 1 X_{n+1} X n + 1
現在 X n X_n X n X 0 , … , X n − 1 X_0,\dots,X_{n-1} X 0 , … , X n − 1 X n X_n X n X 0 , … , X n − 1 X_0,\dots,X_{n-1} X 0 , … , X n − 1 常に X n X_n X n X n X_n X n 3状態の連鎖の遷移行列の各行は、それぞれ:
和が1で、すべての成分が非負である 和が0である 非ゼロの成分をちょうど1つだけ含む 他のすべての行と同一である
遷移行列 P = ( 0.9 0.1 0.5 0.5 ) P=\begin{pmatrix}0.9&0.1\\0.5&0.5\end{pmatrix} P = ( 0.9 0.5 0.1 0.5 ) π P = π \pi P=\pi π P = π ∑ i ∈ S π i = 1 \sum_{i\in S}\pi_i=1 ∑ i ∈ S π i = 1 π \pi π
π = ( 1 / 2 , 1 / 2 ) \pi=(1/2,1/2) π = ( 1/2 , 1/2 ) π = ( 5 / 6 , 1 / 6 ) \pi=(5/6,\,1/6) π = ( 5/6 , 1/6 ) π = ( 1 , 0 ) \pi=(1,0) π = ( 1 , 0 ) π = ( 0.1 , 0.9 ) \pi=(0.1,0.9) π = ( 0.1 , 0.9 ) Googleの元祖ページランクにおいて、減衰係数 d < 1 d<1 d < 1 1 / N 1/N 1/ N
対称である 既約かつ非周期的であり、基本定理により一意の定常分布が保証される 正則(可逆)である 対角行列である