선대/마르코프 연쇄(Markov Chain)와 확률 행렬(Stochastic Matrix)

마르코프 연쇄란 시간에 따른 어떤 계의 상태가 확률적으로 변화하는 과정과 결과를 나타낸다. 또는 이산 확률 과정 중 마르코프 특성을 따르는 것이라고도 한다. 마르코프 특성이 뭔지 그 정의부터 시작하면 어려우니까 예시를 하나 들어보자.


가령 (프리드버그 선대책에 나온 예시인데) 어떤 학교에서 학년은 2개 뿐이고 1학년이 내년에 학교를 그만둘 확률 0.2, 유급해서 1학년으로 남을 확률 0.1, 2학년으로 진학할 확률 0.7, 졸업할 확률은 0이라고 하자. 또, 2학년 중 학교를 그만 둘 확률 0.3, 1학년으로 떨어질 확률은 0, 유급할 확률 0.2, 졸업할 확률 0.5라고 하자. 졸업하거나 자퇴한 사람은 재입학하지 않는다고 간주한다. 그럼 아래 행렬을 보자.

$$A =
\begin{bmatrix}
1 & 0.2 & 0.3 & 0\\
0 & 0.1 & 0   & 0\\
0 & 0.7 & 0.2 & 0\\
0 & 0   & 0.5 & 1
\end{bmatrix}
$$

행렬 A는 다음 해에 각 상태에 있는 사람들이 어떤 확률로 어떤 상태가 되는지를 나타낸다. 4x4 행렬이므로 상태는 4개가 있다. 자퇴자, 1학년, 2학년, 졸업자. 이걸 각각 상태 1,2,3,4 라고 할 수도 있다.
1, 2, 3, 4번째의 행과 열은 각각 4개의 상태에 대응한다. 가령 3행 2열을 보면, 지금 상태 2(1학년)인 사람이 상태 3(2학년)이 될 확률은 0.7이다. 4행 4열에서 졸업자는 다음 해에도 졸업자일 테니 졸업자가 다음 해 졸업자가 될 확률은 1이다.

각 열은 한 상태에서 다른 상태로 갈 확률을 나타내므로, 그 합은 항상 1이 된다. 이렇게 각 열 성분들의 합이 1이고, 음수인 성분이 없는 정방행렬을 확률행렬이라고 부른다. 확률 행렬이 곧 마르코프 행렬이라고도 한다.

예제로 돌아와서, 각 년도는 단계(stage), 각 학년은 상태(state)에 해당한다. 그리고 어떤 열벡터가 성분의 합이 1이면 확률 벡터(probability vector)라고 한다. 이 때 확률 벡터 P, 즉 초기값이 다음과 같이 있다고 하자.

$$P =
\begin{bmatrix}
0.2 \\
0.3 \\
0.3 \\
0.2
\end{bmatrix}
$$

즉 이 해를 n년이라고 하면 n년의 전체 인원 중 자퇴자는 20%, 1학년은 30%, 2학년도 30%, 졸업자는 20%인 셈이다. 여기에 A를 곱해주면 n+1년의 인원 비가 되고, A를 m번 곱해주면 n+m년의 인원 비가 되는 셈이다.
그럼 만약 무수히 많은 해가 지난다면 어떻게 될까? 즉 M이 무한대로 갈 때 \(A^mP\) 의 값은 어떻게 되는가?
만약 \( \lim_{m \to \infty}A^mP \) 가 존재한다면, 이를 안정 상태라고 부른다. 즉 이 상태에서는 몇 년이 지나든 인원 비에 변동이 없다.

처음에 마르코프 연쇄란 마르코프 특성을 따르는 이산 확률 과정이라고 했다. 여기서 마르코프 특성이 무엇이냐면, 한 상태의 확률은 단지 그 바로 전의 상태에만 의존한다는 것이다. 한 상태에서 다른 상태로 옮겨 가는 것은 다른 요인에 의해 영향을 받지 않고, 직전에 어떤 상태였냐에만 영향을 받는다.

마르코프 모델에서 한 단계 더 발전한 은닉 마르코프 모델(Hidden Markov Model)이란 것이 있는데, 은닉치와 관측치를 나눠서 이건 다음에 쓰자. 커피를 다 마시니까 텐션이 떨어졌다.