[확률과정] 1.2 Markov Chain

어느 시간 \(t\)에 내리는 결정은 그 이전 시간에 내린 모든 결정의 결과에 영향을 받는 것이 일반적인 관점일 것이다. 예를 들어, 점심 식사 메뉴를 선택할 때, 월요일에 한식을 먹고, 화요일에 분식을 먹었는데 둘다 맛이 보통이었다면, 수요일엔 아마 다른 선택을 할 것이다. 그러나 경우에 따라서는, 다음 상태의 확률이 바로 그 직전의 상태에만 영향을 받는 경우도 존재한다. 모노폴리 게임을 예로 들어보자.

 

fir0002 flagstaffotos [at] gmail.com Canon 20D + Canon 70-200mm f/2.8 L, GFDL 1.2, via Wikimedia Commons

 

만약 현재 나의 위치를 왼쪽 위 가장자리의 Free Parking에 있고, Fleet Street에 도착하여 빨간색을 모노폴리하기 위해 3이 나오길 기대하는 상황이다. 내 차례가 되어 주사위를 던지고 난 다음 나의 위치는, 내가 지금까지 몇번을 거쳐서 Free Parking에 도달했는지, 내가 어떤 Chance 카드를 보았는지와 전혀 상관없이 오직 이전의 상태, Free Parking에 있었다는 것만이 영향을 미친다.

 

이렇게 \(t\) 시점의 상태는 바로 직전 \(t-1\) 시점의 상태에만 영향을 받는 stochastic process를 Markov chain(마르코프 연쇄)라고 부른다.

 

#Markov chain

stochastic process \(\{X_t\}_{t=0,1,2,...}\)를 생각해보자. 위에서 설명한 것과 같이 n번째 상태 \(X_n\)는 바로 직전의 상태인 \(X_{n-1}\)에만 영향을 받는 것을 Markov property라고 한다.

 

DEFINITION          Markov property

모든 transition probability \(p_n(i_n|i_0,i_1,...,i_{n-1})\)이 \[ p_n(i_n|i_0,i_1,...,i_{n-1}) = P(X_n=i_n|X_{n-1}=i_{n-1}) = p_n(i_n|i_{n-1}) \]을 만족하는 경우, \(X_t\)는 Markov property를 가진다고 부른다.

 

Markov property를 만족하는 경우, \(X\)가 거쳐온 과거 히스토리는 더이상 중요하지 않고, 현재 어떤 상태인지가 중요하게 되며, 다음 상태가 어떤 값이 될지는 오직 현재 상태의 값에만 영향을 받게 된다. 다음 그림을 살펴보자.

 

 

Joxemai4, CC BY-SA 3.0, via Wikimedia Commons

 

이 그림에서 원은 state를 표현한다. 여기에서 \(X_t\)의 state는 A와 E만 존재한다. 화살표는 transition을 표현한다. 예를 들어 A에서 E를 향하는 화살표는 A에서 E로의 transition을 표현하고, 숫자는 transition probability를 표현하고 있다. 즉, \(p_t(E|A)=0.4\), "이전 상태가 A일 때 다음 상태가 E일 확률이 40%"라는 뜻이다. 마찬가지로 A에서 다시 A로 향하는 화살표와 숫자는 "이전 상태가 A일 때 다음 상태가 A일 확률이 60%"이라는 것을 표현하고 있다. 이 그림이 표현하는 stochastic process는 원으로 표현된 state A, E를 시간에 따라 화살표에 적힌 확률로 왔다갔다하는 것으로 이해할 수 있다. 이렇게 Markov property를 가지는 stochastic process를 Markov chain이라고 부른다.^[각주:1]

#probability calculation

위 그림의 Markov chain이 실제로 실행된다면, 시간이 지남에 따라 \(X\)의 값이 A와 E 사이를 왔다갔다 하는 것을 볼 수 있을 것이다. 우선 Markov chain을 시작하는 시점에서 상태는 A와 E 중에서 결정되어 있어야 한다. 이를 initial state라고 부른다. 보통 initial state의 시간을 \(t=0\) 으로 선택하는데, 필요에 따라 다른 값을 선택하기도 한다. 만약 initial state로 E를 선택하면, 시간이 지남에 따라 \(X\) 값이 변하는 것을 관찰할 수 있을 것이다.

\(t\)	0 (initial state)	1	2	3	...
\(X\)	E	A	A	E	...

 

물론 다른 가능성도 있다.

\(t\)	0 (initial state)	1	2	3	...
\(X\)	E	E	E	A	...

 

그렇다면 1번째 체인 EAAE와 2번째 체인 EEEA 중에서 어떤 것이 더 관측될 확률이 높을까? 그림에 있는 transition probability를 자세히 살펴봤을 때, E에서 A로 전이될 확률은 높지만, A에서 E로 전이될 확률은 낮다는 것을 알 수 있다. 따라서 E가 연속으로 많이 나오는 2번째 체인의 확률이 더 낮을 것이라는 예측은 할 수 있을 것이다.

 

각 체인이 관측될 확률이 바로 joint probability^[각주:2]를 계산하는 것이다. conditional probability의 정의^[각주:3]로부터

\[ \begin{align*} P(X_0=E, &X_1=A, X_2=A, X_3=E) \\ \\ &= P(X_3=E|X_0=E, X_1=A, X_2=A)\times P(X_2=A|X_1=A,X_0=E)\times P(X_1=A|X_0=E) \end{align*} \]

우변의 각 conditional probability는 transition probability^[각주:4]이다. Markov chain은 Markov property를 가지므로 각 conditional probability는 마지막 state에 대해서만 조건이 적용된다. 즉,

\[ P(X_3=E|X_0=E, X_1=A, X_2=A) = p(E|A) \]

그림에서 이 transition probability는 0.4라는 것을 확인할 수 있다. 따라서

\[ \begin{align*} P(X_0=E, X_1=A, X_2=A, X_3=E) &= p(E|A)p(A|A)p(A|E) \\ \\ &= 0.4\times 0.6 \times 0.7 = 0.168 \end{align*} \]

즉, 1번째 체인이 나올 확률은 16.8%이다. 마찬가지로 2번째 체인은

\[ \begin{align*} P(X_0=E, X_1=E, X_2=E, X_3=A) &= p(A|E)p(E|E)p(E|E) \\ \\ &= 0.7\times 0.3 \times 0.3 = 0.063 \end{align*} \]

위에서 예측했던 것처럼, 2번째 체인 EEEA가 나타날 확률이 1번째 체인 EAAE가 나타날 확률보다 낮다는 것을 계산할 수 있다.

 

또 흥미로운 질문은 \(t=3\)일 때, state가 A일 확률은 얼마일까? state가 E일 확률은? 이 개념이 바로 marginal probability^[각주:5]이다. marginal probability의 정의를 그대로 따라가면, \(t=3\)일 때 state가 A가 되는 모든 체인의 확률을 더하는 것으로 계산할 수 있다.

\[P(X_3=A) = \sum _{a = A,E} \sum _{b = A,E} P(X_0=E,X_1=a,X_2=b,X_3=A) \]

그래도 \(t=3\)일 때 state가 A인 경우의 수가 4개 밖에 없어서 이렇게 계산하는 것이 가능하지만, \(t=10\)일 때와 같이 \(t\)가 큰 경우에는 매우 비효율적일 것이다. 이러한 계산을 쉽게 하기 위해서, 다음에 설명할 transition probability matrix를 이용할 수 있다.

 

1. 더 일반적인 경우에는 시간에 따라 transition probability가 변하는 경우도 고려할 수 있다. 즉 처음에는 A에서 E로 전이할 확률이 40%이지만, 시간이 지나면 80%로 커지는 경우를 생각해볼 수 있을 것이다. 여기에서는 논의를 간단히 하기 위하여 transition probability가 시간에 따라 변하지 않는다고 가정할 것이다. 이러한 특성을 time-homogeneous property라고 부른다. [본문으로]
2. joint probability에 대해서는 [통계학] 4.1 다중 랜덤 변수 Multiple Random Variables [본문으로]
3. conditional probability 정의는 [통계학] 1.3 조건부 확률, 독립 사건 Conditional Probability, Independent Events [본문으로]
4. transition probability는 1.1 Stochastic process [본문으로]
5. marginal probability에 대해서는 [통계학] 4.1 다중 랜덤 변수 Multiple Random Variables [본문으로]