この章のまとめ

確率論入門　第15章 §15.6

この章では、マルコフ連鎖を長く走らせたときの振る舞いを4つの問いに分けて調べた。

(1) 出発点に戻ってくるか

戻る確率 $f_{jj}$ が 1 かどうかで、状態を再帰的と過渡的に分けた。強マルコフ性から、訪問回数は幾何分布に従う。よって Green 関数 $G(j,j)=\sum_np^{(n)}_{jj}$ が発散することと、再帰性が同値になる。

この判定は $p^{(n)}_{jj}$ の漸近形だけで済む。ランダムウォークでは Stirling の公式から、1次元と2次元の対称な場合が再帰的で、3次元が過渡的であることが分かった。対称な1次元のランダムウォークは $+1$ に確率 1 で達するが、達するまでの平均時間は無限大である。これは第7章で Wald の等式から得た結論と一致する。

再帰性は同じクラスで共有される。再帰的なクラスは閉じており、有限の閉じたクラスは再帰的である。

(2) どこに吸収されるか

最初の1歩で場合を分けると、到達確率と平均到達時間が、連立1次方程式の最小の非負解として特徴づけられる。有限の場合は解がただ1つで、基本行列 $(I-Q)^{-1}$ が過渡的な状態の Green 関数を並べたものになる。ギャンブラーの破産では、1回あたりのわずかな不利が目標到達の確率を大きく下げることを数値で確かめた。

(3) 分布はどこへ落ち着くか

再帰的な状態からの1周期のあいだの平均滞在回数 $\gamma^k$ が、不変測度を与える。既約で再帰的なら、不変測度は定数倍を除いてただ1つである。その総和が平均再帰時間なので、定常分布が存在することと正再帰性が同値で、$\pi_i=1/m_i$ となる。非周期的なら、独立な2つの連鎖を出会わせる結合の議論から、各時刻の分布が全変動距離で定常分布に収束する。

(4) 時間平均は何に収束するか

ある状態に戻る時刻で見本路を切ると、独立同分布の周期の列になる。大数の強法則から、再生過程の強法則と再生報酬定理が出る。これをマルコフ連鎖に使うとエルゴード定理が得られ、時間平均は定常分布による平均に収束する。この定理は周期を仮定しない。

応用として、詳細つり合いを満たすように受け入れ確率を決める Metropolis 法を導いた。また対称性による集約で、Ehrenfest の壺の $2^N$ 状態の連鎖を $N+1$ 状態の出生死滅連鎖に還元した。

この先

この章で確率論入門は終わる。この章の結果は、連続時間のマルコフ過程（待ち行列・化学反応の確率モデル）や、統計力学の Monte Carlo シミュレーション、確率的なアルゴリズムの解析の出発点になる。連続時間に移るときは、第14章 §14.3 の Poisson 過程の到着間隔の指数分布が、状態に留まる時間の分布として現れる。