Markov Chains and Monte Carlo Methods 01日目

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
http://creativecommons.org/licenses/by-nc-sa/2.5/za/legalcode

• Chapter 1. Markov Chains
  • 1.1 Stochastic processes
    • • Definition 1.1 (Stochastic process)
      • Definition 1.2 (Sample path)
      • Theorem 1.3 (Kolmogorov)
  • 1.2 Discrete Markov chains
    • 1.2.1 Introduction
      • Definition 1.4 (Discrete Markov chain)
      • Proposition 1.5
      • Example 1.1 (Phone line)
      • Example 1.2 (Random walk on $\mathbb{Z}$)
      • Proposition 1.6
      • Definition 1.7 (Homogeneous Markov Chain)
      • Definition (initial distribution)
      • Definition 1.8 (Transition kernel)
      • Example 1.3 (Phone line(continued))
      • Example 1.4 (Random walk on $\mathbb{Z}$ (continued))
      • Definition 1.9 (m-step transition kernel)
      • Proposition 1.10
      • Example 1.5 (phone line(continued))
    • 1.2.2 Classificaton of states
      • Definition 1.11 (classification of states)
      • Example 1.6
      • Definition 1.12 (Irreducibility)
      • Definition 1.13 (Period)
      • Example 1.7 (Ex. 1.6 continued)
      • Proposition 1.14
    • 1.2.3 Recurrence and transience
      • Definition 1.15 (Recurrence and transience)
      • Proposition 1.16
      • Proposition 1.17
      • Example 1.8 (ex.16, 1.7 continued)
    • 1.2.4 Invariant distribution and equilibrium
      • Definition 1.18 (Invariant distribution)
      • Example 1.9 (Phone line (continued))
      • Example 1.10 (Random walk on Z (continued))
      • Theorem 1.19 (convergence to equilibrium)
      • Example 1.11 (Phone line (continued))
      • Example 1.12
    • 1.2.5 Reversibility and detailed balance
      • definition 1.20 (Time-reversed chain)
      • Example 1.13(Photo line(cont.))
      • Definition 1.21 (Detailed balance, 詳細釣り合い条件)
      • Theorem 1.22
      • Example 1.14

Chapter 1. Markov Chains

1.1 Stochastic processes

Markov chain は無記憶性という特別な性質を持つ確率過程の一種である. Markov chainをよく学ぶため,まずはStochastic processの概念を形式的に定義する.

Definition 1.1 (Stochastic process)

$X$がstochastic processである
$\Leftrightarrow X$は $X=\{X_t: t \in T\}$という，$T$を添字集合とした確率変数の集合であって,domainとrange$X_t: \Omega \rightarrow S$は共通である. $t$は”time”(時刻)で,$S$は”state space”(状態空間)と呼ばれる.

$T$には様々な集合が考えられるが,我々が当面扱うのは$T$が離散的な集合である場合(stochastic processes in discrete time)で,例えば$T \subset \mathbb{N}$や$T\subset \mathbb{Z}$の場合である. ほかには$T=[0, \infty)$のような連続時間における過程や$T=\mathbb{R}^2$のような空間的な過程を考えることもある.
また,$S$がどのような集合かも問題で，$S$が離散的な集合であれば($X_t$がr.v.として離散的であれば)，このような過程を離散過程(discrete process)という.

Definition 1.2 (Sample path)

$\omega\in \Omega$について,$\{X_t(\omega); t \in T\}$を$X$の$\omega$におけるsample path という.

$T=\mathbb{N}_0$ならばsample pathは点列で，$T=\mathbb{R}$ならばsample pathは$\mathbb{R} \rightarrow S$なる関数である.
fig.1.1はsample pathの例である.

stochastic processは$X_t$のそれぞれの分布のみではなく,それらの依存関係によっても特徴づけられる. この依存関係の構造はprocessのfinite-dimentional distributionsによって表現できる．すなわち
$$P(X_{t_1}\in A_1, ..., X_{t_k} \in A_k)$$
という具合である. $S\subset \mathbb{R}$であればjoint distibution function(同時分布)は
$$F_{(t_1,...,t_k)}(x_1,...,x_k) = P(X_{t_1}\in (-\infty, x_1], ..., X_{t_k} \in (-\infty, x_k])$$
と記述できる.

$X$が
$$F_{(t_1,...,t_{j-1},t_j,t_{j+1},...,t_k)}(x_1,...,x_{j-1},+\infty,x_{j+1},...,x_k) = F_{t_1,...,t_{j-1},t_{j+1},...,t_k)}(x_1,...,x_{j-1},x_{j+1},...,x_k)$$
を満たすとき,$X$のfinite dimentional distribution functionはconsistentであるという.
stochastic process $X$について,$X$がfinite dimentional distributionsによって完全に記述できるか否かについての部分的な答えが以下の定理である.

Theorem 1.3 (Kolmogorov)

$F_{(t_1,...,t_k)}$はconsistent なfinite-dimensional distribution functionの族とする. このとき,以下を満たすprobability spaceとstochastic process $X$が存在する.
$$F_{(t_1,..,t_k)}(x_1,...,x_k) = P(X_{t_1}\in(-\infty, x_1], ..., X_{t_k} \in (-\infty, x_k])$$

この定理から,あるprocessのfinite-dimensional distributionsを与えれば，そのprocessを特徴づけられる(本当か?). ただし,あるfinite-dimensional distributionsによって特徴づけられる$X$は一意ではない. しかし,そのdistributionsはたかだか可算個のr.v.によるeventの全てに確率を一意に割り当てることができて，この講義の範囲ではそれで十分である.

1.2 Discrete Markov chains

1.2.1 Introduction

この節ではMarkov chainのうち，とくに$|S|= |\mathbb{N}|$であるときを考える. これをdiscrete Markov processと呼ぶことはすでに述べた($|S|<\infty$の時も含むが,深くは考えない). discrete Markvo processでは$S$を$\mathbb{N}$として一般性を失わない.

Definition 1.4 (Discrete Markov chain)

$X$はdiscrete stochastic processで，しかも時間についてもdiscreteとする.
$X$がMarkov chain (with discrete state space)
$\Leftrightarrow P(X_{t+1}=x_{t+1}|X_t=x_t,...,X_0=x_0) = P(X_{t+1}=x_{t+1}|X_t=x_t)$
またこの性質をMarkov propertyという.

この定義は，ある時刻における状態がその直前の時刻における状態のみによって決まる(確率的)ということの定式化である.

Proposition 1.5

Markov propertyが成立する$\Leftrightarrow$
任意の$k \in \mathbb{N}$と$t_1<...<t_k\leq t$について
$$P(X_{t+1}=x_{t+1}|X_{t_k}=x_{t_k},...,X_{t_1}=x_{t_1})=P(X_{t+1}=x_{t+1}|X_{t_k}=x_{t_k})$$

Example 1.1 (Phone line)

電話線が使われている状態(1とする)と使われていない状態(0とする)があって，毎分この電話線を監監視する過程$\{X_t|t \in \mathbb{N}_0\}$のstochastic processを考える. $\{X_t\}$がMarkov chainと仮定する. すなわち,これまでどれほど長く電話をしていても1分間後にその電話が切れている確率は変わらず，同様にどれほど長く電話がかかってこなかったとしても1分後に電話がかかってきている確率は変わらない仮定する. Markov assumptionは$\{X_t\}$が同じ分布であることを要求しないので,$P(X_{t+1}=1|X_t=0)=0.8$($t$は昼頃), $P(X_{t+1}=1|X_t=0)=0.1$($t$は深夜)というふうに，時刻によって利用のパターンが異なるモデルにも適用できる.

Example 1.2 (Random walk on $\mathbb{Z}$)

$X_0=0$から始まるrandom walkという確率過程を考える. 全ての時刻で，次の時刻に今あるstateにとどまるか,+1進むか,-1進むかを確率的に選ぶ過程である. 現在あるstateにかかわらず,そのstateにとどまる確率を$1-\alpha-\beta$, -1進む確率を$\alpha$, $+1$進む確率を$\beta$とする.$\alpha, \beta \geq 0, \alpha + \beta \leq 1$である.
$X_{t+1}$を,$P(E_t=-1)=\alpha, P(E_t=0)=1-\alpha-\beta, P(E_t=1)=\beta$任意の$t$に成立するr.v. $E_t$によって
$$X_{t+1} = X_t + E_t$$
と記述する.このとき
$$\begin{aligned} &P(X_{t+1}=x_t-1|X_t=x_t)=\alpha, \\ &P(X_{t+1}=x_t|X_t=x_t)=1-\alpha-\beta, \\ &P(X_{t+1}=x_{t}-1|X_t=x_t)=\beta\end{aligned}$$
であることは明らかである.さらに
$$\begin{aligned} &P(X_{t+1}=x_{t+1}|X_t=x_t,...,X_0=x_0) \\ =&P(E_t=x_{t+1}-x_t|E_{t-1}=x_t-x_{t-1},..,E_0=x_1-x_0,X_0=x_o)\\ =&P(E_t=x_{t+1}-x_t) \ \ \ (\because \{E_t\}\text{の独立性})\\ =&P(X_{t+1}=x_{t+1}|X_t=x_t) \end{aligned}$$
が成り立つから,$\{X_t|t\in \mathbb{N}_0$はMarkov chainである.

Markov chainの分布は初期分布$P(X_0=x_0)$によって完全に定まる.さらに*transition probabilitiesを $P(X_{t+1}=x_{t+1}|X_t=x_t)$と定めると,以下の命題が成立する.

Proposition 1.6

discrete Markov chain $\{X_t | t \in \mathbb{N}_0\}$について，
$$P(X_t=x_t,...,X_0=x_0)=P(X_0=x_0)\cdot \prod_{\tau=0}^{t-1} P(X_{\tau+1}=x_{\tau+1}|X_\tau = x_\tau)$$

proof.

$$\begin{aligned} P(X_t=x_t,...,X_0=x_0) =&P(X_0=x_0) \\ &P(X_1=x_1|X_0=x_0)\\ &P(X_2=x_2|X_1=x_1,X_0=x_0) \\ &\cdots \\ &P(X_t=x_t|X_{t-1}=x_{t-1},...,X_0=x_0) \\ &=P(X_0=x_0)\prod_{\tau=0}^{t-1}P(X_{\tau+1}=x_{\tau+1}|X_\tau =x_\tau) \end{aligned}$$

この証明の1つめの等号は全てのr.v.の組に成立するが,2つ目の等号が成立するのはMarkov chain特有である.
Homogeneous Markov chainという更に特別なクラスは$t$によって$X_t$が変化せず，非常に扱いやすい.以下,全てのMarkov chainはhomogeneousとする.

Definition 1.7 (Homogeneous Markov Chain)

Markov chain $\{X_t|t \in \mathbb{N}_0$がhomogeneous
$\Leftrightarrow P(X_{t+1}=j|X_t=i)=p_{ij} \in [0, 1]$という$t$によらない実数$p_{ij}$が,任意の$i,j \in S$に存在する.

Definition (initial distribution)

initial distributionを$\mathbf{\lambda_0}=(P(X_0=i))_{i \in S}$と書く．$\mathbf{K}$と$\mathbf{\lambda_0}$の組によってhomogeneous Markov chainの分布は完全に定まる(後述).

Definition 1.8 (Transition kernel)

$$\mathbf{K}=(k_{ij})_{ij}, \ \ k_{ij}=P(X_{t+1=j}|X_t=i)$$
という行列$\mathbf{K}$をhomogeneous Markov chain $X$のtransition kernelとかtransition matrixという．
$\sum_{j}k_{ij}=\sum_j P(X_{t+1}=j|X_t=i)=P(X_{t+1}\in S|X_t=i)=1$が成立する.

Example 1.3 (Phone line(continued))

$P(X_{t+1}=0|X_t=0)=0.9, \ P(X_{t+1}=1|X_t=0)=0.1$
$P(X_{t+1}=0|X_t=1)=0.3, \ P(X_{t+1}=1|X_t=1)=0.7$
とするとき,transition kernelは
$$\mathbf{K} = \left(\begin{array}{} 0.9 & 0.1 \\ 0.3 & 0.7 \end{array} \right)$$
となる. transition probabilityを有向グラフを使って表現することが有る. Markov graphという. この例のMarkov graphはfig. 1.4のようになる.

Example 1.4 (Random walk on $\mathbb{Z}$ (continued))

前に挙げたrandom walkのhomogeneous Markov chainのtransition kernelは行，列ともに無限大のToeplitz matrix(テープリッツ行列)で，具体的には
$$\left(\begin{array}{} \ddots & \ddots & \ddots & \ddots & \ddots \\ \ddots & \alpha & 1-\alpha-\beta & \beta & 0 \\ \ddots & \ddots & \alpha &1-\alpha-\beta & \beta &\ddots \\ \ddots & \ddots & \ddots & \ddots & \ddots \end{array} \right)$$
という形をしている.

Definition 1.9 (m-step transition kernel)

homogeneous Markov chain $\{X_t\}$について,$\mathbf{K}^{(m)} = (k^{(m)}_{ij})_{ij}, \ k^{(m)}_{ij} = P(X_{t+m}=j|X_t=i)$を$m$-step transition kernelという.

Proposition 1.10

$X$をhomogeneous Markov chainとすると,
i. $\mathbf{K}^{(m)} = \mathbf{K}^m$
ii. $P(X_m=j) = (\mathbf{\lambda_0}^T \mathbf{K}^{(m)})_j$
が成立する.

proof.

i. $\mathbf{K}^{(m_1+m_2)} = \mathbf{K}^{(m_1)} \cdot \mathbf{K}^{(m_2)}$を示す.
$$\begin{aligned} P(X_{t+m_1+m_2}=k|X_t=i) &=\sum_j P(X_{t+m_1+m_2}=k,X_{t+m_1}=j|X_t=i)\\&=\sum_j P(X_{t+m_1+m_2}=k|X_{t+m_1}=j,X_t=i)P(X_{t+m_1}=j|X_t=i) \\ &= \sum_j P(X_{t+m_2}=k|X_t=j)P(X_{t+m_1}=j|X_t=i) \\&=\sum_j \mathbf{K}_{ij}^{(m_1)} \mathbf{K}_{jk}^{(m_2)} = (\mathbf{K}^{(m_1)} \mathbf{K}^{(m_2)})_{i,k} \end{aligned}$$
ゆえに$\mathbf{K}^{(2)}=\mathbf{K}^2$がたしかに成立し,帰納法により$\mathbf{K}^{(m)}=\mathbf{K}^m$である.
ii. $$P(X_m=j) = \sum_i P(X_m=j,X_0=i) =\sum_i P(X_m=j|X_0=i)P(X_0=i)=(\lambda_0^T\mathbf{K}^m)_j$$

Example 1.5 (phone line(continued))

$$\mathbf{K}=\left(\begin{array}{} 0.9 & 0.1 \\ 0.3 & 0.7 \end{array} \right)$$
のm-step transition kernelは
$$\mathbf{K}^{(m)} = \mathbf{K}^m = \frac{1}{4}\left(\begin{array}{} 3+(\frac{3}{5})^m& 1-(\frac{3}{5})^m \\ 1+(\frac{3}{5})^m & 3-(\frac{3}{5})^m \end{array} \right)$$

1.2.2 Classificaton of states

Definition 1.11 (classification of states)

(a) ある$m \geq 0$があって,$k^{(m)}_{ij} = P(X_{t+m}=j|X_t=i)>0$が成り立つとき$i$は$j$を導くといい,$i \leadsto j$と書く.
(b) $i \leadsto j,\ j \leadsto i$であるとき$i,j$はcommunicateするといい,$i \sim j$と書く.このとき$\cdot \sim \cdot$は同値関係である.

$S$に同値関係を入れられたから,$S$は$\sim$で同値類別できる. ある同値類$C$の全ての元で他の$S$の元に出るpathが無いとき($\Leftrightarrow [\forall i \in C i \leadsto j \Rightarrow j \in C]$), $C$はclosedであるという. ある同値類の元は様々な性質を共有していることをあとで示す.

Example 1.6

$$\mathbf{K} = \left(\begin{array}{}\frac{1}{2} & \frac{1}{4} & 0 & \frac{1}{4} & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & \frac{3}{4} & 0 & 0 & \frac{1}{4} \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & \frac{3}{4} & 0 & 0 & 0 & \frac{1}{4} \\ 0 & 0 & \frac{1}{2} & 0 & 0 & \frac{1}{2} \end{array} \right)$$
をtransition kernelにもつMarkov chainのMarkov graphはfig. 1.5のとおりである. $2 \sim 4, 2 \sim 5, 3 \sim 6, 4\sim 5$が見て取れて,同値類別は$S\backslash \sim = \{\{1\},\{2,4,5\},\{3,6\}\}$であり，特に$\{3, 6\}$のみがclosedである.

Definition 1.12 (Irreducibility)

$S$の全ての元が互いにcommunicateするとき$S$はirreducibleであるという.

phone lineの例とrandom walkの例はreducibleであり,example 1.6はirreducibleである. ところで,ex. 1.6において,$2$から再び$2$に至るのは,$2$から$4$,$4$から$5$,$5$から$2$というステップを踏まなければならないので,$P(X_t=2|X_\tau=2) = \begin{cases} = 0 \ \ &(t \notin \tau + 3\mathbb{N}) \\ >0 &\text{otherwise} \end{cases}$
である. このような振る舞いをperiodicityという.

Definition 1.13 (Period)

(a) $i \in S$のperiod $d(i)$を
$$d(i) = gcd\{m\geq 1| K^{(m)}_{ii} > 0\}$$
と定める. periodを持たないstateも存在する.
(b) $d(i) = 1$なら,$i$はaperiodicという.
(c) $d(i) > 1$なら,$i$はperiodicという.

Example 1.7 (Ex. 1.6 continued)

すでに述べたように$d(2)=3$である. 同様に$d(4)=d(5)=3$である.
また$\mathbf{K}_{1,1},\mathbf{K}_{3,3}, \mathbf{K}_{6,6}>0$だから,$d(1)=d(3)=d(6)=1$.すなわち$3,6$はaperiodicである.
ある同値類(以後,communicateによる同値類をcommunicating classか,単にclassという)においてperiodを共有しているのは偶然ではない.

Proposition 1.14

(a) あるclassの全ての元はperiodを共有する.
(b) irreducible chainでは全ての元はperiodを共有する.

1.2.3 Recurrence and transience

ex. 1.6のMarkov chainを辿り続けると,そのうち$3, 6$を往復するだけになる. このような振る舞いを定式化するため, number of visits in state $i$:
$$V_i = \sum_{t=1}^\infty 1_{\{X_t =i\}}$$
を導入する. 初期値が$i$であるときの条件付き期待値は
$$E[V_i|X_0=i] = E\left[\sum_t 1_{\{X_t=i\}} | X_0=i \right] = \sum_{t=0}^\infty E[1_{\{X_t=i\}}|X_0=i] = \sum_t P(X_t=i|X_0=i) = \sum_{t} k^{(t)}_{ii}$$
この値が有限か無限かによってstateを分類する.

Definition 1.15 (Recurrence and transience)

(a) $i$がrucurrent
$\Leftrightarrow\ E(V_i|X_0=i)=\infty$
(b) $i$がtransient
$\Leftrightarrow\ E(V_i|X_0=i)<\infty$

すなわち,$i$がa.s.無限回訪れられるというのがrecurrentで，a.s.有限回訪れられるというのがtransientである.
prop. 1.14から,あるcommunication classの元たちはrecurrentであるか否かを共有する.

Proposition 1.16

あるcommunicating classにおいて，全ての元がrecurrentであるか，全ての元がtransientであるかのどちらかが成立する.

proof.

$i \sim j$ならば,$i$から$j$に至る長さ$m_{ij}$のpathがあり,$j$から$i$に一有る長さ$m_{ji}$のpathがある. すなわち$k^{(m_{ij})}_{ij}, k_{ji}^{(m_{ji})}>0$である.
$E(V_i|X_0=i) = \sum_t k^{(t)}_{ii} < \infty$とすると，
$$\begin{aligned} EV(V_j|X_0=j) &=\sum_{t} k^{(t)}_{jj} = \frac{1}{{k_{ij}^{(m_{ij})} k^{(m_{ji})}_{ji}}}\sum_t \underline{k_{ij}^{(m_{ij})}k_{jj}^{(t)}k_{ji}^{(m_{ji})}}_{(1)} \\ &\leq \frac{1}{{k_{ij}^{(m_{ij})} k^{(m_{ji})}_{ji}}} \sum_t k^{(m_{ij}+t+m_{ji})}_{ii} \\ &\leq \frac{1}{{k_{ij}^{(m_{ij})} k^{(m_{ji})}_{ji}}} \sum_{s\geq0} k_{ii}^{(s)} < \infty\end{aligned}$$
((1): $j$から$i$に行って,さらに$t$後にまた$i$に戻って,そこから$j$に戻るという確率)
よって$j$もまたtransientである.
また$i$がrecurrentであるとき,
$$\begin{aligned}E[V_j|X_0=j] = \sum_t k^{(t)}_{jj} &\geq \sum_{t=0}^{m_{jj}+ m_{ij}} k^{(t)}_{jj} + \sum_{\tau \geq 0}k^{(m_{ji})}_{ji} k^{(\tau)}_{ii} k^{(m_{ij})}_{ij} \\ &\geq \sum_{t=0}^{m_{jj}+ m_{ij}} k^{(t)}_{jj} + k^{(m_{ji})}_{ji} k^{(m_{ij})}_{ij}\sum_{\tau \geq 0} k^{(\tau)}_{ii} \geq \infty \end{aligned}$$
から,$j$もrecurrent.

Proposition 1.17

(a) closedでないclassはtransient
(b) 有限かつclosedなclassはrecurrent

Example 1.8 (ex.16, 1.7 continued)

ex.1.6において,$\{1\}, \{2,4,5\}$はclosedでないからtransient.
一方$\{3,6\}$は有限かつclosedなのでrecurrent.

1.2.4 Invariant distribution and equilibrium

invariant distributionを導入して,Markov chainの長期的な振る舞いを調べる.

Definition 1.18 (Invariant distribution)

$\mathbf{\mu} = (\mu_i)_{i \in S}$は$S$上のprobablility distributionとする. また$X$がMarkov chainでtransition kernel $\mathbf{K}$をもつとする. $\mathbf{\mu}$が$X$のinvariant distribution (stationary distibution)
$\Leftrightarrow \mathbf{\mu}^T \mathbf{K} = \mathbf{\mu}^T$

さらにこのとき,右から$\mathbf{K}$を掛けることで,
$$\forall i\in \mathbb{N}. \mu^T = \mu^T \mathbf{K}^{n}=\mu^T \mathbf{K}^{(n)}$$
が成立する.したがってprop. 1.10より
$$P(X_m=j) = (\mu \mathbf{K}^{(m)}_j) = (\mu)_j$$
が任意の$m$に成立する. つまり,$X$の分布は時刻によって変化しない.

Example 1.9 (Phone line (continued))

$$\mathbf{K} = \left(\begin{array}{} 0.9 & 0.1 \\ 0.3 & 0.7 \end{array} \right)$$
のstationary distributionを見つける.
$\mu^T \mathbf{K}=\mu^T$を変形して,$\mathbf{K}^T\mu = \mu$.よって$\mu$は$\mathbf{K}^T$のeigenvector(固有ベクトル)であって,ただし確率の公理から$\mu$のそれぞれの要素は非負で，総和は1である.これを解くと,$\mu=[\frac{3}{4}, \frac{1}{4}]^T$である.
Markov chainは必ずしもstationary distributionを持たない.$\mathbb{Z}$上のrandom walkがその例である.

Example 1.10 (Random walk on Z (continued))

$$\mathbf{K}= \left(\begin{array}{} \ddots & \ddots & \ddots & \ddots & \ddots \\ \ddots & \alpha & 1-\alpha-\beta & \beta & 0 \\ \ddots & \ddots & \alpha &1-\alpha-\beta & \beta &\ddots \\ \ddots & \ddots & \ddots & \ddots & \ddots \end{array} \right)$$
であることはすでに言った.$\mu = [1, 1,...]^T$は$\mu^T \mathbf{K}=\mu^T$の唯一の解だが,$\mu$は無限次元のベクトルなので正規化できない.

ある種のMarkov chainは長期的にはstationary distributionに至る.

Theorem 1.19 (convergence to equilibrium)

$X$がirreducibleかつaperiodicなMarkov chainで,stationary distribution $\mu$をもつとする.このとき
$$\lim_{t \rightarrow \infty}P(X_t = i) \rightarrow \mu_i$$
が任意の$i \in S$に成立する.

proof. (sketch)

$X$のinitial distribution, transition kernelをそれぞれ$\lambda$, $\mathbf{K}$とする. initial distribution $\mu$(stational)とtransition matrix $\mathbf{K}$をもつ新しいMarkov chain $Y$を定める. また$T$を$X, Y$が初めて$i\in S$に同時に到達する時刻の確率変数を$T$とする.すなわち
$$T = \min \{t\geq 0| X_t=Y_t=i\}$$
さらに$P(T<\infty)=1$であり，また新しいprocess $Z$を
$$Z_t = \begin{cases} X_t \ \ &(t \leq T) \\ Y_t &(t > T)\end{cases}$$
によって定める. $Z$の概略はfig.1.6のようになる. $Z$はinitial distribution $\lambda$をもち,transition kernel $\mathbf{K}$である. したがって$X$と$Z$は常に同じ分布を持つ.すなわち$\forall j. \ P(X_t=j)=P(Z_t=j)$である.
$Y$のinitial distributionはstationaryなので,$\forall t\forall j.\ P(Y_t = j) = \mu_j$である. $t \rightarrow \infty$において$P(\{Y_t = Z_t\})=1$であって,ゆえに
$$P(X_t=j)=P(Z_t=j)\rightarrow P(Y_t=j)=\mu_j$$

Example 1.11 (Phone line (continued))

phone lineの例で,$\mu=(3/4, 1/4)$だから,$P(X_t=0) \rightarrow 3/4, P(X_t=1) \rightarrow 1/4$.

Example 1.12

Theorem 1.19におけるaperiodicityの仮定が必須であることを示す.
$S=\{1, 2\}$, $\mathbf{K} = (\begin{array}{} 0 & 1 \\ 1 & 0\end{array})$とする. これは明らかにirreducibleだがperiod 2である. stationary distibutionは$(1/2, 1/2)$だが,これは決定論的な過程だから,明らかに$X$はこれに収束しない.

1.2.5 Reversibility and detailed balance

$P(X_{t+1}|X_t)$のように,現在(あるいは過去)を条件にした未来の状態の確率を論じてきたが，今度は逆に未来の状態を条件にした過去あるいは現在の状態の確率を議論する.
$$P(X_t=j|X_{t+1}=i) = P(X_{t+1}=i|X_t=j)\cdot \frac{P(X_t=j)}{P(X_{t+1}=i)}$$
のように条件付き確率の前後が交換できるのはBayesの定理の教えるところである.
chainを逆に辿っていくような新しいMarkov chainの定義を動機づける.

definition 1.20 (Time-reversed chain)

$\tau \in \mathbb{N}$について,$\{X_t | t = 0,...,\tau\}$をMarkov chainとする. $\{Y_t:t=0,..,\tau\}$を$Y_t = X_{\tau - t}$とすると,$Y$を$X$のtime-reversed chainという.
$$\begin{aligned} P(Y_t = j|Y_{t-1}=i)&=P(X_{\tau-t}=j|X_{\tau-t+1}=i)=P(X_s=j|X_{s+1}=i)\\ &=P(X_{s+1}=i|X_s=j)\cdot \frac{P(X_s=j)}{P(X_{s+1}=i)} = k_{ji}\frac{P(X_s=j)}{P(X_{s+1}=i)} \end{aligned}$$
である.

$X$がhomogeneousでも$Y$がhomogeneousとは限らない.
しかし,$X$のinitial distributionがstational $\mu$であれば,$P(X_{s+1}=i)=\mu_i, P(X_s=j)=\mu_j$が任意の$s$に実数として決まって,
$$P(Y_t=j|X_{t-1}=i)=k_{ji}\frac{\mu_j}{\mu_i} \ \ \ \ \ \ (1.2)$$
が成立するから,$\{Y_t\}$はhomogeneousである.

Example 1.13(Photo line(cont.))

すでに挙げた例で,
$\mathbf{K} = (\begin{array}{} 0.9 & 0.1 \\ 0.3 & 0.7 \end{array}), \mu = (3/4, 1/4)^T$だから, 式(1.2)により
$$\begin{aligned} &P(Y_t=0|Y_{t-1}=0) = k_{00}\frac{\mu_0}{\mu_0}=k_{00}=P(X_t=0|X_{t-1}=]1) \\ &P(Y_t=0|Y_{t-1}=1)=k_{01}\frac{\mu_0}{\mu_1} =0.3 =k_{10}=P(X_t=0|X_{t-1}=1) \\ &P(Y_t=1|Y_{t-1}=0)=k_{10}\frac{\mu_1}{\mu_0}=0.1 = k_{01}=P(X_t=1|X_{t-1}=0) \\ &P(Y_t=1|Y_{t-1}=1) =k_{11}\frac{\mu_1}{\mu_1}=k_{11}=P(X_t=1|X_{t-1}=1) \end{aligned}$$
以上よりこの例では$X$と$Y$は同じtransition probabilityをもつ. このようなchainはtime-reversibleであるという.

time-reversible であるか否かを判別する基準を導入する.

Definition 1.21 (Detailed balance, 詳細釣り合い条件)

transition kernel $\mathbf{K}$がdistribution $\mu$によってdetailed balanceを満たす
$\Leftrightarrow \forall i,j\in S. \ \ \mu_ik_{ij}=\mu_jk_{ji}$

detailed balanceは後で学ぶMarkov Chain Monte Carlo(MCMC)の議論でも極めて重要な役割を果たす. detailed balanceを満たす$\mu$はstationary distributionであり，これはdef. 1.19の定義よりも扱いやすいことが多い.

Theorem 1.22

$X$はMarkov chainで,そのtransition matrix を$\mathbf{K}$はdetailed balanceを$\mu$によって満たすとする.このとき
(i) $\mu$は$X$のstationary distributionである.
(ii) $\mu$がinitial distributionであれば,$X$はtime-reverisbleである．

proof.

(i)仮定より
$$(\mu^T K)_i = \sum_j \mu_j k_{ji} =_{(2)}\sum_j \mu_i k_{ij}= \mu_i \sum_j k_{ij} =_{(1)}\mu_i$$
((1): distributionの定義 (2): detailed balanceの定義)
よって確かに$\mu^T\mathbf{K}=\mu^T$だから,$\mu$はstationary distributionである.
(ii) $Y$を$X$のtime-reversalとする.
$$P(Y_t=j|Y_{t-1}=i)=_{(1)}k_{ji}\frac{\mu_j}{\mu_i}=_{(2)}\frac{k_{ij}\mu_i}{\mu_i}=k_{ij}=P(X_t=j|X_{t-1}=i)$$
(1): 式1.2 (2): detailed balanceの定義
よって確かに$X,Y$はtransition matrixを共有する

一方,stationary distributionを持つからと行ってtime-reversibleであるとは限らない.

Example 1.14

$S=\{1, 2, 3\}$.
$$\mathbf{K} = \left( \begin{array}{} 0 & 0.8 & 0.2 \\ 0.2 & 0 & 0.8 \\ 0.8 & 0.2 & 0\end{array} \right)$$
というMarkov chainを考えると,stationary distributionは$\mu = (1/3, 1/3, 1/3)^T$. Markov graphはfig.1.7の通り.

(1.2)からtime-reversed chain $Y$のtransition matrixが
$$\left( \begin{array}{} 0 & 0.2 & 0.8 \\ 0.8 & 0 & 0.2 \\ 0.2 & 0.8 & 0\end{array} \right)$$
と得られるが,これは$\mathbf{K}$と異なる行列である.