マルコフ連鎖

数理統計　第12章 §12.5　★★★ 推移確率行列・定常分布・推移確率の最尤推定と尤度比検定。1級で大問として出た唯一の確率過程

定義と Chapman–Kolmogorov の等式

条件は「次の状態の分布は、現在の状態だけで決まり、それ以前の履歴によらない」という意味である。乗法定理を繰り返すと、経路の確率は

$$P(X_0=i_0,X_1=i_1,\dots,X_n=i_n)=P(X_0=i_0)\,p_{i_0i_1}p_{i_1i_2}\cdots p_{i_{n-1}i_n}\tag{12.17}$$

と推移確率の積になる。この式から、この節の後半で推移確率の尤度を書く。

$n$ 歩後の推移確率 $p^{(n)}_{ij}=P(X_{n}=j\mid X_0=i)$ を考える。途中の時刻 $k$ にいる状態で場合を分けると

$$p^{(n)}_{ij}=\sum_{l=1}^mp^{(k)}_{il}\,p^{(n-k)}_{lj}\tag{12.18}$$

を得る（Chapman–Kolmogorov の等式）。これは行列の積の成分の式そのものなので、$n$ 歩の推移確率行列は $\bm P^n$ である。初期分布を行ベクトル $\bm\pi_0$ で表す。すると $X_n$ の分布は $\bm\pi_0\bm P^n$ になる。

定常分布と極限定理

初期分布が定常分布なら、$X_1$ の分布は $\bm\pi\bm P=\bm\pi$ で、以後ずっと同じままである。

すべての状態が互いに行き来できる連鎖を既約と呼ぶ。任意の $i,j$ に対して、$p^{(n)}_{ij}>0$ となる歩数がある、ということである。状態 $i$ に戻れる歩数 $\{n:p^{(n)}_{ii}>0\}$ の最大公約数を、その状態の周期と呼ぶ。周期が 1 のとき非周期的という。

有限状態で既約かつ非周期的な連鎖では、ある $N$ について $\bm P^N$ のすべての成分が正になることが知られている。次の定理はこの条件から出発する。

証明

行ベクトル $\bm d$ の大きさを $\lVert \bm d\rVert _1=\sum_j\lvert d_j\rvert$ で測る。$\bm Q=\bm P^N$ とおく。成分の和が 0 の行ベクトル $\bm d$ について、次を示す（2つの確率ベクトルの差がこれに当たる）。

$$\lVert \bm d\bm Q\rVert _1\le(1-m\varepsilon)\lVert \bm d\rVert _1.$$

$\sum_id_i=0$ なので、$\sum_id_iq_{ij}=\sum_id_i(q_{ij}-\varepsilon)$ と書ける。$q_{ij}-\varepsilon\ge0$ だから

$$\lVert \bm d\bm Q\rVert _1=\sum_j\Bigl\lvert\sum_id_i(q_{ij}-\varepsilon)\Bigr\rvert\le\sum_i\lvert d_i\rvert \sum_j(q_{ij}-\varepsilon)=(1-m\varepsilon)\lVert \bm d\rVert _1.$$

また推移確率行列自身についても、同じ計算で $\varepsilon=0$ とした $\lVert \bm d\bm P\rVert _1\le\lVert \bm d\rVert _1$ が成り立つ。

1. 一意性。$\bm\pi,\bm\pi'$ がともに定常分布なら、その差は $\bm d\bm Q=\bm d$ を満たす。よって $\lVert \bm d\rVert _1\le(1-m\varepsilon)\lVert \bm d\rVert _1$ である。$m\varepsilon>0$ より $\bm d=\bm 0$。
2. 存在と収束。$\bm\mu_n=\bm\pi_0\bm P^n$ とおく。$n=kN+r$（$0\le r<N$）と書く。番号 $\ell\ge n$ に対して

$$\lVert \bm\mu_\ell-\bm\mu_n\rVert _1=\lVert (\bm\mu_{\ell-n}-\bm\pi_0)\bm P^r\bm Q^k\rVert _1\le2(1-m\varepsilon)^k$$

なので、$\{\bm\mu_n\}$ は Cauchy 列であり、極限 $\bm\pi$ を持つ。$\bm\mu_{n+1}=\bm\mu_n\bm P$ で極限をとると $\bm\pi=\bm\pi\bm P$ で、極限は定常分布である。初期分布によらず同じ極限になることは、2つの初期分布の差に上の縮小を使えば分かる。

この証明から、$\bm\pi_0\bm P^n$ は $\bm\pi$ に指数関数的な速さで近づくことも分かる。実際の速さは、推移確率行列の2番目に大きい固有値の絶対値で決まる（例題 12.7）。既約だが周期的な連鎖では、定常分布は1つだが $\bm P^n$ は収束しない（確認テスト 12.5-3）。

既約な有限状態の連鎖では、さらに次が成り立つ（証明は省く）。

• 状態 $i$ から出発して初めて同じ状態に戻るまでの歩数の期待値は、$1/\pi_i$ である。
• 関数 $g$ について、次の時間平均は確率1で $\sum_j\pi_jg(j)$ に収束する（エルゴード定理）。

$$\frac1n\sum_{k=1}^ng(X_k).$$

後者は、長い時系列で状態 $j$ にいた時間の割合が $\pi_j$ に近づくことを意味する。第11章のマルコフ連鎖モンテカルロ法は、これを使って定常分布からの標本を作る。

到達確率と到達時間

吸収状態（$p_{ii}=1$ の状態）を含む連鎖では、§12.2 の第一歩解析がそのまま使える。吸収状態の集合を $A$ とする。状態 $i$ から出発して吸収されるまでの歩数の期待値を、$\mu_i$ とする。最初の1歩で場合を分けて

$$\mu_i=1+\sum_{j\notin A}p_{ij}\mu_j\qquad(i\notin A),\qquad \mu_i=0\quad(i\in A)\tag{12.19}$$

を得る。特定の吸収状態 $a$ に吸収される確率 $h_i$ も、次の連立一次方程式の解になる。

$$h_i=\sum_jp_{ij}h_j\quad(i\notin A),\qquad h_a=1,\qquad h_b=0\quad(b\in A,\ b\ne a).$$

推移確率の最尤推定

1本の観測列 $x_0,x_1,\dots,x_n$ から推移確率を推定する。記号を次のように定める。

• $n_{ij}$：推移 $i\to j$ の回数。つまり「状態 $i$ の直後に状態 $j$ が来た回数」。
• $n_{i\cdot}=\sum_jn_{ij}$：状態 $i$ から出た推移の回数。

経路の確率 (12.17) を、初期状態 $X_0=x_0$ で条件付けた尤度は

$$L(\bm P)=\prod_{k=1}^np_{x_{k-1}x_k}=\prod_{i=1}^m\prod_{j=1}^mp_{ij}^{\,n_{ij}}\tag{12.20}$$

である（同じ推移 $i\to j$ が $n_{ij}$ 回現れるので、その数だけ推移確率が掛かる）。

証明

対数尤度は $\ell(\bm P)=\sum_i\sum_jn_{ij}\log p_{ij}$ で、行ごとの和 $\ell_i=\sum_jn_{ij}\log p_{ij}$ に分かれる。制約も行ごとに独立なので、行ごとに最大化すればよい。Lagrange 乗数 $\lambda_i$ を使って次の関数を作る。

$$G_i=\sum_jn_{ij}\log p_{ij}-\lambda_i\Bigl(\sum_jp_{ij}-1\Bigr).$$

推移確率で偏微分して 0 とおくと、$n_{ij}/p_{ij}=\lambda_i$、すなわち $p_{ij}=n_{ij}/\lambda_i$。制約に代入して $\lambda_i=\sum_jn_{ij}=n_{i\cdot}$ を得る。

これが最大であることは、次のことから従う。$\ell_i$ は推移確率の凹関数（対数の非負結合）であり、制約が線形なので停留点が最大値を与える。

行 $i$ の推移の回数 $(n_{i1},\dots,n_{im})$ を考える。これは行和を与えたもとで、多項分布 $\mathrm{Mult}(n_{i\cdot};p_{i1},\dots,p_{im})$ と同じ形の尤度を持つ。したがって推定量 (12.21) は、多項分布の割合の最尤推定量と同じ形である。観測列が長いとき、近似的に次が成り立つ。

$$\hat p_{ij}\approx\mathrm{N}\Bigl(p_{ij},\ \frac{p_{ij}(1-p_{ij})}{n_{i\cdot}}\Bigr)\qquad(n_{i\cdot}\text{ は約 }n\pi_i).$$

独立性の尤度比検定

観測列が実はマルコフ性を持たず、各時刻に独立に同じ分布 $(p_1,\dots,p_m)$ から出ているのではないか、という仮説を考える。

$$H_0:p_{ij}=p_j\quad(\text{すべての行が等しい})$$

を、一般のマルコフ連鎖 $H_1$ に対して検定する。

帰無仮説のもとでは、尤度が $\prod_jp_j^{\,n_{\cdot j}}$（$n_{\cdot j}=\sum_in_{ij}$）となる。最尤推定量は $\hat p_j=n_{\cdot j}/n$ である。対立仮説のもとでは (12.21) である。最大対数尤度の差の2倍は

$$G^2=2\sum_{i,j}n_{ij}\log\frac{n_{ij}}{n_{i\cdot}}-2\sum_{i,j}n_{ij}\log\frac{n_{\cdot j}}{n}=2\sum_{i,j}n_{ij}\log\frac{n_{ij}\,n}{n_{i\cdot}\,n_{\cdot j}}\tag{12.22}$$

となる。自由パラメータの数は、対立仮説で $m(m-1)$、帰無仮説で $m-1$ である。第7章の尤度比検定の漸近理論から、帰無仮説のもとで $G^2$ は近似的にカイ二乗分布に従う。その自由度は次のとおりである。

$$m(m-1)-(m-1)=(m-1)^2.$$

$G^2>\chi^2_{(m-1)^2}(\alpha)$ なら、帰無仮説を棄却する。

式 (12.22) は、分割表の独立性の検定の $G^2$ 統計量と同じ形である。推移の回数の表を「前の状態 × 次の状態」の分割表とみなしたものになっている。

確認テスト

オリジナル

1. 12.5-1 2状態の連鎖（$0<a,b<1$）

$$\bm P=\begin{pmatrix}1-a&a\\b&1-b\end{pmatrix}$$

について、定常分布を求めよ。また次の式を数学的帰納法で示せ。

$$\bm 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}.$$ 2. 12.5-2 状態 $\{1,2,3\}$ の連鎖で、状態3は吸収状態とする。ほかの推移確率は次のとおりである。

$$p_{11}=0.5,\quad p_{12}=0.5,\quad p_{21}=0.3,\quad p_{22}=0.2,\quad p_{23}=0.5.$$

状態1から出発して状態3に吸収されるまでの歩数の期待値を求めよ。3. 12.5-3 状態 $\{0,1,2,3\}$ の連鎖で、推移確率を次のように定める（3個の玉が2つの箱を行き来する模型）。

$$p_{i,i-1}=\frac i3,\qquad p_{i,i+1}=\frac{3-i}{3}.$$

詳細つり合いを使って定常分布を求めよ。また $p^{(n)}_{00}$ が $n\to\infty$ で収束しない理由を述べよ。4. 12.5-4 2状態の観測列 $1,1,2,1,2,2,2,1,1,2$ から推移の回数 $n_{ij}$ を数え、推移確率の最尤推定値を求めよ。