12장. 마르코프 체인과 몬테카를로

적분이나 기댓값을 식으로 풀 수 없을 때, 무작위로 많이 뽑아 평균을 내면 됩니다. 이것이 몬테카를로 방법(Monte Carlo method)이고, 6장의 큰 수의 법칙이 그 근거입니다. 그런데 10장의 사후분포처럼 원하는 분포에서 직접 뽑기조차 어려울 때가 있습니다. 그때는 “현재 상태에만 의존해 다음 상태로 가는” 마르코프 체인을 잘 설계해, 오래 돌리면 원하는 분포에 머물게 합니다(MCMC). 이 장은 확률 과목의 마무리로, 선형대수의 고유벡터가 확률에서 어떻게 쓰이는지도 보여 줍니다.

12.1 몬테카를로 적분

정리 12.1. $X_1, \dots, X_n$이 분포 $p$에서 뽑은 i.i.d. 표본이면

이고 오차의 표준편차는 $\sigma_g/\sqrt n$입니다(6장).

오차가 차원과 무관하게 $1/\sqrt n$으로 줄어든다는 점이 핵심입니다. 격자로 적분하면 100차원에서 점이 천문학적으로 필요하지만, 몬테카를로는 그렇지 않습니다.

예제 12.2 (π 어림). 정사각형 $[0, 1]^2$에 점을 고르게 뿌리면 사분원 $x^2 + y^2 \le 1$ 안에 들어갈 확률은 $\pi/4$입니다. 안에 든 비율에 4를 곱하면 $\pi$의 어림값입니다.

중요도 표집. $p$에서 뽑기 어려우면 쉬운 $q$에서 뽑고 무게를 줍니다: $E_p[g] = E_q\!\left[g(X)\frac{p(X)}{q(X)}\right]$. 이를 중요도 표집(importance sampling)이라 합니다. 무게 $p/q$를 중요도 가중치(importance weight)라 하고, 강화학습의 오프-폴리시 학습(PPO의 비율 $\pi_\theta/\pi_{\text{old}}$)이 이 식입니다.

12.2 마르코프 체인

정의 12.3. 상태 $X_0, X_1, \dots$이 $P(X_{t+1} \mid X_t, \dots, X_0) = P(X_{t+1} \mid X_t)$를 만족하면 마르코프 체인(Markov chain)이라 합니다. 다음 상태는 현재만 보고 정해지고, 과거는 잊습니다.

상태가 유한하면 전이행렬(transition matrix) $P_{ij} = P(X_{t+1} = j \mid X_t = i)$로 씁니다. 각 행의 합은 1입니다. 현재 분포가 행벡터 $\boldsymbol\pi_t$이면 다음 분포는 $\boldsymbol\pi_{t+1} = \boldsymbol\pi_tP$이고, $t$단계 뒤에는 $\boldsymbol\pi_0P^t$입니다.

예제 12.4 (날씨). 맑음→맑음 0.9, 맑음→비 0.1, 비→맑음 0.5, 비→비 0.5:

오늘 맑으면 모레 맑을 확률은 $(P^2)_{11} = 0.9\cdot0.9 + 0.1\cdot0.5 = 0.86$입니다.

12.3 정상분포

정의 12.5. $\boldsymbol\pi P = \boldsymbol\pi$를 만족하는 확률분포 $\boldsymbol\pi$를 정상분포(stationary distribution)라 합니다. $P^\top$의 고윳값 1에 대한 고유벡터입니다.

정리 12.6 (수렴, 개요). 유한 상태 체인이 어느 상태에서든 다른 모든 상태로 갈 수 있고(기약), 주기적으로 맴돌지 않으면(비주기), 정상분포가 하나뿐이고 어디서 시작하든 $\boldsymbol\pi_0P^t \to \boldsymbol\pi$입니다.

예제 12.7. 날씨 체인에서 $\boldsymbol\pi = (a, 1 - a)$로 두고 $0.9a + 0.5(1 - a) = a$를 풀면 $a = 5/6$. 오랜 기간으로 보면 맑은 날이 $5/6$입니다. 수렴 속도는 둘째 고윳값 $0.4$의 크기로 정해집니다($0.4^t$로 줄어듦).

구글의 페이지랭크가 바로 웹 위의 무작위 이동 체인의 정상분포입니다.

12.4 MCMC: 메트로폴리스–헤이스팅스

목표 분포 $\pi(x)$를 상수배까지만 안다고 합시다(10장의 사후분포처럼 증거 $p(D)$를 모를 때).

알고리즘 12.8 (메트로폴리스).

1. 현재 $x$에서 대칭인 제안 분포로 후보 $x'$를 뽑습니다(예: $x' = x + \text{작은 정규 잡음}$).
2. 수락 확률 $A = \min\!\left(1, \dfrac{\pi(x')}{\pi(x)}\right)$로 $x'$로 옮기고, 아니면 $x$에 머뭅니다.
3. 반복합니다.

비율만 쓰므로 정규화 상수가 약분됩니다. 더 높은 곳은 항상 받아들이고, 낮은 곳도 가끔 받아들여 분포 전체를 돌아다닙니다.

정리 12.9 (상세 균형). $\pi(x)T(x \to x') = \pi(x')T(x' \to x)$를 만족하면 $\pi$는 정상분포입니다. 메트로폴리스의 수락 규칙은 이 조건을 맞추도록 만든 것입니다.

예제 12.10. $\pi(x') / \pi(x) = 0.3$이면 30% 확률로 이동하고, $2$이면 항상 이동합니다.

12.5 이 장의 요약

• 몬테카를로: 표본 평균으로 기댓값을 어림, 오차 $\sigma/\sqrt n$은 차원과 무관.
• 중요도 표집: $E_p[g] = E_q[g\,p/q]$.
• 마르코프 체인: 전이행렬, $\boldsymbol\pi_{t+1} = \boldsymbol\pi_tP$, 정상분포 $\boldsymbol\pi P = \boldsymbol\pi$.
• MCMC: 정상분포가 목표 분포가 되도록 설계한 체인. 메트로폴리스는 비율만 씁니다.

쓰이는 곳. 강화학습의 마르코프 결정 과정(Markov decision process, MDP: 이 장의 체인에 행동과 보상을 더한 것)과 몬테카를로 정책 평가, 확산 모델(데이터에 잡음을 더하는 마르코프 체인과 그 역과정), 언어 모델의 샘플링(다음 토큰 분포에서 뽑기), 베이즈 통계의 MCMC(Stan, PyMC), 통계물리의 이징 모형 시뮬레이션, 입자물리의 몬테카를로 사건 생성기가 이 장의 도구입니다.

문제

0.7

0.4
0.6

100

0.25