1. 요약 (Executive Summary)
마코프 체인(Markov Chain)은 ‘메모리리스(Memoryless)’ 특성을 가진 이산 시간 확률 과정으로, 미래 상태가 과거의 이력과는 무관하게 오직 현재 상태에 의해서만 결정되는 시스템을 모델링한다. 이 시스템은 전이 확률 행렬(Transition Probability Matrix)을 통해 상태 간의 이동을 정의하며, 장기적으로는 시스템이 평형 상태인 정상 분포(Stationary Distribution)에 도달하는지 여부를 분석하는 데 핵심적인 목적이 있다. 마코프 체인은 물리학, 생물학, 대기 행렬 이론(Queuing Theory)과 같은 전통적 과학 분야부터 구글의 페이지랭크(PageRank) 알고리즘, 생성형 AI 및 강화 학습(Reinforcement Learning)에 이르기까지 현대 기술 전반에 걸쳐 필수적인 분석 도구로 활용되고 있다.
2. 마코프 체인의 기본 정의 및 원리
2.1 마코프 성질 (Markov Property)
마코프 체인의 핵심은 마코프 성질에 있다. 이는 확률 과정 ${X_n, n \ge 0}$에서 시간 $n+1$의 상태가 과거의 모든 경로$(X_0, X_1, \dots, X_{n-1})$가 아닌, 오직 현재의 상태 $X_n$에만 의존한다는 원칙이다. 이를 수학적으로 표현하면 다음과 같다:
$$P(X_{n+1} = j \mid X_0, X_1, \dots, X_n = i) = P(X_{n+1} = j \mid X_n = i) = p_{ij}$$
이러한 특성 때문에 마코프 체인은 ‘기억력이 없는(Memoryless)’ 과정으로 불린다.
2.2 전이 확률 및 행렬 (Transition Matrix)
- 전이 확률($p_{ij}$): 상태 $i$에서 상태 $j$로 이동할 확률이다.
- 시간 균일성(Time-Homogeneity): 전이 확률이 시간 $n$에 따라 변하지 않는 경우를 말한다.
- 전이 확률 행렬($P$): 모든 가능한 상태 간의 전이 확률을 정사각 행렬 형태로 나타낸 것이다. 각 행의 합은 반드시 1이 되어야 하며, 이러한 행렬을 **확률 행렬(Stochastic Matrix)**이라고 한다.
2.3 채프먼-콜모고로프 방정식 (Chapman-Kolmogorov Equations)
$m+n$ 단계 후의 전이 확률은 중간 단계 $k$를 거치는 확률들의 합으로 계산될 수 있다. 이는 행렬의 거듭제곱($P^{m+n} = P^m P^n$)으로 나타낼 수 있으며, 다단계 전이 확률 분석의 기초가 된다.
3. 상태의 분류 및 체인의 성질
마코프 체인의 장기적 거동을 이해하기 위해서는 각 상태(State)의 특성을 분류하는 것이 필수적이다.
3.1 상태 분류 체계
| 분류 명칭 | 정의 및 특징 |
|---|---|
| 재귀적(Recurrent) | 상태 $i$에서 출발하여 다시 $i$로 돌아올 확률이 1인 상태 |
| 일시적(Transient) | 상태 $i$로 다시 돌아오지 못할 확률이 0보다 큰 상태. 장기적으로 방문 횟수가 유한함 |
| 양의 재귀적(Positive Recurrent) | 재귀적 상태이면서, 다시 돌아오기까지 걸리는 평균 시간(평균 재귀 시간)이 유한한 상태 |
| 영의 재귀적(Null Recurrent) | 재귀적이지만 평균 재귀 시간이 무한한 상태 |
| 흡수 상태(Absorbing State) | 한 번 진입하면 다시는 나갈 수 없는 상태 ($p_{ii} = 1$) |
3.2 체인의 구조적 성질
- 기약성(Irreducibility): 체인 내의 모든 상태가 서로 소통(Communicate) 가능한 경우, 즉 어떤 상태에서든 다른 어떤 상태로든 갈 수 있는 경로가 존재할 때 해당 체인은 기약적이라고 한다.
- 주기성(Periodicity): 상태 $i$로 돌아오는 단계 수가 특정 정수 $k > 1$의 배수일 때 이를 주기적이라고 한다. 최대공약수가 1인 경우 **비주기적(Aperiodic)**이라고 한다.
- 에르고딕성(Ergodicity): 상태가 기약적이고 양의 재귀적이며 비주기적일 때, 해당 체인을 에르고딕 체인이라고 부른다. 이는 장기적으로 고유한 정상 분포로 수렴함을 보장한다.
4. 정상 분포 및 극한 이론
마코프 체인 분석의 주요 목적 중 하나는 시간이 충분히 흐른 뒤 시스템이 도달하는 ‘평형 상태’를 찾는 것이다.
4.1 정상 분포 (Stationary Distribution)
확률 벡터 $\pi$가 $\pi^T P = \pi^T$를 만족할 때, 이를 정상 분포라고 한다. 이는 시스템이 일단 이 분포에 도달하면 다음 단계에서도 분포가 변하지 않음을 의미한다.
- 유한 상태의 기약적 마코프 체인은 항상 유일한 정상 분포를 가진다.
- 수렴성: 비주기적이고 기약적인 양의 재귀적 체인에서, 초기 분포와 상관없이 $n$단계 전이 확률 $p_{ij}^n$은 $n \to \infty$일 때 정상 확률 $\pi_j$로 수렴한다.
4.2 수렴 분석 도구
- 결합(Coupling): 두 개의 마코프 체인이 결국 같은 상태에서 만나도록 구성하여 수렴성을 증명하는 기술적 방법이다.
- 전변동 거리(Total Variation Distance): 두 확률 분포 사이의 거리를 측정하여 정상 분포로의 수렴 속도를 분석하는 데 사용된다.
5. 고급 개념 및 확장 모델
5.1 정지 시간(Stopping Time)과 강 마코프 성질
- 정지 시간: 특정 시점 $n$까지의 정보만으로 발생 여부를 결정할 수 있는 무작위 시간(예: 특정 상태에 처음 도달하는 시간)이다.
- 강 마코프 성질(Strong Markov Property): 마코프 체인이 단순한 고정된 시간 $n$뿐만 아니라, 정지 시간 $\tau$ 이후에도 과거와 독립적으로 새로 시작하는 것처럼 행동하는 성질이다.
5.2 재생 과정 (Renewal Processes)
배터리 교체 모델과 같이 사건이 발생할 때마다 시스템이 초기화되는 과정을 마코프 체인으로 모델링할 수 있다. 이는 연령 과정(Age process)이나 잔여 수명 과정(Residual lifetime process)으로 세분화된다.
6. 마코프 체인의 주요 응용 분야
컴퓨터 과학 및 AI
- 구글 페이지랭크: 웹페이지를 상태로, 하이퍼링크를 전이 확률로 모델링하여 웹사이트의 중요도를 평가한다.
- 생성형 AI 및 자연어 처리(NLP): N-Gram 모델을 통해 이전 단어들을 바탕으로 다음 단어의 등장 확률을 예측한다.
- 강화 학습: 마코프 결정 과정(MDP)을 기반으로 보상을 최대화하는 최적의 정책(Policy)을 학습한다.
운영 연구 및 경제학
- 대기 행렬 이론 (M/M/1 큐): 서버의 대기 줄 길이를 마코프 체인으로 분석하여 시스템 효율성을 최적화한다.
- 재고 관리 모델: (s, S) 정책과 같이 재고 수준의 변동을 확률적으로 모델링한다.
물리학 및 통계 분석
- MCMC (Markov Chain Monte Carlo): 복잡한 확률 분포로부터 샘플을 추출하기 위해 마코프 체인을 설계하는 알고리즘(메트로폴리스-헤이스팅스, 깁스 샘플링 등)이다.
- 통계 역학: 입자의 확산이나 물리적 시스템의 평형 상태를 시뮬레이션한다.
도박 및 게임
- 도박사의 파산 (Gambler’s Ruin): 자산의 증감을 랜덤 워크로 모델링하여 파산 확률을 계산한다.
7. 학습 및 구현 리소스
마코프 체인을 심도 있게 학습하거나 구현하기 위한 주요 도구와 경로는 다음과 같다.
- 추천 교재: Blitzstein & Hwang의 확률론 입문서, Sheldon Ross의 마코프 체인 관련 서적 등이 기초 다지기에 권장된다.
- 선결 지식: 기초 확률론, 선형 대수학(고유값, 고유벡터 분석), 기초 미적분학에 대한 이해가 필요하다.
- 구현 도구: Python(NumPy, 기초 시뮬레이션) 및 R을 활용하여 전이 행렬 계산 및 상태 예측 기능을 구현할 수 있다. 특히 대규모 데이터를 다루는 경우 행렬 연산의 효율성이 중요하다.
- 전문 교육: Coursera(이산 시간 마코프 체인 및 몬테카를로 방법), edX(확률론, 선형 대수) 등에서 제공하는 대학 수준의 온라인 코스가 유효한 학습 자원으로 활용된다.