マルコフ連鎖推移確率行列・定常分布・状態の分類・吸収確率

マルコフ連鎖は、次の状態の分布が現在の状態だけで決まる確率過程で、有限状態なら推移確率行列 $P = (p_{ij})$ （各行の和が $1$ ）で表す。 $n$ ステップ後の推移確率は $P^n$ の成分で、時刻 $n$ の分布は行ベクトル $\boldsymbol{\pi}_0 P^n$ になる。定常分布は $\boldsymbol{\pi} P = \boldsymbol{\pi}$ 、 $\sum_i \pi_i = 1$ を解いて求める。有限状態で既約なら定常分布はただ1つで、さらに非周期なら初期分布によらず $\boldsymbol{\pi}_0 P^n \to \boldsymbol{\pi}$ となる。

確率・統計の第8単元（全8単元）。先に読む単元：確率空間と確率変数、線形代数・固有値と固有ベクトル

院試数学基礎完成シリーズ確率統計編

基礎ノートと類題を答案の形で解いた問題集（2,480円）。収録章と見本ページを商品ページで確認できる。過去問の本文は収録していない。

確率統計編の内容を見る

マルコフ性と推移確率行列

定義

離散時間マルコフ連鎖

状態空間 $S$ （有限または可算）に値をとる確率変数の列 $X_0, X_1, \dots$ が、すべての $n$ と状態について

P(X_{n+1} = j \mid X_n = i, X_{n-1} = i_{n-1}, \dots, X_0 = i_0) = P(X_{n+1} = j \mid X_n = i)

を満たすとき（条件の確率が正の場合）、マルコフ連鎖という。右辺が $n$ によらないとき時間的に一様といい、 $p_{ij}$ と書く。 $P = (p_{ij})$ を推移確率行列といい、 $p_{ij} \ge 0$ 、 $\sum_j p_{ij} = 1$ を満たす。

チャップマン・コルモゴロフ方程式: $p_{ij}^{(m+n)} = \sum_{k \in S} p_{ik}^{(m)} p_{kj}^{(n)}, \qquad P^{(n)} = P^n$
時刻 $n$ の分布: $\boldsymbol{\pi}_n = \boldsymbol{\pi}_0 P^n$
$\boldsymbol{\pi}_n = (P(X_n = j))_j$ は行ベクトル。右から $P$ を掛ける。

状態の分類

定義

到達・既約・周期

ある $n \ge 0$ で $p_{ij}^{(n)} > 0$ のとき、 $i$ から $j$ に到達可能という。互いに到達可能な状態は同じ類に属する。全状態が1つの類になるとき既約という。

状態 $i$ の周期を $d(i) = \gcd\{n \ge 1 : p_{ii}^{(n)} > 0\}$ と定め、 $d(i) = 1$ なら非周期という。 $p_{ii} > 0$ ならその状態は非周期である。

定義

再帰と一時

$i$ から出発して $i$ に戻る確率 $f_{ii} = P(\text{ある } n \ge 1 \text{ で } X_n = i \mid X_0 = i)$ が $1$ なら再帰的、 $1$ 未満なら一時的という。再帰的で、戻るまでの時間 $T_i$ の平均 $m_i = \operatorname{E}_i[T_i]$ が有限なら正再帰、無限なら零再帰という。

定理・法則

類の性質

条件

$S$ は可算。類は互いに到達可能な関係による同値類。

主張

同じ類の状態は、周期、再帰か一時か、正再帰か零再帰かが一致する。 $i$ が再帰的であることと $\sum_{n} p_{ii}^{(n)} = \infty$ は同値である。

要点

有限状態の既約な連鎖では、すべての状態が正再帰になる。無限状態では、1次元の対称ランダムウォークのように既約でも零再帰、非対称なら一時的になる場合がある。

定常分布の存在と収束

定義

定常分布

$\pi_j \ge 0$ 、 $\sum_j \pi_j = 1$ 、 $\boldsymbol{\pi} P = \boldsymbol{\pi}$ （すなわち $\pi_j = \sum_i \pi_i p_{ij}$ ）を満たす行ベクトル $\boldsymbol{\pi}$ を定常分布という。 $P^{\mathsf T}$ の固有値 $1$ の固有ベクトルを、成分の和が $1$ になるよう正規化したものにあたる（固有値と固有ベクトル）。

定理・法則

定常分布の一意性と収束（エルゴード定理）

条件

連鎖は既約で正再帰（有限状態なら既約だけでよい）。

主張

定常分布はただ1つ存在し、 $\pi_j = 1/m_j$ （ $m_j$ は $j$ への平均再帰時間）。
さらに非周期なら、任意の $i$ で $\lim_{n\to\infty} p_{ij}^{(n)} = \pi_j$ 。
周期的でも、時間平均 $\dfrac{1}{n}\sum_{k=1}^{n}\mathbf{1}_{\{X_k = j\}}$ は確率1で $\pi_j$ に収束する。

要点

周期的な連鎖では $p_{ij}^{(n)}$ は収束しない。 $P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ は定常分布 $(1/2, 1/2)$ をもつが、 $P^n$ は $I$ と $P$ を交互にとる。

定理・法則

詳細つり合い

条件

確率分布 $\boldsymbol{\pi}$ がすべての $i, j$ で $\pi_i p_{ij} = \pi_j p_{ji}$ を満たす。

主張

$\boldsymbol{\pi}$ は定常分布である。

要点

$\sum_i \pi_i p_{ij} = \sum_i \pi_j p_{ji} = \pi_j$ から出る。逆は成り立たず、詳細つり合いを満たさない定常分布もある。満たす連鎖を可逆という。

定常分布と $P^n$ の計算例

計算例

2状態の連鎖

$P = \begin{pmatrix} 1-a & a \\ b & 1-b \end{pmatrix}$ （ $0 < a, b < 1$ ）の定常分布と $P^n$ を求めよ。 $a = 0.3,\ b = 0.2$ の値も書け。

解答

$\pi_1 a = \pi_2 b$ と $\pi_1 + \pi_2 = 1$ から $\boldsymbol{\pi} = \left(\dfrac{b}{a+b}, \dfrac{a}{a+b}\right)$ 。 $P$ の固有値は $1$ と $1 - a - b$ で、

P^n = \frac{1}{a+b}\begin{pmatrix} b & a \\ b & a \end{pmatrix} + \frac{(1-a-b)^n}{a+b}\begin{pmatrix} a & -a \\ -b & b \end{pmatrix}

$a = 0.3,\ b = 0.2$ なら $\boldsymbol{\pi} = (0.4, 0.6)$ 、第2項の係数は $0.5^n$ で、 $P^n$ の各行は $(0.4, 0.6)$ に収束する。

検算

$n = 0$ で $I$ 、 $n = 1$ で $P$ に戻る。 $a = 0.3,\ b = 0.2$ で $n = 2$ なら、状態1から出発して状態1にいる確率は $0.4 + 0.6 \times 0.25 = 0.55$ で、 $P^2$ の $(1,1)$ 成分 $0.7^2 + 0.3 \times 0.2 = 0.55$ と一致する。

計算例

3状態の連鎖と平均再帰時間

$P = \begin{pmatrix} 1/2 & 1/2 & 0 \\ 1/4 & 1/2 & 1/4 \\ 0 & 1/2 & 1/2 \end{pmatrix}$ の定常分布と、状態1への平均再帰時間を求めよ。

解答

状態1と2、2と3の間でだけ移るので、詳細つり合いを試す。 $\pi_1 \cdot \tfrac12 = \pi_2 \cdot \tfrac14$ から $\pi_2 = 2\pi_1$ 、 $\pi_2 \cdot \tfrac14 = \pi_3 \cdot \tfrac12$ から $\pi_3 = \pi_1$ 。和を $1$ にして $\boldsymbol{\pi} = (1/4, 1/2, 1/4)$ 。既約で有限なので、平均再帰時間は $m_1 = 1/\pi_1 = 4$ 。

検算

$\boldsymbol{\pi} P$ を計算すると $(1/8 + 1/8,\ 1/8 + 1/4 + 1/8,\ 1/8 + 1/8) = (1/4, 1/2, 1/4)$ で $\boldsymbol{\pi}$ に戻る。直接、状態2・3から1に着くまでの平均時間 $h_2, h_3$ を一歩目で分けて解くと $h_2 = 6,\ h_3 = 8$ で、 $m_1 = 1 + \tfrac12 \cdot 0 + \tfrac12 h_2 = 4$ と一致する。

吸収確率と平均吸収時間

$p_{ii} = 1$ の状態を吸収状態という。吸収確率や吸収までの平均時間は、最初の1ステップで場合分けする方法（一歩目解析）で連立方程式にする。 $h_i = P(\text{状態 } N \text{ に吸収} \mid X_0 = i)$ なら、吸収状態でない $i$ で $h_i = \sum_j p_{ij} h_j$ 、境界で $h_N = 1$ 、他の吸収状態で $0$ とおく。

計算例

破産問題

所持金 $i$ （ $0 \le i \le N$ ）から、確率 $p$ で $1$ 増え、確率 $q = 1 - p$ で $1$ 減る賭けを、所持金が $0$ か $N$ になるまで続ける。 $N$ に達する確率 $h_i$ を求めよ。 $p = 0.4,\ N = 10,\ i = 5$ の値と、 $p = 1/2$ のときの平均継続時間も求めよ。

解答

$h_i = p h_{i+1} + q h_{i-1}$ 、 $h_0 = 0$ 、 $h_N = 1$ 。特性方程式 $p r^2 - r + q = 0$ の解は $1$ と $q/p$ なので、 $p \ne q$ では

h_i = \frac{1 - (q/p)^i}{1 - (q/p)^N}

$p = 1/2$ では重解になり $h_i = i/N$ 。 $p = 0.4$ なら $q/p = 1.5$ で $h_5 = \dfrac{1 - 1.5^5}{1 - 1.5^{10}} = \dfrac{1}{1 + 1.5^5} \approx 0.116$ 。

平均継続時間 $D_i$ は $D_i = 1 + \tfrac12 D_{i+1} + \tfrac12 D_{i-1}$ 、 $D_0 = D_N = 0$ を満たし、 $D_i = i(N - i)$ 。 $N = 10,\ i = 5$ なら $25$ 。

検算

$h_0 = 0$ 、 $h_N = 1$ を満たす。 $p \to 1/2$ で $q/p \to 1$ とすると、ロピタルの定理で $h_i \to i/N$ に近づく。 $D_i = i(N-i)$ を漸化式に入れると $1 + \tfrac12\{(i+1)(N-i-1) + (i-1)(N-i+1)\} = i(N-i)$ が成り立つ。

答案でよくある誤り

1
推移確率行列の行と列を取り違える。 $p_{ij}$ は $i$ から $j$ への確率で、行の和が $1$ 。分布は行ベクトルとして $\boldsymbol{\pi}_0 P$ と右から掛ける。列ベクトルで書く教科書では転置した行列を使うので、どちらの流儀かを確かめる。
2
定常分布を $P\boldsymbol{\pi}^{\mathsf T} = \boldsymbol{\pi}^{\mathsf T}$ で解く。これは右固有ベクトルで、行の和が $1$ の $P$ では成分がすべて等しいベクトルになる。 $\boldsymbol{\pi} P = \boldsymbol{\pi}$ （左固有ベクトル）を解く。
3
定常分布が存在すれば $P^n$ が収束すると考える。周期的な連鎖では収束しない。収束には既約性と非周期性を確かめる。
4
$\boldsymbol{\pi} P = \boldsymbol{\pi}$ だけを解いて正規化を忘れる。方程式は1本が従属なので、 $\sum_j \pi_j = 1$ を加えて解を決める。
5
可約な連鎖で定常分布が1つに決まると考える。閉じた類が2つ以上あれば、それぞれの類の定常分布の凸結合がすべて定常分布になる。

マルコフ連鎖が出た院試の過去問

院試hubが年度別解説の大問を分類した集計から、この単元の内容を扱う出題を挙げる。問題文は各大学の公式過去問で確かめ、解き方は各年度の解説ページで読める。