8.50 상태 전이 행렬과 정상 분포

1. 상태 전이 행렬(Transition Matrix)

1.1 정의

시간 동질 이산 마르코프 체인에서 상태 전이 행렬(transition matrix) $\mathbf{P}$ 의 $(i, j)$ 원소는 상태 $i$ 에서 상태 $j$ 로의 1-단계 전이 확률이다.

$P_{ij} = p_{ij} = P(X_{t+1} = j \vert X_t = i)$

$n$ 개의 상태가 있으면 $\mathbf{P} \in \mathbb{R}^{n \times n}$ 이다.

1.2 확률 행렬의 성질

상태 전이 행렬은 확률 행렬(stochastic matrix) 또는 마르코프 행렬이라 하며, 다음의 성질을 만족한다.

비음성: $P_{ij} \geq 0$ , $\forall i, j$
행 합이 1: $\sum_{j=1}^{n}P_{ij} = 1$ , $\forall i$ (각 행이 확률 분포)

이 성질들은 “어떤 상태에서 출발하여 반드시 어떤 상태로 전이“함을 의미한다.

2. 상태 분포의 시간 전개

시각 $t$ 에서의 상태 분포 벡터 $\boldsymbol{\pi}_t = [\pi_t(1), \ldots, \pi_t(n)]^T$ ( $\sum_i \pi_t(i) = 1$ )의 시간 전개는 행 벡터 표기로 다음과 같다.

$\boldsymbol{\pi}_{t+1}^T = \boldsymbol{\pi}_t^T\mathbf{P}$

또는 열 벡터 표기로:

$\boldsymbol{\pi}_{t+1} = \mathbf{P}^T\boldsymbol{\pi}_t$

$n$ -단계 후의 분포:

$\boldsymbol{\pi}_{t+n}^T = \boldsymbol{\pi}_t^T\mathbf{P}^n$

3. $n$ -단계 전이 행렬

채프만-콜모고로프 방정식에 의해:

$\mathbf{P}^{(n+m)} = \mathbf{P}^{(n)}\mathbf{P}^{(m)} = \mathbf{P}^{n+m}$

$n$ -단계 전이 행렬은 1-단계 행렬의 $n$ 제곱으로 계산된다.

4. 정상 분포(Stationary Distribution)

4.1 정의

확률 분포 $\boldsymbol{\pi}^*$ 가 마르코프 체인 $\mathbf{P}$ 의 정상 분포(stationary distribution)란 다음을 만족하는 것이다.

$\boldsymbol{\pi}^{*T}\mathbf{P} = \boldsymbol{\pi}^{*T}$

즉, 분포가 $\boldsymbol{\pi}^*$ 이면 다음 시각에도 동일한 분포가 유지된다. 이는 $\boldsymbol{\pi}^*$ 가 $\mathbf{P}^T$ 의 고유값 1에 대응하는 좌측 고유벡터임을 의미한다.

정규화 조건: $\sum_i\pi^*(i) = 1$ .

4.2 존재와 유일성

정리: 유한 상태 에르고딕 마르코프 체인(기약, 비주기, 양의 재귀)은 유일한 정상 분포를 가지며, 임의의 초기 분포로부터 시작한 상태 분포가 정상 분포에 수렴한다.

$\lim_{n \to \infty}\boldsymbol{\pi}_0^T\mathbf{P}^n = \boldsymbol{\pi}^{*T}$

초기 조건에 무관한 극한이 존재한다.

4.3 정상 분포의 계산

정상 분포는 선형 방정식계 $\boldsymbol{\pi}^{*T}\mathbf{P} = \boldsymbol{\pi}^{*T}$ 와 정규화 조건 $\sum_i\pi^*(i) = 1$ 을 결합하여 풀 수 있다.

또는 $\mathbf{P}^T$ 의 고유값 1에 대응하는 고유벡터를 정규화하여 구한다.

5. 세부 균형 조건(Detailed Balance)

마르코프 체인이 가역(reversible)이란, 다음의 세부 균형 조건을 만족하는 분포 $\boldsymbol{\pi}$ 가 존재하는 것이다.

$\pi(i)P_{ij} = \pi(j)P_{ji}, \quad \forall i, j$

가역이면 $\boldsymbol{\pi}$ 는 정상 분포이다. 역은 일반적으로 성립하지 않는다(모든 정상 분포가 가역인 것은 아니다).

세부 균형 조건은 “상태 $i \to j$ 의 확률 플럭스가 $j \to i$ 와 같다“는 조건이며, 메트로폴리스-헤이스팅스 알고리즘 설계의 기반이다.

6. 수렴 속도

에르고딕 체인의 수렴 속도는 전이 행렬의 두 번째로 큰 고유값 $\lambda_2$ 에 의해 결정된다. 구체적으로 $\lvert\lambda_2\rvert$ 가 작을수록 빠르게 수렴한다. 스펙트럼 간극(spectral gap) $1 - \lvert\lambda_2\rvert$ 가 수렴 속도를 특성화한다.

7. 로봇 공학에서의 응용

7.1 MDP의 정상 분포

마르코프 결정 과정에서 정책이 고정되면 상태 공간에서 유도되는 마르코프 체인의 정상 분포가 로봇이 장기적으로 방문하는 상태들의 분포를 나타낸다. 강화 학습의 방문 분포(occupancy measure) 분석에 사용된다.

7.2 MCMC 샘플링

마르코프 체인 몬테카를로(MCMC) 방법은 관심 대상 분포를 정상 분포로 갖는 마르코프 체인을 설계하고, 이 체인의 샘플 경로를 관심 분포의 샘플로 사용한다. 로봇 공학의 베이지안 추론에서 사후 분포 샘플링에 활용된다.

7.3 활동 인식과 HMM

숨은 마르코프 모델(Hidden Markov Model)에서 상태 전이 행렬은 활동 모드(걷기, 뛰기, 정지 등) 사이의 전이 확률을 모델링한다. 관측(센서 데이터)을 기반으로 활동 상태를 추론한다.

8. 참고 문헌

Norris, J. R. (1997). Markov Chains. Cambridge University Press.
Ross, S. M. (2014). Introduction to Probability Models (11th ed.). Academic Press.
Brémaud, P. (1999). Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Springer.
Puterman, M. L. (2014). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley.

version: 1.0