가역성 (Reversibility)
$ P = (P_{ij}) $ 를 어떤 마르코프 연쇄의 전이행렬이라 하자.
$$ \pi_i P_{ij} = \pi_j P_{ji} $$
모든 $i, j $ 에 대하여 위를 만족하는 $ \pi_i \geq 0 $ 이고, $ \sum_i \pi_i = 1 $ 인 $ \boldsymbol{\pi} = ( \pi_1, \pi_2, \cdots, \pi_M ) $ 이 존재한다고 하자. 이 식을 가역성 조건 또는 세부균형(detailed balance) 조건이라 하며, 이 조건이 성립하면 마르코프 연쇄는 $ \boldsymbol{\pi} $ 에 대해 가역적(reversible)이라 한다.
정상분포에 따라 출발하는 경우, 가역 마르코프 연쇄는 시간 흐름과 관계없이, 즉 순방향이든, 역방향이든 동일한 방식으로 움직인다.
가역성과 정상분포
$ P = (P_{ij}) $ 를 성분 합이 $ 1 $ 인 비음(nonnegative) 벡터 $ \boldsymbol{\pi} = (\pi_1, \pi_2, \cdots, \pi_M) $ 에 대해 가역인 어떤 마르코프 연쇄의 전이행렬이라 하자. 그렇다면 $ \boldsymbol{\pi} $ 는 해당 마르코프 연쇄의 정상분포이다.
가역조건에 따라 다음이 성립한다.
$ \sum_i \pi_i P_{ij} = \sum_i \pi_j P_{ji} = \pi_j \sum_i P_{ji} = \pi_j $
왜냐하면 전이행렬 $ P $ 의 한 행의 원소 합은 $ 1 $ 이기 때문이다.
따라서 $ \boldsymbol{\pi} $ 는 정상분포이다.
선형 연립방정식인 $ \boldsymbol{\pi} P = \boldsymbol{\pi}$ 의 전체 해를 구하는 것보다 가역성 조건을 검증하는 것이 더 쉬울 때가 많기에 이를 활용할 수 있다.
참고로 가역성 조건을 만족하는 $ \boldsymbol{\pi}$ 를 찾는 것이 가능한 대표적 세 마르코프 연쇄가 있다. 하나는 마르코프 연쇄의 전이행렬이 대칭행렬(symmetric matrix)인 경우, 또 하나는 무방향 네트워크에서의 확률보행(random walk on a undirected network), 또 하나는 출생-사망 연쇄(birth-death chains)이다.
대표적 가역 마르코프 연쇄
• 전이행렬이 대칭행렬인 경우
$ P $ 가 대칭행렬이면 정상분포는 상태공간에 대한 균일분포, 즉 $ \boldsymbol{\pi} = (1/M, 1/M, \cdots, 1/M) $ 이다. 또한 $ P $ 가 대칭행렬이면 $ P_{ij} = P_{ji} $ 이다.
가역성 조건은 모든 $i, j $ 에 대해 $ \pi_i P_{ij} = \pi_j P_{ji} $ 가 만족해야 한다는 것이다. 이때, $P$ 가 대칭행렬이므로 $P_{ij} = P_{ji}$ 가 성립하며, 균일분포에서는 모든 상태에 대해 $\pi_i = \pi_j$ 가 성립하므로 가역성 조건을 만족한다..
따라서 정상분포는 균일분포 $ \boldsymbol{\pi} = (1/M, 1/M, \cdots, 1/M) $ 이다.
이를 일반화시킨 것이 이중확률행렬(doubly stochastic matrix)이다. 전이행렬 $ P $ 의 각 열의 성분 합이 $ 1 $ 이면 모든 상태에 대한 균일분포 $ \boldsymbol{\pi} = (1/M, 1/M, \cdots, 1/M) $ 은 정상분포이며, 각 행의 성분 합과 열의 성분 합이 모두 1인 비음 행렬을 이중확률행렬이라고 한다.
• 무방향 네트워크에서의 확률보행 (random walk on a undirected network)
네트워크에서 방랑자(Random Walker)가 특정 노드에서 출발하여 연결된 링크 중 하나를 무작위 균등 확률로 선택해 다음 노드로 이동한다고 가정하자.
이때, 네트워크는 노드 $ 1, 2, \dots, n $ 으로 구성되며, 각 노드의 차수열(degree sequence) $ \mathbf{d} = (d_1, d_2, \dots, d_n) $ 이 주어진다. 여기서 노드 $ i $ 의 차수 $ d_i $ 는 해당 노드에 부속된 링크의 수를 의미하며, 자기 자신으로의 연결(self-loop)이 허용될 경우 차수가 $1$ 증가한다.
서로 다른 모든 $ i $ 와 $ j $ 에 대하여 방랑자의 전이확률은 노드 $ i $ 와 $ j $ 가 링크로 연결되어 있다면 $ P_{ij} = 1 / d_i $, 그렇지 않다면 $ P_{ij} = 0 $ 으로 정의된다.
따라서, 전이행렬 $ P $ 는 가역성을 만족하며, 정상분포 $ \boldsymbol{\pi} $ 는 다음과 같이 차수에 비례하는 형태를 갖는다.
$$ \pi_i = \frac{d_i}{\sum_{j} d_j} $$
예를 들어, 주어진 차수열이 $ (4, 3, 2, 3, 2) $ 라면, 전체 차수의 합은 $ 4 + 3 + 2 + 3 + 2 = 14 $ 이므로, 정상분포는 다음과 같다.
$$ \boldsymbol{\pi} = \left( \frac{4}{14}, \frac{3}{14}, \frac{2}{14}, \frac{3}{14}, \frac{2}{14} \right) $$
• 출생-사망 연쇄 (birth-death chains)
출생-사망 연쇄란 상태공간 $\{1, 2, \dots, M \}$ 에서 이루어지는 마르코프 연쇄로 $ |i - j| = 1 $ 이면 $ P_{ij} > 0 $, $ |i - j| \geq 2 $ 이면 $ P_{ij} = 0 $ 인 전이행렬 $ P = (P_{ij}) $ 를 갖는 마르코프 연쇄이다. 각 상태 $ i $ 에서 자기 자신으로 머무를 확률 $ P_{ii} $ 는 $0$ 이상일 수 있다. 이러한 특성 때문에 출생-사망 연쇄는 한 번에 한 단계씩만 이동하는 형태의 마르코프 과정으로 볼 수 있다.
모든 출생-사망 연쇄는 가역성을 가진다.
$ \pi_1 > 0 $ 이라 하자. $ \pi_1 P_{12} = \pi_2 P_{21} $ 이어야 하므로 다음과 같이 설정하자.
$ \pi_2 = \dfrac{\pi_1 P_{12}}{P_{21}} $
그렇다면 $ \pi_2 P_{23} = \pi_3 P_{32} $ 이어야 하므로 다음과 같이 놓을 수 있다.
$ \pi_3 = \dfrac{\pi_2 P_{23}}{P_{32}} = \pi_1 \dfrac{P_{12}}{P_{21}} \dfrac{P_{23}}{P_{32}} $
반복하면 모든 $ 2 \leq j \leq M $ 에 대하여 다음과 같이 놓을 수 있다.
$ \pi_j = \pi_1 \dfrac{P_{12} P_{23} \cdots P_{j-1,j}}{P_{21} P_{32} \cdots P_{j,j-1}} $
마지막 단계에서 $ \sum_j \pi_j = 1 $ 이 되도록 $ \pi_1 $ 의 해를 구할 수 있다. 그러면 $ \vert i - j \vert = 2 $ 이면 $ P_{ij} = P_{ji} = 0 $ 이고, 출생-사망 연쇄의 구성방식으로부터 $ \vert i - j \vert = 1 $ 이면 $ \pi_i P_{ij} = \pi_j P_{ji} $ 이므로 연쇄는 $ \boldsymbol{\pi} $ 에 대해 가역이다.
따라서 $ \boldsymbol{\pi} $ 는 정상분포이다.
