마르코프 체인과 전이 행렬 - 소프트웨어 융합

마르코프 체인의 개요

마르코프 체인은 이산적인 상태 공간에서 정의되는 확률 과정으로, 현재 상태에 대한 정보만으로 다음 상태에 대한 확률을 결정할 수 있는 특징을 가진다. 이는 조건부 확률이 현재 상태에만 의존한다는 의미로, 수학적으로는 다음과 같이 표현된다.

$\mathbb{P}(X_{n+1} = x_{n+1} \mid X_n = x_n, X_{n-1} = x_{n-1}, \dots, X_0 = x_0) \\ = \mathbb{P}(X_{n+1} = x_{n+1} \mid X_n = x_n)$

여기서 $X_n$ 은 $n$ 번째 시간 단계에서의 상태를 나타낸다.

전이 행렬의 정의

마르코프 체인에서 상태 간의 전이 확률을 나타내는 행렬을 전이 행렬이라고 한다. 만약 상태 공간이 유한하다면, 전이 행렬 $\mathbf{P}$ 는 각 상태 $i$ 에서 다른 상태 $j$ 로 전이될 확률 $p_{ij}$ 를 성분으로 갖는 $n \times n$ 크기의 행렬로 정의된다.

$\mathbf{P} = \begin{pmatrix} p_{11} & p_{12} & \cdots & p_{1n} \\ p_{21} & p_{22} & \cdots & p_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ p_{n1} & p_{n2} & \cdots & p_{nn} \end{pmatrix}$

여기서 $p_{ij} = \mathbb{P}(X_{n+1} = j \mid X_n = i)$ 를 나타낸다. 전이 행렬의 각 행의 성분은 확률을 의미하므로, 각 행의 합은 1이 되어야 한다.

$\sum_{j=1}^{n} p_{ij} = 1 \quad \text{for all } i$

전이 행렬의 성질

전이 행렬 $\mathbf{P}$ 는 마르코프 체인의 다양한 성질을 결정짓는 중요한 역할을 한다. 예를 들어, 전이 행렬을 거듭 제곱함으로써 $k$ 단계 후의 전이 확률을 계산할 수 있다. $k$ 단계 후의 전이 확률 행렬 $\mathbf{P}^k$ 는 다음과 같이 계산된다.

$\mathbf{P}^k = \mathbf{P} \times \mathbf{P} \times \cdots \times \mathbf{P} \quad (k \text{ times})$

여기서, $\mathbf{P}^k = \left( p_{ij}^{(k)} \right)$ 는 상태 $i$ 에서 $k$ 단계 후에 상태 $j$ 로 전이될 확률을 나타낸다.

상태 분류와 흡수 상태

마르코프 체인의 상태들은 그 성질에 따라 여러 가지로 분류될 수 있다. 주요 분류로는 재귀적 상태(recurrent state), 비재귀적 상태(transient state), 그리고 흡수 상태(absorbing state) 등이 있다.

재귀적 상태와 비재귀적 상태

재귀적 상태는 한 번 방문한 후에 다시 방문할 확률이 1인 상태를 말한다. 즉, 상태 $i$ 가 재귀적 상태라면, 언젠가 다시 그 상태로 돌아오게 된다.
비재귀적 상태는 방문 후에 다시 그 상태로 돌아올 확률이 1보다 작은 상태를 말한다. 이 경우, 비재귀적 상태는 언젠가는 체인에서 사라지게 된다.

흡수 상태

흡수 상태란, 한 번 그 상태로 진입하면 더 이상 다른 상태로 전이되지 않고 그 상태에 머물게 되는 상태를 의미한다. 수학적으로 흡수 상태 $j$ 는 전이 행렬의 $p_{jj} = 1$ 이고, 다른 모든 $i \neq j$ 에 대해 $p_{ji} = 0$ 인 상태로 정의된다.

마르코프 체인의 장기 거동

마르코프 체인의 장기적인 거동을 분석하기 위해 평균 도달 시간(mean first passage time)이나 정상 분포(steady-state distribution) 같은 개념이 사용된다.

평균 도달 시간

평균 도달 시간은 특정 상태 $j$ 에 처음 도달하기까지 걸리는 평균 시간(혹은 단계 수)을 의미한다. 상태 $i$ 에서 $j$ 로의 평균 도달 시간을 $\mathbf{M}_{ij}$ 로 나타낼 수 있다.

정상 분포

마르코프 체인의 상태들이 시간이 충분히 경과한 후에 어떤 확률 분포로 수렴한다면, 이 분포를 정상 분포 또는 정적 분포(stationary distribution)라고 한다. 전이 행렬 $\mathbf{P}$ 의 정상 분포 $\mathbf{\pi}$ 는 다음을 만족하는 벡터로 정의된다.

$\mathbf{\pi} \mathbf{P} = \mathbf{\pi}$

즉, 정상 분포는 전이 행렬과 곱해도 변화하지 않는 고정된 분포를 의미한다.

전이 행렬과 고유값, 고유벡터

전이 행렬 $\mathbf{P}$ 의 고유값과 고유벡터는 마르코프 체인의 장기적인 행동을 분석하는 데 중요한 역할을 한다. 특히, 전이 행렬의 가장 큰 고유값은 1이며, 이 고유값에 대응하는 고유벡터가 정상 분포를 나타낸다.

$\mathbf{P} \mathbf{v} = \lambda \mathbf{v}$

여기서 $\lambda = 1$ 인 고유벡터 $\mathbf{v}$ 가 정상 분포를 형성한다.

상태 간의 연결성

마르코프 체인의 상태들은 서로 연결될 수 있으며, 모든 상태가 서로 연결되어 있다면 이를 불가약적(irreducible) 마르코프 체인이라고 한다. 불가약적 체인은 상태들 간의 전이가 가능하므로, 전체 상태 공간을 대상으로 분석할 수 있다.

불가약 마르코프 체인

불가약 마르코프 체인은 모든 상태에서 다른 모든 상태로 전이될 가능성이 있는 체인을 의미한다. 즉, 어떤 상태 $i$ 에서 다른 상태 $j$ 로 전이될 확률이 0이 아닌 경로가 존재한다. 불가약 체인은 다음과 같은 중요한 성질을 가진다:

고유한 정상 분포: 불가약 체인은 고유한 정상 분포를 가진다. 이는 상태 간의 전이가 서로 가능하기 때문에 시간이 충분히 지나면 일정한 확률 분포에 수렴하게 된다.
모든 상태가 재귀적: 불가약 체인에서는 모든 상태가 재귀적이다. 즉, 모든 상태는 언젠가 다시 방문하게 된다.

에르고딕 마르코프 체인

에르고딕(ergodic) 마르코프 체인은 불가약 체인 중에서도 추가적인 성질을 만족하는 체인을 말한다. 에르고딕 체인은 다음 두 가지 조건을 만족해야 한다:

불가약성: 모든 상태가 서로 연결되어 있어야 한다.
비주기성: 체인의 상태 간 이동이 특정 주기에 얽매이지 않고 임의의 시간에 일어날 수 있어야 한다.

에르고딕 체인은 장기적으로 모든 상태에 대해 동일한 비율로 방문하게 되며, 이는 전체 상태 공간에 대해 균등한 확률 분포에 수렴하는 성질을 가진다.

전이 행렬의 수렴과 혼합 시간

마르코프 체인의 전이 행렬은 충분히 많은 시간이 지나면 정상 분포로 수렴하게 되는데, 이 과정에서 중요한 개념이 혼합 시간(mixing time)이다. 혼합 시간은 초기 상태의 영향이 사라지고 체인이 정상 분포에 근접하는 데 걸리는 시간을 의미한다. 수학적으로 혼합 시간 $T(\epsilon)$ 은 다음과 같이 정의된다:

$T(\epsilon) = \min \{ t : \|\mathbf{P}^t(i, \cdot) - \mathbf{\pi} \| < \epsilon \text{ for all } i \}$

여기서 $\mathbf{P}^t(i, \cdot)$ 는 $t$ 단계 후에 상태 $i$ 에서 각 상태로 전이될 확률 분포를 의미하고, $\mathbf{\pi}$ 는 정상 분포를 의미한다.

응용: 마르코프 연쇄 몬테카를로 (MCMC)

마르코프 체인과 전이 행렬은 다양한 응용 분야에서 중요한 역할을 한다. 그 중에서도 마르코프 연쇄 몬테카를로(Markov Chain Monte Carlo, MCMC) 방법은 확률 분포를 근사적으로 계산하는 데 사용된다. MCMC는 대상 분포를 샘플링하기 위해 마르코프 체인을 이용하며, 이 과정에서 전이 행렬이 샘플링의 효율성을 결정한다.

MCMC 알고리즘의 기본 원리

MCMC 알고리즘은 다음과 같은 절차를 따른다:

초기 상태에서 시작하여, 정의된 전이 행렬에 따라 상태를 변화시킨다.
충분히 많은 단계를 거쳐 정상 분포에 도달하게 된다.
수렴한 후의 샘플들을 이용해 대상 분포를 근사적으로 추정한다.

이 과정에서 전이 행렬이 잘 설계되면, MCMC 알고리즘은 대상 분포를 빠르고 정확하게 근사할 수 있다.