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})=\left(\begin{array}{cccc}\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{array}\right)$$

 

시점 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}_i{q}_{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)번째 항

$$⋮$$

$$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