현재의 상태가 미래를 결정한다는 가정. 이 단순해 보이는 명제 위에 마르코프 체인(Markov chain)이라는 확률 모델이 서 있다. 1906년 안드레이 마르코프가 도입한 이 개념은 이후 한 세기에 걸쳐 통신 이론, 자연어 처리, 금융 모델링, 검색 엔진 알고리즘까지 광범위한 영역에서 핵심 도구로 자리 잡았다. 마르코프 체인의 진짜 힘은 복잡한 시스템을 분석 가능한 상태 전이의 연쇄로 바꾸는 데 있다.
마르코프 성질의 정의
마르코프 성질이란 어떤 확률 과정의 미래 상태가 현재 상태에만 의존하고 과거에는 의존하지 않는다는 속성을 말한다. 수식으로는 P(X_{t+1} | X_t, X_{t-1}, …, X_0) = P(X_{t+1} | X_t) 로 표현된다. 시스템이 어떻게 현재 상태에 도달했는지는 미래의 전이 확률에 영향을 주지 않는다. 오직 현재가 어디인지만 중요하다. 이 속성은 기억 없음(memorylessness)이라고도 불린다.
현실의 많은 시스템은 이 속성을 완전히 만족하지 않지만, 근사적으로 마르코프 성질을 가진다고 볼 수 있는 경우가 매우 많다. 날씨, 주가, 단어의 순서, 게임의 진행, 인구 이동, 모두 마르코프 모델로 모델링하면 분석이 단순해지면서도 실용적 예측력을 가진다. 마르코프 가정이 깔끔하게 들어맞지 않는 경우에는 상태 정의를 확장해서 더 많은 정보를 현재 상태에 포함시키는 방식으로 보완할 수 있다. 마르코프 과정의 수학적 배경과 역사에 대해서는 브리태니커 백과사전의 마르코프 체인 항목에서 상세히 정리되어 있다.
전이 행렬과 상태 분포
이산 상태 공간을 가진 마르코프 체인은 전이 행렬(transition matrix)로 완전히 기술된다. n개의 상태가 있다면 n by n 행렬의 각 원소 P_{ij}가 상태 i에서 상태 j로 전이할 확률을 나타낸다. 각 행의 합은 1이고, 이 행렬을 알면 시스템의 미래 행동을 모두 계산할 수 있다.
흥미로운 점은 초기 상태 분포 벡터에 전이 행렬을 반복해서 곱하면 시스템이 어떤 분포로 수렴한다는 것이다. 이 수렴 분포를 정상 분포(stationary distribution) 또는 평형 분포라고 부른다. 마르코프 체인이 비주기적이고 기약(irreducible)이라면 정상 분포는 유일하게 존재하고, 초기 상태와 무관하게 충분한 시간이 지나면 시스템은 그 분포에 도달한다. 이 결과는 마르코프 체인의 가장 강력한 정리 가운데 하나로, 무작위 시스템의 장기 행동을 예측 가능하게 만들어준다.
응용 사례: 검색 엔진과 페이지랭크
구글의 페이지랭크 알고리즘은 마르코프 체인의 가장 유명한 응용 사례다. 웹의 모든 페이지를 노드로 보고, 페이지 사이의 링크를 전이로 정의하면 거대한 마르코프 체인이 만들어진다. 무작위로 링크를 따라가는 사용자(랜덤 워커)가 충분히 오랜 시간 동안 돌아다니면 각 페이지에 도달할 확률이 정상 분포로 수렴하는데, 이 확률이 바로 페이지랭크다. 단순한 마르코프 모델이 인터넷 전체의 정보 구조를 정량화한 셈이다.
이 접근의 깊이는 단순함에서 나온다. 페이지의 중요도를 평가하는 명시적 기준을 정하지 않고, 그저 링크 구조라는 마르코프 체인의 정상 분포를 계산함으로써 자연스럽게 중요한 페이지가 높은 점수를 받게 만들었다. 많은 페이지가 링크하는 페이지는 정상 분포에서 높은 확률을 가지고, 다시 그 페이지가 링크하는 페이지도 영향을 받는다. 마르코프 체인의 수렴 성질이 재귀적 정의를 자연스럽게 해결한다.
은닉 마르코프 모델
실제 분석에서는 시스템의 상태를 직접 관측할 수 없는 경우가 많다. 우리가 보는 것은 상태에서 생성된 어떤 출력이고, 상태 자체는 숨어 있다. 이런 상황을 다루는 것이 은닉 마르코프 모델(Hidden Markov Model, HMM)이다. 음성 인식, 생물정보학, 자연어 처리에서 핵심 도구로 쓰인다.
HMM에서는 상태 전이 행렬과 함께 각 상태에서 어떤 출력을 낼 확률을 정의하는 방출 행렬(emission matrix)이 추가된다. 관측된 출력 시퀀스가 주어졌을 때 가장 가능성 높은 숨은 상태 시퀀스를 찾는 문제(비터비 알고리즘), 모델 파라미터를 데이터로부터 추정하는 문제(바움-웰치 알고리즘) 등이 표준 기법으로 정립되어 있다. 시계열 데이터 분석에서 HMM은 엔트로피 신뢰성 프레임워크에 대한 이전 글에서 다룬 무작위성 측정의 연장선에서 자주 활용되며, 변동성 체제 변화를 모델링하는 데도 적용된다.
마르코프 체인 몬테카를로
마르코프 체인의 가장 우아한 응용 가운데 하나가 마르코프 체인 몬테카를로(MCMC) 기법이다. 직접 샘플링하기 어려운 복잡한 확률 분포에서 표본을 뽑아야 할 때, 그 분포를 정상 분포로 가지는 마르코프 체인을 설계해서 충분히 오래 돌리면 원하는 분포의 표본을 얻을 수 있다. 메트로폴리스-헤이스팅스 알고리즘이나 깁스 샘플링이 대표적인 구현 방식이다.
MCMC가 베이즈 통계의 부흥을 이끈 핵심 도구다. 사전 분포와 가능도의 곱이 사후 분포에 비례한다는 베이즈 정리의 결과를 실용적으로 활용하려면, 정규화 상수를 계산하지 않고도 사후 분포에서 샘플링할 수 있어야 하는데, MCMC가 정확히 이 문제를 해결한다. 확증편향과 손실회피에 대한 이전 분석에서 살펴봤듯이, 인지편향에 빠진 신념 업데이트는 베이즈적이지 않다. MCMC가 시연하는 사후 분포의 정확한 갱신 과정은, 인간의 편향적 업데이트와 좋은 대조를 이룬다.
흡수 상태와 도박사의 파멸
모든 마르코프 체인이 정상 분포로 수렴하는 것은 아니다. 한 번 들어가면 빠져나올 수 없는 상태(흡수 상태, absorbing state)가 있는 체인에서는 시스템이 결국 흡수 상태 가운데 하나에 도달해 머문다. 도박사의 파멸 문제가 이 구조의 고전적 사례다.
유한한 자금을 가진 도박사가 1대1 배당의 베팅을 반복할 때, 자금이 0이 되거나 어떤 목표 금액에 도달할 때까지 게임을 계속한다고 하자. 이 시스템은 두 개의 흡수 상태(파산과 목표 달성)를 가진 마르코프 체인이다. 베팅의 기대값이 정확히 0인 공정한 게임이라도, 자금이 한정되어 있다면 파산 확률은 양수이고, 카지노처럼 살짝 불리한 게임에서는 자금이 충분하더라도 파산이 거의 확실해진다. 마르코프 체인의 수학이 이 결과를 명확하게 보여준다.
도박사의 파멸 정리는 자금 관리의 본질을 수학적으로 설명한다. 기대값이 음수인 게임에서 무한히 반복하면 자금은 0으로 수렴한다는 것은 직관적으로 이해할 수 있지만, 기대값이 0인 공정한 게임에서도 유한 자금이라면 결국 한쪽 흡수 상태에 도달한다는 사실은 깊이 생각해볼 가치가 있다. 도박과 확률에 대한 학술적 자료는 미국수학회의 출판물에서 다양하게 다뤄지고 있다.
마르코프 가정의 한계
마르코프 모델이 강력하지만 모든 상황에 들어맞지는 않는다. 가장 큰 한계는 기억 없음 가정이다. 시스템의 미래가 현재뿐 아니라 과거에도 의존한다면, 단순 마르코프 모델로는 정확한 표현이 어렵다. 이 경우 흔히 쓰는 방법은 상태 정의를 확장하는 것이다. 현재 상태에 과거 k개의 시점 정보를 포함시키면 k차 마르코프 체인이 되고, k를 충분히 크게 잡으면 어떤 시스템도 마르코프 모델로 근사할 수 있다.
그러나 상태 공간이 지수적으로 커지는 비용을 치러야 한다. 상태가 10가지인 시스템의 2차 마르코프 체인은 100개 상태를 가진 1차 체인이 되고, 3차는 1000개, 4차는 1만 개가 된다. 이 트레이드오프를 어떻게 다루느냐가 실용적 마르코프 모델링의 핵심이다. 충분히 단순한 모델이 데이터에 잘 맞으면 그것이 가장 좋고, 복잡한 모델은 과적합의 위험을 키운다. 모델의 단순성과 표현력 사이의 균형은 모든 통계 모델링이 공유하는 근본 문제다.
실용적 관점에서의 정리
마르코프 체인이 실무에서 빛을 발하는 영역은 명확하다. 시스템의 상태를 잘 정의할 수 있고, 상태 간 전이가 충분히 안정적인 환경에서 마르코프 모델은 짧은 시간 안에 강력한 예측력을 제공한다. 사용자 행동 분석, 마케팅 퍼널, 신용 등급 변화, 질병 진행, 모두 마르코프 체인으로 모델링되어 활용된다. 정확하지 않더라도 의사결정에 충분한 수준의 근사를 제공하는 것이 마르코프 모델의 가치다.
결국 마르코프 체인은 복잡함을 단순함으로 환원하는 도구다. 모든 정보를 가지고 미래를 예측하려는 욕심을 내려놓고, 현재 상태만 가지고 충분히 좋은 예측을 하겠다고 받아들이는 순간 분석은 단순해지고 실용성이 올라간다. 이 절제가 마르코프 모델의 본질이고, 한 세기가 지나도 여전히 광범위하게 쓰이는 이유다.