확률과정03-마르코프연쇄

Wednesday. March 27, 2019 - 8 mins

Statistics StochasticProcess

Contributor : Jiwoo Lim

확률과정이란?

확률과정: 임의의 $t\in{T}$에 대하여 $X_t$가 같은 확률공간상에 정의된 확률변수일 때 확률변수들의 집합 ${X_t t\in{T}}$
- $T$ : 관찰시점들의 총집합=지수집합=시간공간
- $X_t(\omega)$ : 시점 t에서의 상태 혹은 위치
- **상태공간 **: 모든 $t\in{T}$에 대하여 $X_t$가 취할 수 있는 가능한 모든 값들의 집합 S
확률과정의 분류
- 상태공간/시간공간/종속관계에 따라 분류 가능
- 마르코프연쇄: 상태공간 S와 시간공간 T가 모두 이산, 미래의 상태변화가 현재 상태에 의해 결정되며 현재를 알면 과거의 변화와는 무관
- 포아송과정: 도착간격시간이 서로 독립이고 지수분포를 따르는 counting process
  - counting process : $N_t$가 t시간까지의 도착 수를 나타낼 때
- 재생과정: 도착간격시간의 분포가 iid이지만 지수분포가 아닌 일반적인 분포로 가정한 counting process
- 정상과정: 확률변수 간의 확률 분포가 시간에 상관없이 일정한 확률 과정

마르코프연쇄

1. 서론

$X_n=i$ : n 시점에서 확률과정이 상태 i에 있는 사상
마르코프 확률과정: 마르코프성질을 만족하는 확률과정 ${X_n}$
- 마르코프성질: $P(X_{n+1}=i+1\mid X_0=i_0,X_1=i_1,…,X_n=i_n)=P(X_{n+1}=i+1\mid X_n=i_n)$
- 마르코프연쇄: 상태공간이 이산형인 마르코프 확률과정
전이확률/추이확률: $P_{ij}^{m,n}=P(X_n=j\mid X_m=i)$
- $n\ge{m}$일 때 확률과정 {$X_n$}이 시간 m에서 상태 i에 있다가 시간 n에서 상태 j로 바뀔 확률
- 정상전이확률: $P_{ij}^{m,n}=P_{ij}^{0,n-m}$이 성립할 경우, i에서 j로 가는 확률이 출발 및 도착시점과 무관하고, 오로지 경과된 시간에 의해서만 좌우됨
- m-단계전이확률: $P(X_{n+m}=j\mid X_n=i)=P_{ij}^{(m)}$, 정상전이확률을 갖는 마르코프연쇄에서 i에 있다가 m단계 후 j 상태가 되는 확률
- 전이확률행렬(=전이행렬): $P_{ij}$를 원소로 갖는 행렬 [$P_{ij}$]
여기서는 이산상태공간과 정상전이확률을 갖는 마르코프연쇄에 대해서만 다루기로 한다…!

2. 채프만 콜모고로프의 방정식

마르코프연쇄에서는 초기 확률변수 $X_0$의 분포와 전이확률로부터 확률과정의 모든 확률적인 정보에 접근가능
초기분포: $X_0$의 분포
$P(X_n=i_n,…,X_0=i_0)=P(X_n=i_n\mid X_0=i_0,…,X_{n-1}=i_{n-1})P(X_0=i_0,…,X_{n-1}=i_{n-1})$

= $P(X_n=i_n\mid X_{n-1}=i_{n-1})P(X_{n-1}=i_{n-1}\mid X_0=i_0,…,X_{n-2}=i_{n-2})P(X_0=i_0,…,X_{n-2}=i_{n-2})$

= ….

= $P(X_n=i_n\mid X_{n-1}=i_{n-1})P(X_{n-1}=i_{n-1}\mid X_{n-2}=i_{n-2})..P(X_1=i_1\mid X_0=i_{0})P(X_0=i_0)$

= $p_{i0}P_{i_0i_1}…P_{i_{n-1}i_n}$
채프만-콜모고로프 방정식
- $P_{ij}^{(n+m)}=\sum_{k\in{S}}P_{ik}^{(n)}P_{kj}^{(m)}$
- i에서 출발하여 (n+m)단계를 거쳐 j로 갈 확률=처음 n단계에서 임의의 k상태를 거쳐 나머지 m단계동안 j로 가는 확률
- $P^{(n+m)}=P^{(n)}P^{(m)}$

3. 상태의 분류

$\begin{cases}\bold{도달가능}: 상태 \;i가 \;유한\; 번의 \;단계를 \;거쳐 \;상태\; j로\; 갈\; 수 \;있으면, \;즉 \;P_{ij}^{(n)}>0인\; n\ge0이 \;존재하면 \\hspace{40pt}상태 \;j는 \;상태\; i에서\; 도달가능,\; i\to{j}\\bold{상호도달가능} : i\leftrightarrow{j} \end{cases}$
- 상태공간에서 관계 $\leftrightarrow$는 아래의 세 조건을 만족한다
(1) $i\leftrightarrow{i}$ : 반사성

(2) $i\leftrightarrow{j}$이면 $j\leftrightarrow{i}$ : 대칭성

(3) $i\leftrightarrow{j}$이고 $j\leftrightarrow{k}$이면 $i\leftrightarrow{k}$ : 추이성
- 동치관계: 위의 3가지 조건을 만족하는 관계
  - 동치관계 “$\leftrightarrow$”는 상태공간 S를 “동치류”로 분할
  - $C_i={j\mid i\leftrightarrow{j}}$

$\begin{cases}\bold{기약(irreducible) 마르코프연쇄} : 동치류가\; 하나뿐\;=>모든\; 상태가\; 서로 \;상호도달\\bold{비기약(reducible) 마르코프연쇄} : 동치류가 \;2개 \;이상\end{cases}$

$f_{ij}^{(n)}$ : i에서 출발하여 처음으로 j에 도달하는 최초 방문시간이 n(n$\ge$1)이 될 확률

=$P(X_n=j,X_m\ne{j},1\le{m}\le{n-1}\mid X_0=i)$

$f_{ij}$ : i에서 출발하여 언젠가는 j에 도달할 확률

=$\sum_{n=1}^{\infty}f_{ij}^{(n)}=P(\bigcup(X_n=j)\mid X_0=i)$
$N_{ij}$ : i에서 출발한 확률과정이 j를 방문하는 총 횟수
- $P(N_{ij}=0)=1-f_{ij}$
- $P(N_{ij}=n)=f_{ij}(f_{jj})^{n-1}(1-f_{jj}), n\ge1$
- 특히 i=j이면 $f_{ii}<1$일 때 $P(N_{ii}=n)=(f_{ii})^n(1-f_{ii}) (n\ge0)$이고, $N_{ii}$는 기하분포를 따름
$\begin{cases}\bold{재귀적 \;상태}:f_{ii}=1인 \;상태 \;i\\bold{일시적 \;상태}: f_{ii}<1인 \;상태 \; i\end{cases}$
- $E(N_{ii})=\begin{cases} \infty,&f_{ii}=1
  \frac{f_{ii}}{1-f_{ii}}\;(=\sum_{n=0}^{\infty}n(f_{ii})^n(1-f_{ii})),&f_{ii}<1 \end{cases}$
- $E(N_{ii})=E[\sum_{n=1}^{\infty}I_{{X_n=i}}\mid X_0=i]\ \hspace{29pt}=\sum_{n=1}^{\infty}E[I_{{X_n=i}}\mid X_0=i]\\hspace{29pt}=\sum_{n=1}^{\infty}P(X_n=i\mid X_0=i)\\hspace{29pt}=\sum_{n=1}^{\infty}P_{ii}^{(n)}$
  
  => 상태 i가 재귀상태 $\Leftrightarrow$ $\sum_{n=1}^{\infty}P_{ii}^{(n)}=\infty$
- 흡수상태: $P_{ii}=1$인 상태
상태와 관련된 정리 2가지
- $i\leftrightarrow{j}$이면 i와 j는 동시에 일시적이거나 동시에 재귀적이다
  - $P_{jj}^{(n+s+m)}\ge{P_{ji}^{(m)}P_{ii}^{(s)}}P_{ij}^{(n)}$ by 채프만-콜모고로프 방정식
    
    => $\sum_{s=0}^{\infty}P_{jj}^{(s)}\ge{\sum_{s=0}^{\infty}P_{jj}^{(n+s+m)}\ge{P_{ji}^{(m)}P_{ij}^{(n)}\sum_{s=0}^{\infty}P_{ii}^{(s)}}}$
    
    => $\sum_{s=0}^{\infty}P_{ii}^{(s)}=\infty$이면, 즉 i가 재귀상태이면 j도 재귀상태이다. 만약 j가 일시상태이면 i도 일시상태가 된다
- i가 재귀적이고 $i\to{j}$이면, j도 재귀적이고 $f_{ji}=1$
  - $\alpha:$ i에서 출발하여 언젠가는 j에 도착할 확률 ($\alpha>0$). 만약 j에서 i로 다시 돌아오지 않을 수 있다면 $f_{ji}<1$이고, i에서 출발 후 다시 i로 돌아오지 못할 확률이 $\alpha(1-f_{ji})>0$이 성립한다. 이는 i가 재귀적이라는 가정에 모순이다. 따라서 $f_{ji}=1$ 성립하고 $i\leftrightarrow{j}$
  - $i\to{j}$일 때 i가 재귀상태이면 $C_i={j i\to{j}}$의 모든 상태들은 상호도달가능하게 되어 동치류 형성

4. 정상분포와 극한 성질

마르코프연쇄의 전이확률이 오랜 시간이 경과한 후에는 어떤 값을 갖게 될 것인가?
$P=\begin{bmatrix} 0.7 & 0.3
0.4 & 0.6 \end{bmatrix}$ => $P^{(8)}=\begin{bmatrix} 0.572 & 0.428
0.570 & 0.430 \end{bmatrix}$
- n이 커지면서 $P^{(n)}$의 각 열의 원소들이 거의 같아짐
- 마르코프연쇄 ${X_n: n\ge0}$가 오랜 시간 경과 후 ($n\to\infty$) 상태 j가 될 확률은 출발지점 i에 관계없이 어떤 특정 값으로 수렴하게 됨

4.1 주기

S={정수}를 상태공간으로 하고 $P_{ii+1}=p, P_{ii-1}=1-p$인 단순확률보행과정에서 $P_{ii}^{(n)}>0$이 성립하기 위해서는 n이 2의 배수여야 한다.
${n:P_{ii}^{(n)}>0}$의 최대공약수를 d라 할 때, d>1이면 상태 i는 주기 d를 갖는 주기적 상태라 하고, d=1이면 i는 비주기적 상태라 한다. 따라서 i가 주기 d를 갖게 되면 d의 배수가 아닌 n에 대하여 항상 $P_{ii}^{(n)}=0$이 성립

주기에 관한 정리 2가지
1. $d(i)=g.c.d. {n\ge1:P_{ii}^{(n)}>0}$
2. $i\leftrightarrow{j}\;이면\; d(i)=d(j)이다.$

4.2 평균재귀시간과 극한분포

$u_i=\sum_{n=1}^{\infty}nf_{ii}^{(n)}$
- i가 재귀상태이면 상태 i로 돌아오는 데 걸리는 평균시간( = 상태 i의 평균재귀시간)
- $i:\begin{cases} \bold{귀무재귀상태}, & \mbox{if }u_i=\infty
  \bold{양재귀상태,} & \mbox{if }u_i<\infty \end{cases}$
i에서 출발한 마르코프 연쇄에서

$T_1^{(i)}=$처음 i로 돌아오는 데 필요한 전이횟수

$T_2^{(i)}=$ 처음 i로 돌아온 이후 다시 두번째로 i에 돌아오는 데 필요한 전이횟수

….이라 가정하자
- $T_n^{(i)}$는 iid이므로 강대수법칙을 적용하면 $\frac{T_1^{(i)}+…+T_n^{(i)}}{n}\to{u_i}$
- 좌변의 분자: i를 n번 방문할 때까지 필요한 총 전이횟수=>좌변: 1회 방문에 필요한 평균전이횟수=>
  
  $\frac{1}{u_i}$: 총 전이횟수 중에서 i로 전이한 횟수의 상대적 비율
$P_{ii}^{(n)}=\sum_{k=0}^nf_{ii}^{(k)}P_{ii}^{(n-k)}$
$P_{ii}^{(n)}=\begin{cases} i에서\;출발한\;확률과정이\;i에\;머무르는\;시간비 &\mbox{if}\; \mbox{i는 비주기적 재귀상태}&(n\to\infty)
m\ne{nd}인\;m에\;대해서\;P_{ii}^{(m)}=0,\;{lim_{n\to\infty}P_{ii}^{(nd)}=\frac{d}{u_i}} &\mbox{if}\;\mbox{i는 주기 d를 갖는 재귀상태}&\mbox{} (n\to\infty) \end{cases}$

극한분포에 대한 정리 2가지

$j가\;일시상태이면\;모든\;i에\;대하여\;P_{ij}^{(n)}\to0\qquad(n\to\infty)$
- j가 일시상태이면 모든 i에 대하여 $\sum{P_{ij}}^{(n)}<\infty$이므로 $n\to\infty$일 때 $P_{ij}^{(n)}\to0 $
$j가\;비주기적,\;재귀적상태이면\;모든\;i에\;대하여\;P_{ij}^{(n)}\to{\frac{f_{ij}}{u_j}}\qquad(n\to\infty)$
- 비주기적 기약 마르코프연쇄에서는 초기에는 불규칙하게 움직이던 확률과정이 시간이 지날수록 안정성을 유지하게 되어 $P_{ij}^{(n)}$은 초기상태 i와는 무관한 극값을 갖게 된다?
- $\begin{cases} P_{ij}^{(n)}\to{0}\hspace{35pt}if\; j가 \;귀무재귀상태\quad(u_j=\infty) &(n\to\infty)
  P_{ij}^{(n)}\to{\frac{1}{u_j}>0}\hspace{10pt} if\; j가 \;비주기적 \;양재귀상태일 \;때\; i와\; j가\; 같은\; 동치류에\; 속하면\; f_{ij}=1이므로 &(n\to\infty) \end{cases}$

$i\leftrightarrow{j}$이면 i와 j는 동시에 일시적이거나 동시에 양재귀이거나 또는 동시에 귀무재귀가 된다

4.3 정상분포와 극한분포

정상과정: 확률과정 ${X_n:n\ge{0}}$에서 임의의 $k>0,m>0$에 대하여 $(X_0,X_1,…,X_m)$의 결합분포가 $(X_k,X_{k+1},…,X_{k+m})$의 결합분포와 항상 같아지는 경우의 $X_n$
정상분포: 상태공간 S를 갖는 마르코프연쇄에서 $\sum_{i\in{S}}\pi_i=1$, $\sum_{i\in{S}}\pi_iP_{ij}=\pi_j$ $(j\in{S})$를 만족하는 수집합 $\pi_i\ge0$을 전이행렬 $\bold{P}=[P_{ij}]$에 대한 정상분포라 부른다
- $\bold{\pi{P}=\pi}$로 표현가능
초기분포가 정상분포 $\pi_j\;(j=0,1,2,…)$를 갖는다고 가정하자
- $P(X_1=j)=\sum_{i}P(X_1=j\mid X_0=i)P(X_0=i)$
  
  $=\sum_{i}\pi_{i}P_{ij}=\pi_j$
- n>1인 임의의 n에 대하여 $X_{n-1}$의 분포가 $\pi$라고 가정하면 다음이 성립한다
  - $P(X_n=j)=\sum_{i}P(X_n=j\mid X_{n-1}=i)P(X_{n-1}=i)$
    
    $=\sum_{i}\pi_{i}P_{ij}=\pi_j$
- 따라서 수학적 귀납법에 의해 임의의 n에 대한 $X_n$의 분포는 초기분포 $\pi$와 같아진다
  
  => 극한 분포 $\pi_j$를 $X_n$의 불변확률분포라 부름
- $P(X_n=i,X_{n+1}=i_1,…,X_{n+k}=i_k)\=P(X_n=i)P_{ii_1}P_{i_1i_2}…P_{i_{k-1}i_k}\=\pi_iP_{ii_1}P_{ii_2}…P_{i_{k-1}i_k}$
  
  => $X_n,X_{n+1},…,X_{n+k}$의 결합확률분포는 n에 독립이다!
초기분포가 정상분포인 경우 정리 2가지
1. $초기분포가 \;정상분포이면 \; 임의의 \;n에 \;대한 \; X_n의 \; 분포도 \;정상분포이다$
2. $초기분포가 \;정상분포인 \;마르코프과정 \; {X_n}은 \;\bold{정상확률과정}이다$
극한분포/평형상태분포: 모든 $i,j\in{S}$에 대하여 $lim_{n\to\infty}P_{ij}^{(n)}=\pi_j\ge0$이고, $\sum_{j\in{S}}\pi_j=1$인 경우의 $\pi_j$
- $\pi_j$가 극한분포이면 $P_{kj}^{(n+1)}=\sum_{i\in{S}}P_{ki}^{(n)}P_{ij}$의 양변에 $n\to\infty$를 취해주면 $\pi_j=\sum_{i\in{S}}\pi_iP_{ij}$
  
  => 극한분포는 유일한 정상분포! (but 마르코프연쇄가 정상분포를 갖는다는 것이 극한분포를 가짐을
  
  의미하지는 x)
정상분포와 극한분포 사이의 관계
- $\bold{P}=[P_{ij}]$를 전이행렬로 갖는 마르코프연쇄에서 임의의 i,j에 대하여 $lim_{n\to\infty}P_{ij}^{(n)}=\pi_j$라 가정하면 다음이 성립한다
  - $\sum_{j\in{S}}\pi_j\le1$이고 $\sum_{i\in{S}}\pi_iP_{ij}=\pi_j$ ($j\in{S}$)이다.
  - 모든 $j\in{S}$에 대하여 $\pi_j=0$이거나 $\sum_{j\in{S}}\pi_j=1$이다.
  - 모든 $j\in{S}$에 대하여 $\pi_j=0$이면 정상분포는 존재하지 않고, $\sum_{j\in{S}}\pi_j=1$이면 $\pi_j$ $(j\in{S})$는 극한분포이며 동시에 유일한 정상분포이다.
비주기적 기약 마르코프연쇄에서는 임의의 i,j에 대하여 $lim_{n\to\infty}P_{ij}^{(n)}=\pi_j$를 만족하는 $\pi_j$가 존재한다. 따라서 다음 두 가지 중 하나가 성립한다

1) 모든 상태가 일시적이거나 귀무재귀이다

=> 임의의 i,j에 대하여 $P_{ij}^{(n)}\to0$이 되므로 정상분포 존재 x

2) 모든 상태가 양재귀이다

=> 비주기적, 양재귀적 기약 마르코프연쇄에서는 극한분포 존재
n단계추이행렬 $P^{(n)}$에서 $P_{ij}^{(n)}\to\pi_j\ge{0}$, $\sum_{j\in{S}}\pi_j=1$이면

=> $P(X_n=j)=\sum_{i\in{S}}p_iP_{ij}^{(n)}\to\sum_{i\in{S}}p_i\pi_j=\pi_j$

=> $lim_{n\to\infty}P(X_n=j)$는 초기분포 $p_i$의 영향을 받지 않는다!
$\pi{P}=\pi$의 의미
- $\pi_j=\sum_{i\in{S}}\pi_iP_{ij}=\sum_{i\ne{j}}\pi_iP_{ij}+\pi_jP_{jj}$
  
  => $\pi_j(1-P_{jj})=\sum_{i\ne{j}}\pi_iP_{ij}$
  
  ( $\pi_j$: 상태 j에 있게 되는 극한 확률, $(1-P_{jj})$ : j 상태에 있는 마르코프연쇄가 j를 떠날 확률 )
  
  => 좌변 $\pi_j(1-P_{jj})$: 마르코프연쇄가 상태 j를 떠날 극한확률
  
  우변 $\sum_{i\ne{j}}\pi_iP_{ij}$: 다른 상태로부터 상태 j로 들어오는 극한확률
  
  => 시스템이 평형상태에 이르렀음!

5. 흡수 마르코프연쇄

흡수상태($P_{ii}=1$)와 일시상태만이 있는 유한상태공간을 갖는 마르코프연쇄를 가정해보자. 상태공간이 $S={1,2,…,N}$이라고 하고, 상태 ${1,2,…,r}$은 흡수상태이고 ${r+1,r+2,…,N}$은 일시상태라 하자. 그러면 마르코프연쇄의 전이행렬은 다음과 같이 표기된다.
- $\bold{P}=\begin{bmatrix} \bold{I} & 0
  \bold{R} & \bold{Q} \end{bmatrix}$
- $\bold{I}$ : $P_{ii}=1$, 0 : $흡수상태\to{일시상태}$, $\bold{R}: 일시상태\to{흡수상태}$, $\bold{Q}: 일시상태\to{일시상태}$
  - ex) $P=\begin{bmatrix} 1 &0&0\0.5&0.5&0\0&1&0\end{bmatrix}$
흡수마르코프연쇄에서 흡수상태가 아닌 상태는 모두 일시상태이고, 궁극적으로 흡수상태 중 하나로 흡수된다.
P의 n단계 전이행렬 및 극한
- $\bold{P}^n=\begin{bmatrix}\bold{I}&0\(\bold{I}+\bold{Q}+…+\bold{Q}^{n-1})\bold{R}&\bold{Q}^n\end{bmatrix}$ $\to$ $\begin{bmatrix}\bold{I}&0\(\bold{I}-\bold{Q})^{-1}\bold{R}&0\end{bmatrix}$
흡수마르코프연쇄에서의 관심사 2가지

1) 흡수되기 전까지 일시상태 j로의 평균전이횟수
- $m_{ij}$ : 일시상태 i에서 출발한 마르코프과정이 일시상태 j를 방문하게 되는 평균횟수
  - T: 일시상태집합, A: 흡수상태집합이라 하자
  - $m_{ij}=\delta_{ij}+\sum_{l\in{T}}P_{il}m_{lj}$ ($\delta_{ij}=\begin{cases} 1, & i=j
    0, & i\ne{j} \end{cases}$)
    
    <=> $\bold{M=I+QM}$ <=> $\bold{M=(I-Q)^{-1}}$ ( $\bold{M}=[m_{ij}]$ )
- $a_i$ : 일시상태 i에서 출발하여 임의의 흡수상태로 흡수되기까지 걸리는 시간
  - 흡수되기 전까지는 일시상태 위에서 움직이므로 $E(a_i)=\sum_{j\in{T}}m_{ij}$=>행렬 $\bold{M}$의 i번째 행의 합
2) 흡수상태 k로 들어갈 확률
- $f_{ik}$ : $P(언젠가는 \;상태 \; k에 \;흡수됨 현재상태는 \; i)$
  
  = $P_{ik}+\sum_{l\in{T}}P_{il}f_{lk}$
  
  <=> $\bold{F=R+QF}$ <=> $\bold{F=(I-Q)^{-1}R=MR}$ ( $\bold{F}=[f_{ik}]$ )
  - $\bold{P^n} $$\to$ $\begin{bmatrix}\bold{I}&0\\bold{F}&0\end{bmatrix}$ as $n\to\infty$