【統計検定準1級】マルコフ連鎖

はじめに

この記事ではマルコフ連鎖（Markov chain）を扱います。統計検定準1級の出題範囲表の一部です。

大項目	中項目	項目（学習しておくべき用語）例
マルコフ連鎖と確率過程の基礎	マルコフ連鎖	推移確率、既約性、再帰性、定常分布

だいたいこれくらいの範囲を簡単にカバーできればokとします。

目次

はじめに

マルコフ連鎖

推移確率行列

既約性

再帰性

定常分布

参考文献

マルコフ連鎖

確率変数がとる値の集合 $S$ を状態空間（state space）といい、その要素を状態（state）と呼びます。状態 $i,j \in S$ に対して確率 $p_{ij}$ は、 $p_{ij} \geq 0$ で $\sum_{j \in S} p_{ij} =1$ を満たします。ここで $i,j,x_{n-1},\cdots.x_{0} \in S$ に対して、

${ \begin{eqnarray} P(X_{n+1} =j|X_n =i) = p_{ij} \tag{1} \\ P(X_{n+1} =j|X_n =i,X_{n-1}=x_{n-1},\cdots,X_0=x_0) = p_{ij} \tag{2} \end{eqnarray} }$

を仮定します。(1)(2)を満たす確率過程を（離散）マルコフ連鎖（Markov chain）と呼びます*1。

(1)は状態 $i$ から状態 $j$ に移る確率が $p_{ij}$ で与えられており、 $p_{ij}$ を推移確率（transition probability）と呼びます。(2)は推移確率が直前の状態（ $X_n =i$ ）のみに依存し、過去の履歴（ $X_{n-1}=x_{n-1},\cdots,X_0=x_0$ ）に依存しないことを意味します。過去の履歴が直前の状態に集約される、とも言えます。この性質をマルコフ性（Markov property）と呼びます。このマルコフ性によって、(2)の同時分布は(1)の推移確率と初期分布（ $P(X_0 =i)$ ）が与えられれば計算することが可能です。

推移確率行列

$(i,j)$ 成分が $p_{ij}$ からなる行列を推移確率行列（transition probability matrix）と呼びます。第 $i$ 成分が $1$ で他は $0$ からなるベクトルを $e_i$ とすると、 $n$ 回の推移によって状態 $i$ から状態 $j$ に推移する確率は、

${ \begin{eqnarray} P(X_{n} =j|X_0 =i) = e_i^{\mathrm{T}} \mathbf{P}^n e_j \tag{3} \end{eqnarray} }$

と表されます。

$S=\{0,1,2,\cdots \}$ の場合、推移確率行列は、

${ \begin{eqnarray} \mathbf{P} = \begin{bmatrix} p_{00} & p_{01} & p_{02} & \cdots \\ p_{10} & p_{11} & p_{12} & \cdots \\ p_{20} & p_{21} & p_{22} & \cdots \\ \vdots & \vdots & \vdots & \ddots \tag{4} \end{bmatrix} \end{eqnarray} }$

ただし $\sum_{j \in S} p_{ij} =1$ です。

$X_n$ が2つの値 $0,1$ だけをとる、つまり $S=\{0,1\}$ の場合、推移確率行列は、

${ \begin{eqnarray} \mathbf{P} = \begin{bmatrix} p_{00} & p_{01} \\ p_{10} & p_{11} \tag{5} \end{bmatrix} \end{eqnarray} }$

ただし $p_{00} + p_{01} = p_{10} + p_{11} = 1$ を満たします。

既約性

状態 $i,j\in S$ に対して $P(X_n = j|X_0 = i) >0$ となる正の整数 $n$ がとれるとき、 $i$ から $j$ へ到達可能であるといい、 $i \rightarrow j$ と表します。 $i$ と $j$ を入れ替えても成立するとき、 $i$ と $j$ は相互到達可能であるといい、 $i \leftrightarrow j$ と表します。

任意の状態 $i,j\in S$ が相互到達可能であるとき、マルコフ連鎖は既約（irreducible）である、といいます。

再帰性

マルコフ連鎖では、ある状態が繰り返し出現することがあります。 $P(X_n=i|X_0=i)>0$ となる整数 $n$ の最大公約数を状態 $i$ の周期（period）と呼び、 $d(i)$ と定義します。そのような $n$ が存在しないときは $d(i)=0$ です。 $d(i)=1$ のときつまり周期が $1$ のとき、状態 $i$ は非周期的（aperiodic）であり、 $d(i)>1$ のとき状態 $i$ は周期的（periodic）です。すべての状態が非周期的であるときマルコフ連鎖は非周期的となります。

マルコフ連鎖の中には、繰り返し実現する確率が1、つまり同じ状態に必ず戻るものがあります。必ず戻ることを再帰的（reccurent）だと呼びます。再帰性を定義するため、次の2つの記号を導入します。

${ \begin{eqnarray} p_{ij}^{(n)} &=& P(X_{n} =j|X_0 =i) \tag{6} \\ f_{ij}^{(n)} &=& P(X_{n} =j,X_k \neq j, k=1,2,\cdots,n-1|X_0 =i) \tag{7} \end{eqnarray} }$

(6)は状態 $i$ から出発して $n$ 回目に状態 $j$ に到着する確率を表します。ただし途中で何回でも $j$ に到着しても問題ありません。これに対して(7)は、状態 $i$ から出発して $n$ 回目で初めて状態 $j$ に到着する確率です。さらに次の確率を導入します。

${ \begin{eqnarray} f_{ij} = \sum_{n=1}^{\infty} f_{ij}^{(n)} \tag{8} \end{eqnarray} }$

これは状態 $i$ を出発していつかは状態 $j$ に到着する確率を表します。したがって、 $f_{ii}$ は $i$ から出発していつかは $i$ に戻ってくる全確率です。

$f_{ii}$ を使って、再帰性を定義すると、

$f_{ii}=1$ ならば再帰的
$f_{ii}<1$ ならば非再帰的（一時的）

となります。

定常分布

十分に長い時間が経過したとき、マルコフ連鎖の状態の確率分布はどのようになるのでしょうか。

$π_i,i \in S$ を $\sum_{i \in S} π_i = 1$ なる確率分布とします。任意の $j \in S$ に対して $\sum_{i \in S}π_i p_{ij} = π_j$ が成立するとき、 $π_i,i \in S$ をマルコフ連鎖の定常分布（stationary distribution）と言います。

時点 $n$ で定常分布 $π_i,i \in S$ に至ったと仮定します。すなわち任意の $j \in S$ に対して、

${ \begin{eqnarray} P(X_n = j) = π_{j} \tag{9} \end{eqnarray} }$

です。このとき、

${ \begin{eqnarray} P(X_{n+1} = j) &=& \sum_{i \in S} P(X_n = i, X_{n+1} =j ) \\ &=& \sum_{i \in S} P(X_n = i)P(X_{n+1}=j|X_n =i) \\ &=& \sum_{i \in S} π_i p_{ij} \\ &=& π_j \tag{10} \end{eqnarray} }$

となり、 $n$ 以降はすべて定常分布になります。
これを行列で表します。推移行列が $\mathbf{P}$ のマルコフ連鎖が時点 $n$ に状態 $i$ にある確率を $π_n(i)$ として、 $\mathbf{π_n}=(π_n(1),π_n(2),\cdots)$ と表します。(10)の状態では、次の漸化式