Markov Chains and Monte Carlo Methods 02日目

Ioana A. Cosma and Ludger Evers, Markov Chains and Monte Carlo Methods
http://users.aims.ac.za/~ioana/notes.pdf
CC-by-nc-sa 2.5

• • • 1.3 General state space Markov chains
      • Definition 1.23 (Markov chain)
      • Example 1.15 (Gaussian random walk on R\mathbb{R})
      • Definition 1.24 (Irreducibility)
      • Example 1.16 (Gaussian random walk (continued))
      • Definition 1.25 (Recurrence)
      • Definition 1.26 (Harris Recurrence)
      • Definition 1.27 (Stationary distribution)
      • Proposition 1.28 (証明略)
      • Definition 1.29 (Detailed balance)

1.3 General state space Markov chains

$|S| > |\mathbb{N}|$の場合の議論を始める. より一般的な場合にも定義できるのだが,ここでは$S=\mathbb{R}^d$とする.

Definition 1.23 (Markov chain)

$\{X_t\}$はdiscrete time stochastic processで, state spaec $S$は$S=\mathbb{R}^d$とする. $X$ がMarkov property を満たす
$\Leftrightarrow$

$$\forall A \in \mathcal{F}.\ P(X_{t+1}\in A| X_0=x_0,...,X_t=x_t)=P(X_{t+1}\in A|X_t=x_t)$$

ただし$\mathcal{F}$は$S$の可測集合族とする.
以後,Markov chainはhomogeneousとする.すなわち $(X_{t+1}\in A|X_t=x_t)$は$t$によらない. このときtransition kernel $K: S \times S \rightarrow \mathbb{R}_0^+$によって

$$P(X_{t+1}\in A| X_t=x_t) = \int_A K(x_t, x_{t+1})dx_{t+1}\ \ \ \ \ (1.3)$$
として得られる. $K(x, y)$というのは$X_t=x_t$が与えられたときの$X_{t+1}$のconditional probability densityである. def. 1.8における$K(i, j)=k_{ij}$というのはdiscrete spaceにおけるconting measureであって,(1.3)の式に合致する.
さらに
$$\begin{aligned}&P(X_{t+m}\in A|X_t=x_t) \\&= \int_A \int_S \cdots \int_S K(x_t, x_{t+1})K(x_{t+1},x_{t+2})\cdots K(x_{t+m-1},x_{t+m})dx_{t+1}\cdots dx_{t+m-1}dx_{t+m}\end{aligned}$$
だから,$m$-step transiton kernelは
$$K^{(m)}(x_0, x_m) = \int_S\cdots \int_SK(x_t,x_{t+1})\cdots K(x_{m-1},x_m)dx_{m-1}\cdots dx_1$$
であり,
$$P(X_{t+m}\in A| X_t=x_t) = \int_A k^{(m)} (x_t, x_{t+m})dx_{t+m}$$
と簡潔に書ける.

Example 1.15 (Gaussian random walk on $\mathbb{R}$)

$\mathbb{R}$上のrandom walkを

$$X_{t+1} = X_t + E_t, \ \ E_t \sim N(0, 1)$$
とすると,
$$X_{t+1}|X_{t} = x_t \sim N(x_t, 1)$$
と同値. $Et_t$は$X_0, E_1,...,E_{t-1}$と独立とし, $X_0 \sim N(0,1)$とすれば,
$$\begin{aligned} P(X_{t+1}\in A| X_t=x_t,...,X_0=x_0) &= P(E_t\in A-x_t|X_t=x_t,...,X_0=x_0) \\ &=P(E_t\in A-x_t)=P(X_{t+1}\in A|X_t=x_t) \end{aligned}$$
よって$X$はMarkov chainであり,しかも
$$P(X_{t+1}\in A| X_t=x_t) = P(E_t \in A - x_t) = \int_A \phi(x_{t+1}-x_t)dx_{t+1}$$
である.ただし$\phi(z)=\frac{1}{\sqrt{2\pi}}\exp(-\frac{1}{2}z^2)$である.したがって$K(x, x_{t+1}) = \phi(x_{t+1}-x_t)$.
$m$-step transition kernelは(1.3)によって計算できるが,非常に複雑になる. それよりも
$$X_{t+m} = X_t + E_t + ... + E_{t+m-1}$$
を利用すれば,$X_{t+m} |X_t = x_t \sim N(x_t, m)$が成立して,
$$P(X_{t+m}\in A| X_t=x_t) = P(X_{t+m}-X_t\in A-x_t) = \int_A \frac{1}{\sqrt{m}}\phi \left(\frac{x_{t+m}-x_t}{\sqrt{m}}\right)dx_{t+m}$$
したがって
$$K^{(m)}(x_t, x_{t+m}) = \frac{1}{\sqrt{m}}\phi \left(\frac{x_{t+m}-x_t}{\sqrt{m}} \right)$$
が$m$-step kernelとして得られる.

Definition 1.24 (Irreducibility)

$S$上の分布$\mu$が与えられて, Markov chain $X$が$\mu$-irreducibleである
$\Leftrightarrow$

$$P(X_{t+m}\in A| X_t=x) = \int_A K^{(m)}(x, y)dy > 0$$
が任意の$\mu (A) > 0$なる$A \in \mathcal{F}$と任意の$x \in S$に成立するような$m \in \mathbb{N}_0$が存在するとき$\mu$-irreducibleといい,特に任意の$A$に$m=1$で成立するときstrongly $\mu$-irreducibleという.

Example 1.16 (Gaussian random walk (continued))

ex. 1.15で$X_{t+1}|X_t = x_t \sim N(x_t, 1)$を見た. $P(X_{t+1}\in A|X_t=x_t)>0$が任意のnullでない$A$に成立するから,これは任意のcontinuous distributionにstrongly irreducibleである.

periodicity, recurrence, そしてtransienceのような概念を$S$が連続的なMakov chainに導入するため, atomsやsmall setsのような概念を導入する必要があって,これらはこのノートの範囲を超えるので,recurrenceのみを一般化する.
section 1.2.3で定義した$|S|\leq |\mathbb{N}|$の場合のrecurrenceとは,全てのstateがそれを初期のstateとしたとき,平均して無限回訪れられることであった. $S$が連続である場合には,あるstate一点ではなく,stateの集合たちを考えることになる. $V_A=\sum_{t=0}^\infty 1_{\{X_t \in A\}}|X_0=x$として,$A$が訪れられる回数をあらわす. expected valueを考えると

$$E[V_A|X_0=x] = E[\sum_{t=0}^\infty 1_{\{X_t \in A\}}|X_0=x] = \sum_{t=0}^\infty E(1_{\{X_t \in A\}}|X_0=x) =\sum_{t\geq 0} \int_A K^{(t)}(x, y)dy$$
である. recurrenceをMarkov chain全体に定義する前に,集合のrecurrenceを定義する.

Definition 1.25 (Recurrence)

(a) $A \subset S$がMarkov chain $X$においてrecurrentである
$\Leftrightarrow$ 任意の$x \in A$に

$$E(V_A|X_0=x) = \infty$$
(b) Markov chain $X$がrecurrent
$\Leftrightarrow$
(i) $X$はある分布$\mu$に対して$\mu$-irreducibleであって,かつ
(ii) 任意の$A \in \mathcal{F}, \mu(A) > 0$はrecurrent

定義より,recurrent setとは平均して無限回訪れられる集合であって,より強い命題に,その集合が無限回訪れられる確率が1であるというのがある. この強い性質によって定義できるrecurrenceをHarris Recurrenceという.

Definition 1.26 (Harris Recurrence)

(a) $A \subset S$が$X$にHarris-recurrentである
$\Leftrightarrow \forall x \in A P(V_A=\infty|X_0=x)=1$
(b) Markov chain $X$がHarris-recurrent
$\Leftrightarrow$
(i) $X$はある$\mu$に$\mu$-irreducible
(ii) 任意の$A \in \mathcal{F}, \mu(A) > 0$はHarris-recurrent

Harris recurrenceはrecurrenceを導くことは明らかで,discreteの場合2つは一致する.
どちらの概念も成立を証明することは非常に困難だが,あるMarkov chainがirreducibleで唯一のstationary distributionをもつならばrecurrentであるという命題を主張する. その前に,stationaryを定義する.

Definition 1.27 (Stationary distribution)

分布PDF$f_{\mu}$をもつ分布$\mu$がtransition kernel $K$をもつ$X$のstationary distibutionである
$\Leftrightarrow \forall y \in S.\ \ f_\mu(y) = \int_S f_\mu(x)K(x, y)dx$

Proposition 1.28 (証明略)

$X$が$\mu$-irreducible Markov chainで,$\mu$を唯一のstationary distibutionにもつなら,$X$はrecurrentである.

また,def. 1.27によってstationarityを確かめるのは困難なので,discreteの場合と同様により簡単な十分条件を定義する.

Definition 1.29 (Detailed balance)

transition kernel $K$がdistribution $\mu$にdetailed balanceである
$\Leftrightarrow \forall x,y \in S. \ \ f_\mu(x)K(x, y)=f_\mu(y)K(y,x)$

theorem 1.22と同様に,$\mu$によってdetailed balanceなMarkov chain $X$はtime-reversibleで$\mu$は$X$のstational distibutionである.