[Statistics 110] Lecture 31: Markov Chains

Markov Chains

$X_0,X_1,...$에서 $X_n$을 discrete time n에서의 state라고 생각

Markov Property

$$ P(X_{n+1}=j|X_n=i_n,X_{n-1}=i_{n-1},...X_0=i_0)\\ =P(X_{n+1}=j|X_n=i_n) = q_{ij} $$

과거의 모든 정보가 주어졌을 때 다음 state에 대한 확률은 현재 state만 아는 경우에서의 다음 state 확률과 동일 = (과거와 미래는 현재의 상태가 주어졌을 때 조건부 독립이 성립)

$q_{ij}$는 Transition probability(전이확률)로 시간과 독립(n에 독립)으로 이러한 마르코프 체인을 동질 마르코프 체인이라고 부름

 

그림을 보면 직관적으로 이해가 되는데, state 1, 2, 3, 4를 오가는 입자가 있다고 생각해보자 각 state 간 이동은 그림에 있는 확률에 의해서 이루어진다. 동질 마르코프 체인(이하 마르코프 체인)의 특성은 과거에 어떤 state를 얼마나 방문했는지는 중요하지 않다는 것이다. (1→2→3을 이동한 입자의 3→4 확률은, 1→1→2→3→4→3을 따라 이동한 입자의 3→4 확률과 동일)

state 간 전이확률은 모아서 matrix 꼴로 나타낸 것을 전이행렬(Transition Matrix)라고 한다. 위 그림의 예시에서 전이행렬은 아래와 같다. (좌측상단부터 state 1,2,3,4, $q_{ij}$는 i에서 j로 전이될 확률)

 

$$ \begin{pmatrix}1/3 & 2/3 & 0 &0 \\ 1/2 & 0 &  1/2& 0\\  0& 0 & 0 & 1\\  1/2& 0 & 1/4 & 1/4\end{pmatrix} $$

마르코프 체인은 생물학, 물리학 등 여러 분야에 근사를 위해 사용되지만 강력한 가정인 “현재 state를 알면 과거 state를 고려하지 않음”이 있기 때문에 주가, 날씨 등이 마르코프 체인으로 모델링되어도 되는가에 대한 논쟁이 지속되고 있음

Markov chain Monte Carlo(MCMC)

확률분포로부터 원하는 정적분포를 가지는 표본을 추출하는 알고리즘 중 하나

원하는 분포에 수렴하도록 커스텀 마르코프 체인 설계를 하는것으로 계산이 어려운 상황을 시뮬레이션 할 수 있는 도구, 매우 다양한 분야에서 사용

Stationary Distribution

마르코프 체인이 반복되면 수렴하는 지점은?

$\vec s(1\times M)$가 $\vec sQ = \vec s$를 만족하면 stationary distribution

 

Reference

[0] https://www.youtube.com/playlist?list=PL2SOU6wwxB0uwwH80KTQ6ht66KWxbzTIo 

Statistics 110: Probability