마르코프 체인은 어떻게 현재만 보고 미래를 계산하는가
마르코프 성질, 전이확률행렬, n-step 전이, 정지분포, 수렴 조건, 흡수 상태와 가역성을 중심으로 마르코프 체인을 정리합니다.
마르코프 체인은 어떤 시스템이 여러 상태 사이를 확률적으로 이동하는 과정을 다룬다. 날씨가 맑음에서 흐림으로 바뀌거나, 사용자가 홈 화면에서 상품 페이지로 이동하거나, 서버가 정상 상태에서 과부하 상태로 바뀌는 일을 하나의 상태 전이 시스템으로 보는 방식이다.
핵심은 단순하다.
다음 상태의 분포는 과거 전체가 아니라 현재 상태에 의해 결정된다.
이 말은 과거가 아무 의미 없다는 뜻이 아니다. 과거의 정보가 현재 상태 안에 충분히 요약되어 있다면, 다음을 예측할 때는 현재 상태만 보면 된다는 뜻이다.
마르코프 체인의 기본 형태
P에 모은다.
마르코프 성질
확률 과정 X_0, X_1, X_2, ...가 있을 때, 이 과정이 마르코프 체인이라는 말은 다음 조건을 만족한다는 뜻이다.
P(X_{n+1} = j | X_n = i, X_{n-1}, ..., X_0)
=
P(X_{n+1} = j | X_n = i)
미래를 예측할 때 과거 전체를 다시 펼쳐 보지 않고, 현재 상태 X_n만 사용한다. 이 성질을 마르코프 성질이라고 한다.
주의할 점이 있다. 마르코프 성질은 “다음 상태가 현재 상태와 독립”이라는 뜻이 아니다. 오히려 다음 상태는 현재 상태에 강하게 의존한다. 다만 현재 상태를 알고 나면, 그 이전의 이력은 추가 정보를 주지 않는다는 뜻이다.
전이확률행렬
상태가 A, B, C 세 개라고 하자. 한 단계 뒤 어디로 갈지의 확률은 행렬로 표현할 수 있다.
next A next B next C
A 0.6 0.4 0.0
B 0.3 0.5 0.2
C 0.0 0.6 0.4
이 글에서는 행 벡터 관례를 사용한다. 즉, 현재 분포 pi^(0)를 왼쪽에 두고 오른쪽에 전이행렬 P를 곱한다.
pi^(1) = pi^(0) P
pi^(2) = pi^(0) P^2
pi^(n) = pi^(0) P^n
행렬의 각 행은 현재 상태 하나를 의미한다. 어떤 상태에 있든 다음 단계에는 반드시 어딘가의 상태가 되어야 하므로, 각 행의 합은 1이어야 한다. 이런 행렬을 row-stochastic matrix라고 부른다.
상태 전이 예시
n-step 전이 계산
초기 상태가 반드시 A라고 하자.
pi^(0) = [1, 0, 0]
한 단계 뒤에는 전이행렬의 첫 번째 행 그대로가 된다.
pi^(1) = [1, 0, 0] P
= [0.6, 0.4, 0.0]
두 단계 뒤에는 다시 한 번 P를 곱한다.
pi^(2) = [0.6, 0.4, 0.0] P
= [0.48, 0.44, 0.08]
이 값이 중요하다. Notion 원문에는 같은 예시의 두 단계 뒤 분포가 [0.42, 0.44, 0.14]로 적혀 있었지만, 행 벡터 관례와 위 전이행렬을 그대로 사용하면 올바른 값은 [0.48, 0.44, 0.08]이다.
정지분포와 수렴분포
정지분포는 전이 이후에도 변하지 않는 분포다.
pi = pi P
sum(pi_i) = 1
pi_i >= 0
위 예시의 정지분포를 풀어보면 다음과 같다.
pi = [0.36, 0.48, 0.16]
확인해보면 pi P = pi가 된다.
정지분포의 의미
정지분포와 수렴분포는 비슷해 보이지만 구분해야 한다.
정지분포는 “이미 이 분포로 시작하면 한 단계 뒤에도 그대로”라는 대수적 조건이다. 반면 수렴분포는 “어떤 초기 상태에서 시작해도 시간이 충분히 지나면 그 분포로 가까워지는가”라는 극한 조건이다.
유한 상태 마르코프 체인에서는 다음처럼 정리할 수 있다.
| 조건 | 의미 | 결과 |
|---|---|---|
| 유한 상태 | 상태 수가 유한하다. | 적어도 하나의 정지분포가 존재한다. |
| 불가약 | 어떤 상태에서든 충분한 단계 뒤 다른 모든 상태로 갈 수 있다. | 유한 체인에서는 정지분포가 유일하다. |
| 비주기적 | 특정 주기마다만 되돌아오는 구조가 아니다. | 불가약성과 함께 있으면 분포가 정지분포로 수렴한다. |
| 가산 무한 상태 | 상태가 무한하지만 셀 수 있다. | 불가약, 비주기성만으로는 부족하고 positive recurrence 조건이 필요하다. |
즉 “불가약 + 비주기적이면 항상 하나의 분포로 수렴한다”는 말은 유한 상태 체인에서는 안전하지만, 무한 상태 공간까지 일반화하려면 positive recurrence를 함께 확인해야 한다.
상태를 분류하는 말들
마르코프 체인을 읽다 보면 여러 성질이 나온다. 처음에는 아래 정도를 구분하면 충분하다.
| 개념 | 뜻 | 왜 중요한가 |
|---|---|---|
| 불가약 | 모든 상태가 하나의 연결된 세계 안에 있다. | 장기 분포가 초기 상태에 덜 의존하게 된다. |
| 주기성 | 어떤 상태로 돌아오는 시간이 특정 주기의 배수로만 가능하다. | 주기가 있으면 분포가 흔들리며 수렴하지 않을 수 있다. |
| 흡수 상태 | 들어가면 빠져나오지 못하는 상태다. | 장기적으로 어디에 흡수되는지가 핵심 문제가 된다. |
| 재귀 상태 | 언젠가 다시 돌아올 확률이 1인 상태다. | 무한 상태 체인에서 positive/null recurrence를 구분해야 한다. |
| 가역성 | pi_i P_ij = pi_j P_ji를 만족한다. |
상세균형을 이용해 정지분포를 쉽게 검증할 수 있다. |
흡수 마르코프 체인
흡수 상태가 있는 체인은 장기분포를 볼 때 조심해야 한다. 예를 들어 종료, 장애, 결제 완료 같은 상태는 한 번 들어가면 더 이상 빠져나오지 않는 상태로 모델링할 수 있다.
P(absorb -> absorb) = 1
이런 체인에서는 “전체가 하나의 평형으로 섞인다”보다 “어느 흡수 상태에 도달할 확률이 얼마인가”, “흡수되기까지 평균 몇 단계가 걸리는가”가 더 자연스러운 질문이다.
연속시간 마르코프 체인
Notion 원문에는 DTMC와 CTMC가 함께 언급되어 있다. 둘은 상태 전이의 철학은 같지만 시간 모델이 다르다.
| 구분 | 시간 | 핵심 객체 | 정지 조건 |
|---|---|---|---|
| DTMC | 0, 1, 2처럼 단계가 나뉜다. | 전이확률행렬 P |
pi = pi P |
| CTMC | 시간이 연속적으로 흐른다. | 전이율 행렬 또는 generator Q |
pi Q = 0 |
CTMC에서는 “다음 단계로 갈 확률”보다 “얼마의 rate로 다른 상태로 점프하는가”가 중심이 된다. 예를 들어 서버 장애 모델에서 정상 상태가 평균적으로 100시간 유지되고, 복구 상태가 평균적으로 2시간 걸리는 식의 시간을 직접 다룰 수 있다.
어디에 쓰이는가
마르코프 체인은 단순한 수학 장난이 아니라, “현재 상태를 잘 정의하면 다음 흐름을 확률적으로 계산할 수 있다”는 틀이다.
응용을 읽는 방식
PageRank는 특히 좋은 예다. 웹 페이지를 그래프의 노드로 두고, 사용자가 링크를 따라 무작위로 이동한다고 보면 하나의 마르코프 체인이 된다. 장기적으로 어떤 페이지에 오래 머무는지가 그 페이지의 중요도와 연결된다. 실제 PageRank에는 dangling node와 spider trap 문제를 피하기 위한 teleportation이 들어가는데, 이 역시 체인이 잘 섞이도록 만드는 장치로 이해할 수 있다.
글을 읽을 때의 기준
마르코프 체인 문서를 볼 때는 아래 질문을 순서대로 던지면 덜 헷갈린다.
1. 상태는 무엇인가?
2. 시간은 discrete인가, continuous인가?
3. 전이확률행렬 P 또는 generator Q는 어떻게 정의되는가?
4. 행 기준인가, 열 기준인가?
5. 정지분포를 묻는가, 수렴분포를 묻는가?
6. 불가약성, 비주기성, 흡수 상태는 어떻게 되는가?
특히 4번이 중요하다. 어떤 책은 행 벡터를 쓰고 pi P를 계산한다. 어떤 책은 열 벡터를 쓰고 P pi를 계산한다. 둘 중 어느 쪽이든 수학적으로는 가능하지만, 한 글 안에서는 관례를 섞으면 계산이 틀어진다.
정리
마르코프 체인은 복잡한 이력을 현재 상태 하나로 접어 넣는 모델이다. 상태 정의가 잘 되어 있으면, 다음 상태는 전이확률행렬로 계산할 수 있고, 여러 단계를 지나면 P^n이 시스템의 장기 행동을 보여준다.
다만 장기적으로 안정된 분포가 생기는지는 조건을 봐야 한다. 유한 상태에서 불가약이고 비주기적인 체인은 유일한 정지분포로 수렴한다. 흡수 상태가 있거나 주기성이 있거나 무한 상태 공간이라면 이야기가 달라질 수 있다.
그래서 마르코프 체인의 핵심은 “현재만 본다”가 아니라, “미래를 계산하기에 충분한 현재 상태를 어떻게 정의할 것인가”에 있다.
