선형대수 · 마르코프 연쇄

마르코프 연쇄

마르코프 사슬은 상태 사이를 무작위로 이동하며, 다음 상태의 확률은 현재 상태에만 의존한다. 전이 행렬을 P라 하면 내일의 분포는 오늘의 분포에 오른쪽에서 P를 곱한 것이다. 이 과정을 반복하면 흔히 πP = π인 정상 분포 π, 즉 고유값 1의 왼쪽 고유벡터에 가까워진다.

이 그림에서 보는 마르코프 연쇄

마르코프 사슬에서 다음 상태의 확률은 현재 상태에만 의존한다. 여기서는 맑음, 흐림, 비가 상태다. 전이 행렬 PP의 ii번째 행은 오늘 상태가 ii일 때 내일의 확률을 나열하므로 각 행은 확률벡터다. 오늘의 분포가 행벡터 pp이면 내일은 pPpP이고 nn일 뒤에는 pn=p0Pnp_n = p_0 P^n이다. 상태가 세 개이면 모든 분포는 삼각형 안의 점이다. 각 꼭짓점에서는 한 상태의 확률이 1이고 세 확률은 꼭짓점에 주는 가중치다. 짙은 점들은 PP의 행, 파란 점은 시작, 빨간 경로는 p0,p1,p2,…p_0, p_1, p_2, \dots을 잇는다.

한 단계에서 일어나는 일

한 단계가 지나면 각 꼭짓점은 그에 대응하는 행으로 간다. 오늘 반드시 맑다면 내일 분포는 첫째 행이다. 다른 모든 분포 pp은 꼭짓점의 가중평균이므로 pPpP은 같은 가중치로 계산한 행들의 평균이다. 삼각형 전체는 각 행이 만드는 작은 삼각형 안으로 들어가고 두 단계 뒤에는 P2P^2의 행들이 만드는 삼각형에 들어간다. PP의 어떤 거듭제곱의 성분이 모두 양수이면 이 중첩된 삼각형은 한 점, 정상 분포 π\pi로 줄어든다.

π가 고유벡터인 이유와 pₙ의 수렴 속도

고정점은 πP=π\pi P = \pi을 만족하므로 π\pi은 고유값 1의 왼쪽 고유벡터이다(열로 쓰면 PTπT=πTP^{\mathsf T}\pi^{\mathsf T} = \pi^{\mathsf T}). 차이 p0−πp_0 - \pi의 성분 합은 0이다. 이 부분공간에서 PP의 고유값은 나머지 두 값 λ2,λ3\lambda_2, \lambda_3이다. 각 고유방향의 벡터에는 단계마다 해당 고유값이 곱해진다. 두 절댓값이 모두 1보다 작으면 pnp_n은 π\pi로 수렴하며 더 큰 절댓값 ∣λ2∣|\lambda_2|이 수렴 속도를 결정한다. 날씨 사슬에서는 ∣λ2∣≈0.462|\lambda_2| \approx 0.462이다. 시작점에 λ2\lambda_2 방향의 성분이 있으면 큰 nn에서 매 단계 거리가 절반보다 조금 적게 남는다. 고유값이 복소수이면 경로가 줄어들면서 회전한다.

분포가 수렴하지 않을 때

순환에서는 맑음, 흐림, 비가 반복된다. 다른 두 고유값의 절댓값이 1이어서 π\pi에서 시작하지 않으면 pnp_n은 계속 돈다. 두 흡수 상태에서는 맑음과 비가 각각 계속되고, 고유값 1이 두 번 나타나며 맑음과 비의 어떤 혼합 분포도 고정된다. 따라서 pnp_n는 수렴하지만 극한은 시작점에 달려 있다. 유한 사슬에서 어느 시작점에서나 pnp_n이 같은 π\pi로 수렴할 필요충분조건은 닫힌 소통류가 정확히 하나이고 그 소통류가 비주기적인 것이다. 그 안에서는 모든 상태가 서로 도달 가능하고 밖으로 나갈 수 없다. 어떤 거듭제곱 PmP^m의 모든 성분이 양수이면 이 조건이 보장된다.

눈여겨볼 점

  • 시작 날씨와 무관하게 정상 분포는 먼 미래 어느 날의 날씨 확률을 준다. 실제 날씨는 날마다 계속 변한다.
  • 상태가 셋보다 많으면 분포들은 삼각형의 고차원 확장인 단체를 채운다. 같은 논리가 적용된다.

조작 방법

  • 짙은 점을 끌어 전이 행렬의 한 행을 바꾸거나 파란 점을 끌어 시작 분포를 바꾼다. 방향키로 초점이 있는 점을 0.01씩 움직일 수 있다.

관련 개념