31. 마코프 체인(Markov Chains)

본 글은 Havard University Statistics 110 강의를 듣고 정리한 내용입니다.

 

마코프 체인

현재까지 계속 독립항등분포인 경우만 다뤄왔지만, 확률변수가 iid가 성립하지 않는다면 어떻게 해야하는가?

 

defn)

X1, X2, ... 가 이산적인 시간 n에서의 시스템의 상태라고 했을 때,  

\[ P(X_{n+1} = j|X_n=i_n, X_{n-1}=i_{n-1}, \cdots, X_0 = i_0)\]

\[ = P(X_{n+1}=j|X_n=i)\]

=> 현재가 주어지면, 과거와 미래는 조건부 독립이다.

\[= q_{ij}\]

전이확률, j상태에서의 확률이 항상 q_ij이다(homogeneous)

Xn의 상태에서 Xn+1 상태로 넘어갈 때, 각각의 확률

이전의 상태는 상관없이 현재의 상태만 고려하게 된다.

전이행렬(Transition Matrix)

\[ Q = (q_{ij}) = \begin{pmatrix}\frac{1}{3} & \frac{2}{3} & 0 & 0 \\\frac{1}{2} &0 & \frac{1}{2} & 0 \\ 0& 0 & 0 & 1 \\\frac{1}{2} & 0 & \frac{1}{4} & \frac{1}{4} \\\end{pmatrix}\]

 

시점 n에 Xn은 s​⃗​​의 분포를 따른다고 할 때, (s는 1xM 행렬)

\[ P(X_{n+1}=j) = \sum_{i}^{}P(X_{n+1}=j|X_n=i)P(X_n=i)\]

\[= \sum_{i}^{}s_iq_{ij}\]

s_i q_ij -> s​⃗​​Q의 j번째 항

\[ P(X_{n+1}=j|X_n=i) = q_{ij}\]

\[ P(X_{n+2}=j|X_n=i) = \sum_{k}^{}P(X_{n+2}=j|X_{n+1}=k, X_n=i)P(X_{n+1}=k|X_n=i)\]

\[= \sum_{k}^{}q_{kj}q_{ik}\]

-> Q^2의 (i, j)번째 항

\[ \vdots \]

\[  P(X_{n+m} = j |X_n = i) \]

-> Q^m의 (i, j)번째 항

 

고정된 분포(Stationary Distribution)

마코프 체인이 반복되다 보면 언젠가는 어떤 상태에 수렴하게 되는가?

​s​⃗​​ (1×M의 확률 벡터)는 ​s​⃗​​Q=​s​⃗​​ 를 만족할 때 고정된 분포이다.

 

 체크사항:

• 고정된 분포라는 것이 존재할 수 있는가?
• unique한 분포인가?
• 마코프 체인이 실제로 s​⃗​​ 에 결국 수렴하는가?
• 고정된 분포 ​s​⃗​​ 를 어떻게 구할 수 있는가?

 

출처: https://www.edwith.org/ai152