MIT OCW, Fundamentals of Probability 22日目 Markov Chain I

David Gamarnik, and John Tsitsiklis. 6.436J Fundamentals of Probability. Fall 2008. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

Lecture 23. Markov Chains

23.1 Introduction

Definition 23-1

$\{X_n \}_{n\geq 1}$がMarkov chain
$\Leftrightarrow$ $X(\Omega) = \mathcal{X}$はたかだか可算集合で,
$$P(X_n=x_n|X_{n-1}=x_{n-1}, X_{n-2}=x_{n-2}, ..., X_1=x_1) = P(X_n=x_n|X_{n-1}=x_{n-1})$$
$\mathcal{X}$をstatesといい,$X_n = s \in \mathcal{X}$なら,$\{X_n\}$は$n$においてstate $s$をとる という. 特に無限であると言わない場合,$|\mathcal{X}| <\infty$の場合を考える.このとき$\mathcal{X} = \{1, ..., N\}$として一般性を失わない.

Proposition 23-1

Markov chain $\{X_n\}_{n \geq 1}$について,
(a) 任意の$s, x_1, ..., x_n \in \mathcal{X}$と$m \in \mathbb{N}$について,
$$P(X_{n+m}=s|X_{n-1}=x_{n-1}, X_{n-2}=x_{n-2},...,X_1=x_1)=P(X_{n+m}=s|X_{n-1}=x_{n-1})$$

(b) 任意の$x_1, ...,x_n \in \mathcal{X}$と$k \in \{1, ...,n\}$について,
$$\begin{aligned} &P(X_n=x_n|X_{n-1}=x_{n-1},...,X_1=x_1|X_k=x_k)\\&=P(X_n=x_n,X_{n-1}-x_{n-1}, ..., X_{k+1}=x_{k+1}|X_k=x_k)P(X_{k-1}=x_{k-1},...,X_1=x_1|X_k=x_k) \end{aligned}$$

23.2 Examples

random walkはMarkov chainの一つである.
サイコロを繰り返しふって,$X_n$は$n$回の試行で過去出た出目6の回数とする. このとき$P(X_n=x+1|X_{n-1}=x) = 1/6, P(X_n=x|X_{n-1}=x)=5/6$であり,また$y\neq x, x+1$なら $P(X_n=y|X_{n-1}=x)=0$である.これは右へ進む確率$1/6$,その場にとどまる確率$1/6$のrandom walkとみなせる.

23.3 Homogeneous Finite State Markov Chain

Definition 23-2

Markov chain $\{X_n\}$がhomogeneousである
$\Leftrightarrow \forall n\ P(X_{n+1}=y|X_n=x)=P(X_2=y|X_1=x)$

$p(x, y)=P(X_{n+1}=y|X_n=x)$と書くようにすると,$N\times N$行列$P=(p_{i,j})$という行列ができる.これを$\{X_n\}$のtransition matrixという. $\sum_j p_{i,j}=1$である. 任意の行について,その行の要素の和が1であり,全ての要素が非負な行列を stochastic matrixという.
さて,
$$\begin{aligned} P(X_{n+2}=j|X_n=i) &= \sum_{1 \leq k \leq N} P(X_{n+2}=j|X_{n+1}=k,X_n=i) P(X_{n+1}=k|X_n=i)\\&=_{\text{}}\sum_{1\leq k\leq N} P(X_{n+2}=j|X_{n+1}=k)P(X_{n+1}=k|X_n=i)\\&=_{}\sum_{1 \leq k \leq N}p_{k,j}p_{i,k} \end{aligned}$$
だから,$P^2$の$(i, j)$成分($p^{(2)}_{i,j}$と書く)は,$\{X_n\}$を1つ飛ばしにしたMarkov chainのtransition matrixと考えることが出来る. 同じ論法で$r \in \mathbb{N}$に,$P^r$は$r-1$飛ばしのMarkov chainのtransition matrixである. $P^r$の$r\rightarrow \infty$での振る舞いを理解するのは大切である. Markov chainの多くを占めるクラスで,$j$のみによって$\lim_{r \rightarrow \infty} p_{i,j}^{r}$が存在することを後で見る.この性質をmixingという.
$e_j$で$\mathbb{R}^N$の$j$番目の標準基底ベクトルを表すことにする.また$e$を全ての要素が1である$N$次元ベクトルとする. $X_0 = i$とすると, $X_n$のprobability vectorは$e^T_i P^n$であり,$X_0$がprobability vector $\mu$によって決まるなら, $X$のprobability vectorは$\mu^T P^n$になる.

23.4 Stationary Distribution

$\mathcal{X} = \{1, 2\}, p_{1, 1,}=p_{1,2}=1/2, p_{2,1}=1, p_{2,2}=0$という単純なMarkov chainを考える. $\mu_1 = P(X_0=1)=2/3, \mu_2=P(X_0=2)=1/3$なる$\mu =(\mu_1, \mu_2)^T$から$n=0$でのstateが生成されるとき,$P(X_1=1)=(1/2)P(X_0=1)+P(X_0=2) = 2/3, P(X_1=2)=1-P(X_1=1)=1/3$.
よって$P(X_0=i)=P(X_1=i)\ \ \ i=1,2$で,$X_0, X_1$は同じ分布を持つと言える.これは任意の$n$も言える.

Definition 23-2

probability vector $\pi = (\pi_i), 1 \leq i \leq N$がstationary distribution
$\Leftrightarrow P(X_0)=\pi_i$と初期状態を決めると$\forall 1\leq i\leq N,1 \leq n, \ \ P(X_n=i)=\pi_i$

さらにこのとき(Markov chain$\{X_n\}$にsteady stateがあって,初期状態がそれによって決められたとき)$\{X_n\}$はsteady stateにあるという.

定義から,$\pi$がsteady stateである必要十分条件は,$\pi_i \geq 0, \sum \pi_i=1$かつ
$$\forall i\ \ \pi_i = \sum_{1 \leq k \leq N} p_{k,i}\pi_k$$
が成り立つことである. これはベクトル形式で書くと
$$\pi^T = \pi^T P$$
である.

Theorem 23-4

$\mathcal{X}<\infty$なMarkov chainは少なくとも１つのstationary distributionをもつ.

proof. 略 linear programming(線形計画法)の知識が必要らしい・・・ あとで確率論的な証明を与える.

23.5 Classification of States, Rucurrennt and Transient States

state 有限, homogeneousなMarkov chainがtransition matrix $P$を持っているとき, 有向グラフが作れる.
ノード集合$V= \mathcal{X}$, $p_{i,j} > 0$なる$i, j\in V$はedge集合の元;$(i, j) \in E$とする. $i$から$j$へ至るpathがあるとき$i$は$j$とコミュニケートする(i communicates with j)といい,$i \rightarrow j$と書く. これは$\sum_n p_{i,j}^{(n)}>0$ということである. $i\rightarrow j$だが$j\rightarrow i$でないというのは,chainが$i$から始まって$j$に至ると,再び$i$に戻ることはほとんど必ずないということである.

Definition 23-5

$i \in \mathcal{X}$がtransient
$\Leftrightarrow i \rightarrow j$だが$j \nrightarrow i$なる$j\in \mathcal{X}$が存在する

$i$がtransientでないとき,recurrentであるという.
$i\rightarrow j, j \rightarrow i$なるとき$i \leftrightarrow j$と書く.この関係は同値関係である.recurrent statesは同値類$R_1, ..., R_r$に分割でき,$T$をtransient stateの集合とすると,
$\mathcal{X} = T \cup R_1 \cup ... \cup R_r$と,互いに素な集合の和集合として書ける.