MIT OCW, Fundamentals of Probability 24日目 Markov Chain III

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 25. Markov Chain III. Periodicity, Mixing, Absorption
    • 25.1 Periodicity
      • Lemma 25-1
      • Lemma 25-2 (証明略)
      • Theorem 25-3 (証明略)
      • Theorem 25-4 (証明略)
    • 25.2 Absorption Probabilities and Expected Time to Absorption
      • Example: Gambbler’s Ruin

Lecture 25. Markov Chain III. Periodicity, Mixing, Absorption

25.1 Periodicity

$x \in \mathcal{X}$がrecurrentであるとき,$x$がそれ自身からaccessibleである時刻,すなわち$I_x = \{n\geq 1: p_{xx}^{(n)} > 0\}$を考える. $I_x$は和に対して閉じている(i.e. $m,n\in I_x \Rightarrow m+n\in I_x$). $d_x$を$I_x$の元の最大公約数として,$x$のperiodという. periodの諸性質を論じる.

Lemma 25-1

$x, y$が同じrecurrentにあるとき,$d_x = d_y$である.

proof.

$p^{(m)}_{xy}, p^{(n)}_{yx} > 0$である$m, n$を選ぶ(同じrecurrentだから存在する). $p_{yy}^{(m+n)} \geq p_{xy}^{(m)}p_{yx}^{(n)} > 0$だから$d_y$は$m+n$を割り切る. また$l$を$p_{xx}^{(l)} > 0$なる$l \in \mathbb{N}$とすると,$p_{yy}^{m+n+l} \geq p_{yx}^{(n)}p_{xx}^{(l)}p_{xy}^{(m)}>0$だから,$d_y$は$m+n+l$を割り切り,故に$l$を割り切る. したがって$d_y$は$d_x$を割り切る. 同じ論法で$d_x$が$d_y$を割り切ることも言えて,以上より$d_x=d_y$

$d > 1$であるようなrecurrent classをperiodicといい,$d=1$であるときにはaperidicという. periodicityは$p_{xy}^{(n)}$が$\pi_y$に収束することを妨げている. $y$がperiodicなrecurrent classの元とすると,$p_{yy}^{(n)}=0$が,$n$が$d$の倍数でない限り成立するが,$\pi_y>0$である. 一方$d=1$(aperiodic)であれば,十分大きな全ての$n$に,markov chainが$y$に戻ってくる確率が正になる.

Lemma 25-2 (証明略)

$d_y=1$であれば,$N \geq 1$があって,$n \geq N\Rightarrow p_{yy}^{(n)}>0$である.

Markov chainがただ一つのrecurrent classをもち(irreducible),かつaperiodicであるとき,steady stateの振る舞いはstationary distributionによって与えられる.この事実をmixingという.

Theorem 25-3 (証明略)

irreduibleかつaperiodicなMarkov chainがあるとき,任意のstateの組$x, y$について$\lim_{n \rightarrow \infty} p_{xy}^{(n)}=\pi_y$

periodicな場合には,$p_{xy}^{(n)}$の部分列の収束に関する定理が有るがここでは扱わない.
$\pi_x p_{xy} = \pi_y p_{yx}$が任意の$x, y \in \mathcal{X}$に成り立つとき,そのMarkov chainはreversibleであるという. Theorem 25-3の仮定にreversible性を加ええ場合の重要な定理が知られている.

Theorem 25-4 (証明略)

irreducible, aperiodic, reversibleなMarkov chainについて,任意の$x, y \in \mathcal{X}$に$|p_{xy}^{(n)} - \pi_y| \leq C|\lambda_2|^n$が成り立つような定数$C$が存在する.ただし$\lambda_2$は$P$の二番目に絶対値が大きいeigenvalueとする.

$|\lambda_2|<1$だから,これは$p_{xy}^{(n)}$の$pi_y$への収束の速さを与える.

25.2 Absorption Probabilities and Expected Time to Absorption

Markov chainの長期的な振る舞いを見てきたが,今度は短期的な振る舞いを議論する. 特にtransientなstateから始まったchainの振る舞いを考える. 簡単のため,recurrent state $i$はabsorbingであるとする.すなわち$p_{ii}=1$である. これから考察するMarkov chainはtransient classのほかは全てabsorbingとする.
absorbing state $i$がただ一つであるときには$\pi_i = 1$であって,必ず$i$に到達する. 一方absorbing stateが複数存在するときには,どのabsorbing stateに至るかは確率的に決まる.
$$a_{ki} = P(X_n \text{eventually equals i} | X_0 = k)$$
をabsorbing probabilityという. $j$がabsorbingなら$a_{jj}=0, a_{ji}=0$である.
$k$がtransientなら
$$\begin{aligned} a_{ki} &=P(\exists n: X_n=i|X_0=k) \\ &=\sum_{j=1}^N P(\exists n: X_n=i|X_1=j)p_{kj} \\ &= \sum_{j=1}^N a_{ji}p_{kj} \end{aligned}$$
だから,この線形連立方程式を解くことでabsorption probabilityを得られる.

Example: Gambbler’s Ruin

あるギャンブラーが一回の勝負ごとに$p$の確率で1ドルを得て,$1-p$の確率で1ドルを失うとする. それぞれの勝負は独立であるとする. ギャンブラーは$m$ドルを稼ぐか金を全て失うまで勝負を続ける. 彼が全財産を失う確率を求めよ

$i$はギャンブラーの持つ金額として,Markov chain $\mathcal{X} = \{0, 1, ..., m\}$を考える. $i=0$なるとき,彼は全財産を失うったということであり,$i=m$となるとき,彼は目的を達成したということである. $0, m$はabsorbing stateであると言える.
transition probabilityは$p_{i, i+1} = p, p_{i, i-1}=1-p$が全ての$i=1, ..., m-1$で成立する.また$p_{00}=p_{mm}=1$である. $i=0$のabsorbing probabilityは
$$\begin{aligned} a_{00} &= 1 \\ a_{m0} &= 0 \\ a_{mm}&=1\\ a_{i0} &=(1-p)a_{i-1, 0} + p(a_{i+1}, 0) \ \ \ \ \ \text{for } i=1, ..., m-1\end{aligned}$$
によって計算できる.$b_i = a_{i0} - a_{i+1, 0}, \rho = (1-p)/p$とすると,上の方程式から
$$\begin{aligned} (1-p)(a_{i-1, 0} -a_{i, 0}) &= p(a_{i0} -a_{i+1, 0}) \\ b_i &= \rho b_{i-1} \end{aligned}$$
であって,故に$b_i = \rho^i b_0$である. $b_0+b_1+\cdots +b_{m-1} = a_{00} - a_{m0} = 1$であって, $(1+\rho + ...+rho^{m-1})b_0 = 1$であって,
$$b_i = \begin{cases} \frac{\rho^i (1-\rho)}{1-\rho^m} \ \ \ &if \rho \neq 1 \\ \frac{1}{m} & otherwise\end{cases}$$
さらに$a_{i,0}$は$\rho \neq 1$ならば$i=1,...,m-1$について
$$a_{i0} = a_{00} -b_{i-1} - ... -b_0 = \frac{\rho^i - \rho^m}{1-\rho^m}$$
$\rho = 1$ならば
$$a_{i0} = \frac{m-i}{m}$$
したがって$i$がいかなる値でも$m$が大きくなると全財産を失う確率が$1$に近づく.

Discrete Stochastic Processesに続く