マルコフ連鎖の再帰性とエルゴード性

状態の再帰・過渡を判定し、平均再帰時間と定常分布の関係 $π_{i} = 1/ m_{i}$ を使える

前提

到達確率と平均到達時間（大学数学確率・統計）
定常分布（大学数学確率・統計）

この技能までの道筋（65 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
条件付き確率と乗法定理（数学A 場合の数と確率）
四則の混じった計算の順序（算数計算と数のきまり）
等間隔にならんだ数の和（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
等差・等比数列の和と Σ （数学B 数列）
マルコフ連鎖と推移確率（大学数学確率・統計）
期待値（数学A 場合の数と確率）
確率変数と確率分布（数学B 統計的な推測）
平均と合計（算数いろいろな文章題）
平均値・中央値・最頻値（中学数学データの活用）
代表値（平均値・中央値・最頻値）（数学I データの分析）
分散と標準偏差（数学I データの分析）
変量の変換と平均・分散（数学I データの分析）
確率変数の期待値・分散と $a X + b$ （数学B 統計的な推測）
確率変数の和と積（独立な場合）（数学B 統計的な推測）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
多項式の不定積分（数学II 微分法と積分法）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
積と商の微分（数学III 微分法）
合成関数の微分（数学III 微分法）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
$sin x / x$ の極限（数学III 極限）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
三角関数の導関数（数学III 微分法）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
自然対数の底 $e$ （数学III 極限）
指数関数・対数関数の導関数（数学III 微分法）
基本的な関数の不定積分（数学III 積分法）
置換積分（数学III 積分法）
部分積分（数学III 積分法）
定積分の計算（数学II 微分法と積分法）
定積分の置換・部分積分と偶関数・奇関数（数学III 積分法）
重積分と累次積分（大学数学微分積分）
同時分布・周辺分布と独立性（大学数学確率・統計）
条件付き分布と全期待値の公式（大学数学確率・統計）
到達確率と平均到達時間（大学数学確率・統計）
定常分布（大学数学確率・統計）

説明

ある状態から出発した連鎖が確率 1 でその状態に戻ってくるか（再帰）、戻らない可能性があるか（過渡）を判定します。戻ってくる場合は、平均再帰時間 $m_{i}$ と定常分布 $π$ の間に $π_{i} = 1/ m_{i}$ という関係が成り立ちます。これを使うと、一段解析の長い連立方程式を解かなくても、 $π P = π$ を解くだけで平均再帰時間が求まります。逆に、平均再帰時間から、長い時間が経った後にその状態にいる時間の割合を読み取ることもできます。

なぜそうしてよいのか

状態 $i$ から出発したとき、初めて $i$ に戻る時刻を $T_{i} = min {n \geq 1 : X_{n} = i}$ とします（戻らなければ $T_{i} = \infty$ ）。戻る確率を $f_{i} = P_{i} (T_{i} < \infty)$ とおき、 $f_{i} = 1$ のとき $i$ は再帰的、 $f_{i} < 1$ のとき過渡的といいます。マルコフ性により、 $i$ に戻った瞬間から先の振る舞いは、最初に $i$ から出発したときと同じです（戻るたびにリセットされる）。そのため、 $k$ 回以上戻る確率は $f_{i}^{k}$ になります。戻る回数を $N$ とすると、 $E_{i} [N] = \sum_{k \geq 1} P_{i} (N \geq k) = \sum_{k \geq 1} f_{i}^{k}$ です。一方、 $N$ は各時刻 $n$ に $i$ にいるかどうかの和なので、 $E_{i} [N] = \sum_{n \geq 1} p_{ii}^{(n)}$ でもあります。前者は $f_{i} = 1$ のときに限って発散するので、再帰的であることは $\sum_{n \geq 1} p_{ii}^{(n)} = \infty$ と同値です。互いに行き来できる状態の集まりを通信類といい、同じ類の中では再帰・過渡がそろいます。状態が有限個のとき、外へ出られない類（閉じた類）は再帰的です。外へ出ると戻れなくなる道がある類は過渡的です。

再帰的な状態は、平均再帰時間 $m_{i} = E_{i} [T_{i}]$ が有限か無限かでさらに分けます。 $m_{i} < \infty$ なら正再帰、 $m_{i} = \infty$ なら零再帰です。正再帰のとき、 $i$ から $i$ への往復（サイクル）は互いに独立で同じ分布をもつ繰り返しになり、1 回の長さの平均は $m_{i}$ です。すると $n$ ステップの間に戻る回数はおよそ $n / m_{i}$ 回なので、長い目で見て $i$ にいる時間の割合は $1/ m_{i}$ に近づきます。一方、既約（全状態が互いに行き来できる）な連鎖を定常分布 $π$ から出発させると、どの時刻でも $P (X_{n} = i) = π_{i}$ です。したがって、 $i$ にいる時間の割合の期待値はちょうど $π_{i}$ です。既約で再帰的なら長期の滞在割合は出発点によらないので、二つを比べると $π_{i} = 1/ m_{i}$ が得られます。特に、既約な連鎖では「正再帰であること」と「定常分布（和が 1 の非負の解）が存在すること」は同値で、存在すれば定常分布は一意です。

さらに、周期 $d_{i} = g cd {n \geq 1 : p_{ii}^{(n)} > 0}$ が 1 のとき、状態 $i$ を非周期的といいます（周期も通信類の中でそろいます）。既約・正再帰・非周期的な連鎖をエルゴード的と呼びます。エルゴード的な連鎖では、滞在割合だけでなく分布そのものも収束し、 $p_{ij}^{(n)} \to π_{j} = 1/ m_{j} (n \to \infty)$ となります。

手順

状態を通信類に分け、各類が閉じているかを調べる。状態が有限個なら、閉じた類は正再帰、閉じていない類は過渡的と判定する（無限個なら $\sum_{n} p_{ii}^{(n)}$ の発散・収束で再帰・過渡を判定する）。
調べたい状態を含む閉じた既約な類に連鎖を制限し、その上で $π P = π$ , $π_{i} \geq 0$ , $\sum_{i} π_{i} = 1$ を解く。
平均再帰時間を $m_{i} = 1/ π_{i}$ で求める（過渡的・零再帰的な状態では $m_{i} = \infty$ または戻らない可能性があり、定常分布での値は $π_{i} = 0$ ）。
必要なら周期を調べ、非周期的（エルゴード的）なら $p_{ij}^{(n)} \to π_{j}$ として長時間後の分布に使う。

例題

状態空間 ${1, 2, 3}$ 上のマルコフ連鎖の推移確率が $p_{11} = \frac{1}{2}, p_{12} = \frac{1}{2}, p_{13} = 0$ , $p_{21} = \frac{1}{4}, p_{22} = \frac{1}{2}, p_{23} = \frac{1}{4}$ , $p_{31} = 0, p_{32} = \frac{1}{2}, p_{33} = \frac{1}{2}$ で与えられている。状態 1 から出発したとき、初めて状態 1 に戻るまでの時間の期待値 $m_{1} = E_{1} [T_{1}]$ （ $T_{1} = min {n \geq 1 : X_{n} = 1}$ ）を求めよ。

例題の解答

手順1: $1 \to 2 \to 3$ と $3 \to 2 \to 1$ がともに正の確率で起こるので、3 つの状態は 1 つの通信類をなし、連鎖は既約です。状態は有限個で、この類は閉じているので、すべての状態は正再帰です。したがって定常分布が一意に存在し、 $π_{1} = 1/ m_{1}$ が使えます。

手順2: $π P = π$ の第 1 成分は $π_{1} = \frac{1}{2} π_{1} + \frac{1}{4} π_{2}$ で、ここから $π_{2} = 2 π_{1}$ です。第 3 成分は $π_{3} = \frac{1}{4} π_{2} + \frac{1}{2} π_{3}$ で、ここから $π_{2} = 2 π_{3}$ です。よって $π_{3} = π_{1}$ です。和が 1 なので $π_{1} + 2 π_{1} + π_{1} = 1$ となり、 $π = (\frac{1}{4}, \frac{1}{2}, \frac{1}{4})$ を得ます。第 2 成分も $\frac{1}{2} \cdot \frac{1}{4} + \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{4} = \frac{1}{2}$ で成り立っています。

手順3: $m_{1} = 1/ π_{1} = 4$ です。

（検算）一段解析でも確かめます。状態 $j$ から 1 に初めて到達するまでの平均時間を $h_{j}$ とすると、 $h_{2} = 1 + \frac{1}{2} h_{2} + \frac{1}{4} h_{3}$ , $h_{3} = 1 + \frac{1}{2} h_{3} + \frac{1}{2} h_{2}$ です。第 2 式から $h_{3} = 2 + h_{2}$ で、これを第 1 式に代入すると $\frac{1}{4} h_{2} = \frac{3}{2}$ 、すなわち $h_{2} = 6$ です。よって $m_{1} = 1 + \frac{1}{2} \cdot 0 + \frac{1}{2} h_{2} = 4$ となり、一致します。

答え: $4$

よくある誤り

平均再帰時間を、他の状態からの平均到達時間と取り違える誤り。例題で $h_{2} = 6$ を $m_{1}$ としてしまうのは誤りです。正しくは、最初の 1 歩を含めて $m_{i} = 1 + \sum_{j \neq = i} p_{ij} h_{j}$ で、例題では $m_{1} = 4$ です。
状態が無限個でも「再帰的なら定常分布がある」としてしまう誤り。 $Z$ 上の対称ランダムウォークでは $\sum_{n} p_{00}^{(2 n)} = \sum_{n} (n 2 n) 4^{- n} = \infty$ なので再帰的です。しかし $m_{0} = \infty$ （零再帰）です。実際、 $π P = π$ は $π_{i} = \frac{1}{2} (π_{i - 1} + π_{i + 1})$ となり、その解は $π_{i} = a + bi$ の形です。このうち全ての $i \in Z$ で非負になるのは $b = 0$ の定数だけで、定数では和を 1 にできません。つまり定常分布（非負で和が 1 の解）は存在しません。正しくは、定常分布が存在するのは正再帰のときです。
周期的な連鎖でも $p_{ii}^{(n)} \to π_{i}$ としてしまう誤り。 $p_{12} = p_{21} = 1$ の 2 状態連鎖では $π = (\frac{1}{2}, \frac{1}{2})$ で、 $m_{i} = 2$ なので $π_{i} = 1/ m_{i}$ は成り立ちます。しかし $p_{11}^{(n)}$ は $0, 1, 0, 1, \dots$ と振動して収束しません。正しくは、分布の収束には非周期性（エルゴード性）が必要です。
既約でない連鎖に $π_{i} = 1/ m_{i}$ をそのまま使う誤り。吸収状態が 2 つある連鎖（ $p_{11} = p_{22} = 1$ ）では $m_{1} = m_{2} = 1$ ですが、 $(a, 1 - a) (0 \leq a \leq 1)$ はどれも定常分布で、一般には $π_{1} = a \neq = 1/ m_{1}$ です。正しくは、閉じた既約な類ごとにその類の上の定常分布を求め、その類の中で $π_{i} = 1/ m_{i}$ を使います。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

難易度 4（大学院入試の難問レベル）
$n \geq 2$ を整数とし、 ${0, 1}^{n}$ に値をとるマルコフ連鎖 $(X_{t})_{t \geq 0}$ を次のように定める。 $X_{0} = (0, 0, \dots, 0)$ とし、各時刻 $t = 0, 1, 2, \dots$ において、添字 $i \in {1, 2, \dots, n}$ を一様に選び、それとは独立にビット $b \in {0, 1}$ を等確率で選んで、 $X_{t}$ の第 $i$ 成分だけを $b$ に置き換えたものを $X_{t + 1}$ とする（他の成分は変えない）。各時刻の選択は互いに独立とする。
$T = min {t \geq 0 : X_{t} = (1, 1, 0, 0, \dots, 0)}$
とおく（第 $1$ 成分と第 $2$ 成分が $1$ 、残りが $0$ の状態に初めて到達する時刻）。期待値 $E [T]$ を $n$ の式で求めよ。

この技能の次に学べること

誘導写像とカッツの補題・アブラモフの公式（大学院数学力学系・エルゴード理論）