Markov Chain #

개요 #

시간이 지남에 따라 바뀔 수 있는 시스템을 연구할 때 이러한 변화를 추적할 방법이 필요하다. Markov Chain는 주어진 확률에 따라 변화하는 시스템을 추적하는 특정 모델이다. Markov Chain은 다음과 같은 Markov 특성을 가지는 이산시간 확률 프로세스이다.

$$P({ C }_{ t+1 }|{ C }_{ t },\cdots ,{ C }_{ 1 })=P({ C }_{ t+1 }|{ C }_{ t })$$

이때 특정 시간 t 동안 특정 상태 i에서 특정한 다른 상태 j로 전이할 확률을 전이 확률(Transition Probability)이라고 한다.

$${ \gamma }_{ ij }(t)=P({ C }_{ s+t }=j|{ C }_{ s }=i)$$

또한, 모든 상태 조합에 대한 전이 확률을 나타낸 것이 전이 확률 행렬(Transition Probability Matrix)이다.

$${ \Gamma }(t)=\{ { \gamma }_{ ij }(t)\} ,\quad { \Gamma }={ \Gamma }(1)$$

Chapman-Kolmogrov Equation에 의하면 시간 t+u의 전이 확률 행렬은 시간 t의 전이 확률 행렬과 시간 u의 전이 확률 행렬의 곱으로 나타난다.

$${ \Gamma }(t+u)={ \Gamma }(t){ \Gamma }(u)$$

Markov Chain은 미래의 사건을 예측할 수는 있지만, 미래의 사건에 대해서는 예측이 덜 유용하게 된다. (주식 시장이나 날씨의 예측과 비슷하다.)

Markov Chain을 이해하기 위해서는 행렬 산술에 대한 사전 지식이 필요하다.

상태란 시스템에서 가능한 특정 상황을 말한다. 예를 들어 비 오는 날을 공부하고 있다면 다음과 같은 두 가지 상태가 있다.

• 오늘 비가 오고 있다.
• 오늘 비가 오고 있지 않다.

Markov Chain이라는 용어는 일정한 수의 상태와 주어진 확률로 시스템이 어떤 상태에서 다른 상태로 바뀌는 모든 시스템을 나타낸다.

한 번에 받아들여야 할 것이 많으므로 비 오는 날의 예를 사용하여 설명하자면, 시스템의 확률은 다음과 같다.

오늘 비가 내리는 경우 (R), 내일 비가 내릴 확률은 40%, 비가 내리지 않을 확률은 60%이다. 오늘 비가 오지 않으면 (N), 내일 비가 내릴 확률은 20%, 비가 내리지 않을 확률은 80%이다.

Transition Matrix #

Markov Chain이 k개의 상태로 구성되어있는 경우, 전이 행렬은 각 상태에서 다른 상태로 이동할 확률을 기록하는 k*k 행렬이다. 행렬의 행은 현재 상태에 해당하고 열은 다음 상태에 해당한다. 예를 들어, 행 1과 2의 항목은 상태 1에서 2로 이동할 확률을 기록한다.

위의 예시를 이용해 전환 행렬을 만들어 보자. R이 항상 N보다 먼저 온다고 가정했을 때 첫 번째 행과 첫 번째 열은 R을 의미하고 두 번째 행과 두 번째 열은 N을 의미한다. 행은 from을 의미하고 열은 to를 의미한다.

R에서 R로의 전환은 0.4이므로 행렬의 왼쪽 위에 0.4를 넣는다. R에서 N으로의 전환은 0.6이다. N에서 R은 0.2, N에서 N은 0.8이다.

$$ P\quad =\quad \begin{pmatrix} 0.4 & 0.6 \\ 0.2 & 0.8 \end{pmatrix} $$

참고 문헌 #

• Hidden Markov Model.1
• Markov Chain: Definition, Applications & Examples2