線形代数 · マルコフ連鎖

マルコフ連鎖

マルコフ連鎖では状態が確率的に変化し、次の状態の確率は現在の状態だけで決まる。確率を推移行列 P に並べると、明日の分布は今日の分布に右から P を掛けたもの。繰り返すと、多くの場合 πP = π を満たす定常分布 π(固有値1の左固有ベクトル)に近づく。

この図で見るマルコフ連鎖

マルコフ連鎖では、次の状態の確率は現在の状態だけで決まる。ここでは晴れ・曇り・雨の3状態を使う。推移行列 PP の第 ii 行には、今日が状態 ii のときの明日の確率が並び、各行は確率ベクトルになる。今日の分布を行ベクトル pp とすれば、明日は pPpP、nn 日後は pn=p0Pnp_n = p_0 P^n。3状態なら分布は三角形内の点で、各頂点は一つの状態が確実な場合、三つの確率は各頂点の重みを表す。濃い点は PP の各行、青は初期分布、赤は p0,p1,p2,…p_0, p_1, p_2, \dots を結ぶ道である。

1ステップで起きること

1ステップで各頂点は対応する行に移る。今日が確実に晴れなら明日の分布は第1行になる。他の分布 pp は頂点の加重平均なので、pPpP は各行の同じ重みでの平均。三角形全体は行が張る小さな三角形に、2ステップ後には P2P^2 の行が張る三角形に入る。PP のあるべきの全成分が正なら、入れ子の三角形は一点、定常分布 π\pi に縮む。

π が固有ベクトルである理由と pₙ の収束速度

動かない点は πP=π\pi P = \pi を満たす。したがって π\pi は固有値1の固有ベクトルで、正確には左固有ベクトル(列で書けば PTπT=πTP^{\mathsf T}\pi^{\mathsf T} = \pi^{\mathsf T})。差 p0−πp_0 - \pi の成分の和は0で、この部分空間での PP の固有値は残りの二つ λ2,λ3\lambda_2, \lambda_3 である。各固有方向では1ステップで対応する固有値倍になる。両方の絶対値が1未満なら pnp_n は π\pi に近づき、大きい方の絶対値 ∣λ2∣|\lambda_2| が収束の速さを支配する。天気の連鎖では ∣λ2∣≈0.462|\lambda_2| \approx 0.462。初期分布に λ2\lambda_2 方向の成分があれば、nn が大きいと各ステップ後に残る距離は半分弱になる。複素固有値なら縮みながら回転もする。

収束しない場合

周期の例は晴れ・曇り・雨を繰り返す。他の二つの固有値の絶対値は1で、π\pi から始める場合を除いて pnp_n は巡り続ける。二つの吸収状態の例では晴れも雨も一度入ると抜け出せず、固有値1は二重。晴れと雨のどんな混合も動かないので pnp_n は収束するが、極限は初期分布に依存する。有限連鎖で pnp_n がどこからも同じ π\pi に収束する必要十分条件は、閉じた通信類がただ一つあり、それが非周期的であること。通信類の内部ではどの2状態間も行き来でき、閉じていれば外に出られない。PmP^m の全成分が正になるようなべきがあればこの条件を満たす。

注目する点

  • 天気の連鎖の定常分布は、初期状態によらず、遠い将来のある日の天気の確率を表す。実際の天気はその後も日々変わる。
  • 4状態以上では、分布は三角形を高次元にした単体を埋める。同じ議論が成り立つ。

操作

  • 濃い点をドラッグすると推移行列の行、青い点なら初期分布を変更できる。フォーカスした点は矢印キーで0.01ずつ動く。

関連項目