고등학생 때 처음 확률과 통계를 접했을 때 참 아리송~ 했었는데 아직도 확률은 참 어려운 것 같습니다.
마르코프 체인이란 과거의 상태에 따라 현재 상태의 확률이 결정되는 확률 모델을 의미하는데요.
어제 비가 왔을 때 오늘 비가 올 확률
위와 같은 문제를 많이 보셨을 것 같아요.
오늘 설명드릴 "Absorbing Markov Chain" 은 우리말로 번역하면 흡수 마르코프 체인 또는 흡수 마르코프 연쇄로 해석이 됩니다.
마르코프 체인에서 계속해서 상태 전이가 발생할 때 Steady State , 무한 번 상태 전이가 발생했을 때 결국엔 특정 안정 상태로 가게되는 확률 모델을 의미합니다.
예를 들어 볼게요.
1. 문제
어떤 물질이 주기적으로 화학반응을 반복하며 상태가 변화한다. 충분한 시간이 흐른 후, 특정 상태에서 더 이상 변화하지 않고 각 상태 전이별 확률이 주어질 때 최종 상태별 상태 전이가 수렴할 확률은?
State Diagram 표현
Absorbing Markov Chain 모델을 가장 이해하기 쉽게 표현한 그림은 State Diagram으로 표현되는 그래프 모델입니다.
각 노드는 상태를 표현하고, 엣지는 상태 전이 확률을 의미합니다.
분홍색 엣지는 현재 상태가 A일 때 다음 상태가 다시 A가 될 획률, 즉 상태가 머무를 확률을 의미합니다.
따라서 각 노드에서 나가는 엣지의 합은 1 (100%)가 되어야 합니다.
위 그래프에서 한 번 C 상태나 D 상태가 되면 더 이상 상태가 변하지 않는 것을 확인할 수 있습니다.
이를 따라서 이러한 상태를 Steady State라 하고 이러한 노드를 말단 노드, Terminal Node라고 합니다.
Markov Matrix
앞서 설명한 State Diagram은 모델을 이해하기에 편하고 직관적이지만 계산을 위해 사용하기에는 한계가 있습니다. 따라서 이를 행렬 (Matrix)로 표현하곤 합니다. 각 행을 Input, 열을 Output이라 할 때 Input 상태가 Output 상태가 될 확률을 행렬로 표현할 수 있습니다. 위 State Diagram을 행렬로 표현해보면,
$ \begin{bmatrix}
0.4 & 0.4 & 0.2 & 0 \\
0.5 & 0 & 0 & 0.5 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix} $
감이 잡히시나요? 각 행 번호는 Source, 각 열 번호는 Destination이라고 할 때 Source에서 Destination으로 상태가 변경될 확률입니다. 이 그래프에서는 A, B, C, D 순서대로 행과 열을 배열했습니다.
이 Matrix를 이용하면 다음과 같은 계산이 편해집니다.
"현재 상태가 될 확률이 X일 때 다음 상태가 될 확률은?"
$X = \begin{bmatrix}
0.25 & 0.25 & 0.25 & 0.25
\end{bmatrix}$
단순히 $X$에 위 Matrix 행렬 $P$를 곱해주는 것으로 다음 상태가될 확률들을 구할 수 있습니다.
왜냐면, $X$에서 각열은 현재 상태가 각각 A, B, C, D가 될 확률을 의미하는데 다음 상태 $X'$에서 A가 될 확률은
A에서 A가 될 확률 + A에서 B가 될 확률 + A에서 C가 될 확률 + A에서 D가 될 확률 입니다.
$X'_A = X_A \times P_{AA} + X_B \times P_{BA} + X_C \times P_{CA} + X_D \times P_{DA}$
즉, 두 Matrix를 곱한 첫 번 째 열에 해당하게 됩니다.
Standard Form of Absorbing Markov Chain
Absorbing Markov Chain에는 두 가지 Node 상태가 있습니다.
일반 Node와 특정 상태에 도달하면 더 이상 상태 변화가 발생하지 않는 Terminal Node입니다.
명확히 구분하기 위하여 일반 Node를 Non-Terminal Node 즉, NT Node라고 해보겠습니다.
$NT = \{A, B\}$
$T = \{C, D\}$
다음과 같이 Matrix 내 Element를 재배치해봅니다.
- T -> T
- T -> NT
- NT -> NT
- NT -> T
행 순서 및 열 순서를 Terminal Node 먼저 나오도록 $\{C, D, A, B\}$로 바꿔봅니다.
$ P = \begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0.2 & 0 & 0.4 & 0.4 \\
0 & 0.5 & 0.5 & 0
\end{bmatrix} $
이렇게 변경하고 나면 특정 패턴이 나타나는데요
좌측 상단은 Identity 행렬, 우측 상단은 영행렬이 됩니다.
이를 기준으로 각각 I행렬 밑 부분을 R, 영행렬 밑 부분을 Q 행렬로 표현하면 아래와 같은 표준형이 됩니다.
$ P = \begin{bmatrix}
I & O \\
R & Q
\end{bmatrix} $
이 표준형의 특징은 P가 무한으로 반복될 때 P는 $ \bar{P} $ 로 수렴한다는 특징을 갖습니다.
그리고 $ \bar{P} $ 는 아래와 같은 형태가 되죠.
$ \bar{P} = \begin{bmatrix}
I & O \\
FR & O
\end{bmatrix} $
$ F = (I - Q)^-1 $
바로 $ \bar{P} $ 의 X 행 Y 열이 의미하는 바는 P Matrix를 가진 Markov Chain이 계속해서 반복될 때 초기 상태 X가 최종 상태 Y가 되어 더 이상변화하지 않을 확률입니다.
$ \bar{P} $ 를 구하기 위해 F를 구하고 FR을 구해보면,
$ F = \begin{bmatrix}
1 - 0.4 & 0 - 0.4 \\
0 - 0.5 & 1 - 0
\end{bmatrix}^{-1} = \begin{bmatrix}
2.5 & 1 \\
1.25 & 1.5
\end{bmatrix} $
$ FR = \begin{bmatrix}
0.5 & 0.5 \\
0.25 & 0.75
\end{bmatrix} $
이 되고 최종 $ \bar{P} $ 는 아래와 같습니다.
$ \bar{P} = \begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0.5 & 0.5 & 0 & 0 \\
0.25 & 0.75 & 0 & 0
\end{bmatrix} $
즉, 최초 상태가 A일 때 C로 수렴할 확률은 50%, B일 때 D로 수렴할 확률은 75%입니다.