マルコフ連鎖モンテカルロ法(3)マルコフ連鎖について振り返る

はじめに

前回2回は頻用される2つのアルゴリズム、MHアルゴリズムとGibbsサンプラーについて述べた。しかし、まだMCMCのそもそもの前提条件についてを述べていなかった。今回はマルコフ連鎖についての話をまとめる。

マルコフ連鎖

時点 $t(t = 1, 2, ...)$ にしたがって状態が推移するような確率変数 $x^{(t)}$ の系列を考える。この系列を確率過程という。また、 $x^{(t)}$ がとりうる値すべてからなる集合 $S$ を状態空間という。 $t$ において状態が $i \in S$ である場合に次の $t+1$ において状態 $j \in S$ となる確率は、 $t-1$ 以前の状態の履歴も含めた条件付き確率として

$\displaystyle P(x^{(t+1)} = j | x^{(1)} = i_1, x^{(2)} = i_2, ..., x^{(t)} = i)$

と定義できる。
さて、もし上記の確率が $t$ の状態だけに依存して決まる（ $t-1$ 以前の履歴に依存しない）、つまり

$\displaystyle P(x^{(t+1)} = j | x^{(1)} = i_1, x^{(2)} = i_2, ..., x^{(t)} = i) = P(x^{(t+1)} = j | x^{(t)} = i)$

となるとき、確率過程はマルコフ連鎖と呼ばれる。
$i$ から $j$ への推移確率を $P(x^{(t+1)} = j|x^{(t)} = i) = P_{ij})$ とし、同じ状態にとどまる確率 $P_{ii}$ も含めすべての推移確率を並べた行列 $P = (P_{ij})$ を推移確率行列という。今は離散的な状態空間を考えているが、連続的な場合も考えることができ、その場合も含め一般的には推移核と呼ばれる。
推移確率行列を用いた状態推移の表現を考えよう。初期状態のベクトルを $\pi^{(1)}$ とすると、次の状態 $\pi^{(2)}$ への推移は推移確率行列 $P$ を掛けることで

$\displaystyle \pi^{(1)} P = \pi^{(2)}$

と書くことができる。続く $\pi^{(3)}$ への推移には再度 $P$ を掛ければよい。したがって時点 $t+1$ の確率分布は一般的に

$\displaystyle \pi^{(t)} P = \pi^{(t+1)}, \\ あるいは \pi^{(1)} P^t = \pi^{(t+1)}$

と表せる（ $P^t$ は、転置ではなく $t$ 乗を表す）。
状態 $\pi^{(t)}$ と $\pi^{(t+1)}$ は一般的には異なるが、ある条件を満たすマルコフ連鎖においては1つの分布に収束し、推移確率行列に従ってもそれ以上分布が変化しなくなる。つまり

$\displaystyle \pi P = \pi$

が成立する。収束先の $\pi$ を、推移確率行列 $P$ をもつマルコフ連鎖の定常分布という。MCMCは、直接サンプリングが困難な確率分布とこの定常分布とが等しくなるように推移確率行列（あるいは推移核）を設計して、目的とするサンプルを得るための方法である。

定常分布に収束する条件

マルコフ連鎖が定常分布に収束する条件として「エルゴード性」と呼ばれる性質がある。このエルゴード性を構成する3つの概念をまずはまとめる。

1.既約的
状態 $i$ から $j$ へ有限回の推移で到達できる（確率が0でない）とき、 $i$ は $j$ へ到達可能であるという。推移確率で表現すると $P^{t}_{ij} > 0$ である。逆方向にも有限回の推移で到達できるなら（ $P^{t^{'}}_{ji} > 0$ ）、 $i$ と $j$ は互いに到達可能であるという。
状態空間 $S$ のすべての要素の組が互いに到達可能であるとき、そのマルコフ連鎖は「既約的」であるという。

2.非周期的
周期とは、状態 $i$ から $j$ への推移の中で同じ推移のパターンが何度も繰り返されるような場合、そのパターン1つの時点間の長さのことをいう。どの状態に関しても周期が1、つまり同じパターンの繰り返しが存在しないようなマルコフ連鎖は「非周期的」であるという。

3.正再帰的
状態 $i$ から再び $i$ へ戻ってくるまでの最小の推移数を $T_i$ とするとき、 $P(T_i < \infty) = 1$ 、つまり確実に有限回数で戻ってくるような場合、マルコフ連鎖は「再帰的」という。さらに $E[T_i] < \infty$ であるとき「正再帰的」という。