Markov Chain & Stationary Distribution
Markov Chain은 학부 시절 확률적 OR이었나… 뭐 비슷한 수업에서 처음 들어본 개념이다. 뭐 굳이 OR을 가지고 올 필요 없이, 확률론에서도 이 개념이 등장하는 것으로 알고 있다.
Markov Chain은 쉽게 말해 여러 State를 갖는 Chain 형태의 구조를 일컫는다. 무엇이 되었건 State가 존재하고, 각 State를 넘나드는 어떤 확률값이 존재하며, 다음 State는 현재 State 값에만 의존(Markov Property)한다면, 이는 모두 Markov Chain이다.
MCMC라는 개념에도 등장하는 것이 바로 Markov Chain인데, MCMC에서는 Markov Chain이 Stationary Distribution을 가져야만 작동 가능한 것으로 규정되어 있다. 더욱 엄밀히 말하자면, Unique Stationary Distribution을 가지고, Limiting Distribution을 가져야 한다.
그렇다면 이 Stationary Distribution은 무엇인가?
쉽게 표현하자면 aP = a 형태를 만족하는 a를 Stationary Distribution이라고 한다. 여기서 P는 Transition Matrix다. 위의 식을 풀이해보면, 어떤 Transition 확률이 존재할 때, vector a가 얼마 만큼의 Transition이 이뤄지건 간에 동일한 a로 남는다는 얘기다. 즉 특정 State가 발생할 확률이 늘상 같다는 말이다.
위 슬라이드를 보면 P가 주어졌을 때, (1/3, 1/3, 1/3) 벡터는 P를 몇번이고 곱해도 (1/3, 1/3, 1/3)이다.
MCMC에서는 모든 State를 넘나들 수 있다는 점을 근거로 삼는데, Stationary Distribution은 이 가정의 모체가 된다.
하나 짚고 넘어가야 할 부분은 모든 Markov Chain이 Unique Stationary Distribution을 가지진 않는다는 것이다. Intuitive하게 접근해보면, 만일 Chain 내의 특정 node 둘이 서로 Cycle 관계에 놓여있다고 하면, 해당 node에서는 적어도 두 번 이상의 transition을 수행해야 출발한 위치로 돌아올 수 있다. 이 경우엔 Unique Stationary Distribution이 존재하는 것이 말이 안된다. 왜냐면 시작점에서 바로 시작점으로 갈 수 없는 조건이기 때문이다. 이 처럼 특정 node 사이 관계가 1을 초과하는 주기값을 갖는 Chain(Periodic)에 한해서는 Unique Stationary Dist.가 존재할 수 없다. 반대로 node 간에 이러한 주기성이 없는 경우는 aperiodic(주기가 1이라는 소린데, 사실 없다는 이야기와 같지 않나) chain이라고 부르며, Unique Stationary Chain이 될 수 있는 필요 조건 중 하나가 된다.
Stationary Dist.가 존재할 수 있는 두 번째 조건은 한 state에서 다른 state로 넘어갈 확률은 모두 0을 넘는 값이어야 한다는 사실이다. (Irreducible)
이 경우도 직관적으로 이해가 가능한데, 특정 State에서는 전체 Chain의 일부 State로만 이동이 가능한 경우를 떠올려보자. 아래 그림에서 두 번째 Chain이 이에 해당한다.
Reducible Chain에서 4번 State를 보면, 1번 State에서의 전이만 설정이 되어 있고, 다시 1번으로 돌려주는 전이가 정의되어 있지 않다. 이 체인을 무한히 작동시킨다고 하면, 4번 State로 빠지는 순간 순환이 이뤄질 수 없다고 볼 수 있다. 블랙홀처럼 그저 빨아들이기만 하는 4번 State와 같은 경우를 Absorbing State라고 한다.
마찬가지로, 1번 State에서 2번 State로의 이동이 이뤄지고 나면, 이후의 동작은 State 2번과 3번 사이에서만 발생하게 된다. 2–3번 State 중에는 Absorbing State가 존재하지 않으니, Chain은 이 조건 하에서는 멈추지 않는다.
Irreducible Markov Chain은 단어 의미 그대로 받아들이면, 더 줄일 수 없는 Chain이라고 볼 수 있다. ‘더 줄일 수 없다’는 말은 순환이 Chain 내에 특정 Set에 맴돌지 않는다는 말처럼 느껴진다. 아래 Reducible Case의 2–3번 State는 그 둘만 떼어놓고 보면 모든 State로의 전이가 자유자재인 Irreducible Chain의 형태이다.
Stationary Dist.가 존재할 마지막 조건은 State i를 이제 막 지나친 순환이 유한한 시간 내에 다시 State i를 재방문할 수 있어야 한다는 점이다. 이 조건을 만족하는 MC를 Positive Recurrent Markov Chain이라고 한다. 이는 위에서 언급한 Absorbing State와 어느 정도 의미가 통한다고 볼 수 있는데, 특정 State j에서 나머지 모든 State로 이동할 수 있는 확률이 정의되어 있다해도, 그 확률이 상대적으로 매우 작을 경우에는, 해당 State에 갇히게 될 가능성이 있다. 이런 경우에는 State i에서 출발한 순환이 다시 i로 돌아오기까지 너~무도 긴 시간이 소요될 것이다.
사실 나도 얼마전까지는 Stationary Dist에 대해서는 딱 위의 내용까지만을 파악하고 있었다. 하지만 최근 이 Stationary Dist.에 Limit를 씌운 형태인 Limiting Distribution이 존재한다는 점을 알게 되었다. 이 부분에 대해서는 더 공부를 해보고 적어볼 계획이다.
