Markov Chain

Markov Chain 매우 간단한 예제

햄버거, 피자, 핫도그 세 음식이 있으며, 매일 셋 중 하나의 음식이 제공된다. 그리고 직전 날에 무엇을 제공받았냐에 따라 그 날의 음식이 결정된다. 즉, 오늘 음식을 먹으면 내일 무슨 음식을 받을 지 예측할 수 있다.

화살표의 시작은 오늘 먹은 음식, 끝은 내일의 음식, 숫자는 오늘->내일 음식의 확률이다. 이 그래프가 바로 Markov chain이다.

Markov Chain의 중요한 컨셉은, 미래의 상태가 바로 직전의 상태에만 의존한다는 것이다. 즉, 내일의 음식은 오늘의 음식만 영향을 주고, 어제의 음식은 영향을 주지 않는다는 것이다.

Markov chain 식

직전의 상태만 보면 되기 때문에 문제를 쉽게 만들 수 있다.

 

Stationary distribution

Directed Graph -> Adjacency Matrix(인접행렬)=Transition Matrix로도 더 편리하게 표현할 수 있다. 

각 행 index는 내일 먹을 음식, 열 index는 오늘 먹을 음식을 의미하고, 각 원소는 확률이다. 

 

stationary state(=stationary): the system remains in the same state as time elapses, in every observable way
시간이나 관찰 방식이 달라져도 항상 같은 상태를 유지하는 시스템

Markov chain에서의 stationary distribution은 시간이 지남에 따라 Markov chain에서 변하지 않는 확률 분포를 의미한다. 일반적으로 원소들의 합이 1인 row vector π와 transition matrix P로 표시된다.

 

π=πP

즉, π는 P에 의해 변하지 않는다. eigenvector 식인 Av=λv에서 eigenvalue λ=1, eigenvector v=π인 경우와 같다.

 

따라서 Markov chain의 stationary distribution은 λ=1으로 두고 π를 찾으면 된다. 이 distribution은 특정 state가 발생할 확률이 같다는 것으로 해석할 수 있다.

예를 들어, 위 음식 예제의 stationary distribution π=[0.35211, 0.21127, 0.43662]인데, 햄버거, 피자, 핫도그 각각이 발생할 총 확률(관측 기간에서 각 음식이 발생한 횟수/총 기간)이 distribution과 같다는 뜻이다.

 

확률이기 때문에 distribution의 각 원소는 0 이상이어야 하며, 합은 1이다.

 

 

 

 

 

Reference

https://www.youtube.com/watch?v=i3AkTO9HLXo 

https://brilliant.org/wiki/stationary-distributions/