마르코프 연쇄

Markov chain; 마르코프 연쇄
다음 상태의 확률이 오직 현재 상태에만 달려 있는 확률 과정

마르코프 연쇄(Markov chain)는 상태가 확률적으로 바뀌어 가는 과정 가운데, 다음 상태로 갈 확률이 지금 어떤 상태인지에만 달려 있고 그 상태에 어떻게 왔는지(과거 이력)와는 무관한 과정이다. 이 "기억 없음" 성질을 마르코프 성질이라 한다. 러시아 수학자 안드레이 마르코프(1856~1922)가 1906년 처음 연구해 그의 이름이 붙었다. '마르코프 체인'이라고도 한다.

상태와 전이 확률만으로 정의되는 단순한 모형이지만, 오래 돌렸을 때 각 상태에 머무는 비율(정상 분포)을 계산할 수 있다는 점 때문에 쓰임이 넓다. 구글의 페이지랭크 같은 순위 계산, 베이즈 통계의 표본 추출 기법인 마르코프 연쇄 몬테카를로(MCMC), n-gram 언어 모델, 대기행렬 이론, 그리고 은닉 마르코프 모델, 마르코프 결정 프로세스, 확산 모델처럼 인공지능에서 쓰는 여러 모형의 뼈대가 된다.

정의

상태 공간 $S$ (유한하거나 셀 수 있는 집합) 위의 확률 변수열 $X_{0}, X_{1}, X_{2}, \dots$ 가 모든 $n$ 과 상태 $i_{0}, \dots, i_{n - 1}, i, j$ 에 대해

$P (X_{n + 1} = j ∣ X_{n} = i, X_{n - 1} = i_{n - 1}, \dots, X_{0} = i_{0}) = P (X_{n + 1} = j ∣ X_{n} = i)$

를 만족하면 이산 시간 마르코프 연쇄다. 이 식이 마르코프 성질이다. 전이 확률 $P (X_{n + 1} = j ∣ X_{n} = i)$ 가 시점 $n$ 과 무관하면 시간 동질(time-homogeneous) 연쇄라 하고, 보통 마르코프 연쇄라 하면 이것을 가리킨다.

마르코프 성질은 과거가 쓸모없다는 뜻이 아니라, 미래를 예측하는 데 필요한 과거 정보가 모두 현재 상태에 담겨 있다는 뜻이다. 그래서 상태를 어떻게 정의하느냐가 중요하다.
직전 $k$ 개 상태에 의존하는 $k$ 차 마르코프 연쇄도 있다. 이는 "직전 $k$ 개 상태의 묶음"을 새 상태로 보면 1차 연쇄로 바꿀 수 있다. 대신 상태 수가 $| S |^{k}$ 로 늘어난다.
동전 던지기처럼 서로 독립인 시행의 열도 형식상 마르코프 연쇄지만, 이론이 의미를 갖는 것은 다음 상태가 현재 상태에 실제로 의존할 때다.

전이 행렬

상태가 유한 개( $1, \dots, N$ )일 때 전이 확률 $p_{i j} = P (X_{n + 1} = j ∣ X_{n} = i)$ 를 모아 $N \times N$ 크기의 행렬로 나타내고 $P$ 라 쓴다. 각 행은 한 상태에서 나가는 확률 분포이므로 성분이 모두 0 이상이고 행의 합이 1이다. 이런 행렬을 확률 행렬(stochastic matrix)이라 한다.

예를 들어 날씨를 맑음, 흐림, 비 세 상태로 단순화한 모형은 다음과 같다(수치는 설명용 가정).

오늘 \ 내일	맑음	흐림	비
맑음	0.7	0.2	0.1
흐림	0.3	0.4	0.3
비	0.2	0.3	0.5

여러 단계 전이

$n$ 단계 전이 확률은 행렬 거듭제곱 $P^{n}$ 의 성분이다. 이는 $p_{i j}^{(m + n)} = \sum_{k} p_{i k}^{(m)} p_{k j}^{(n)}$ , 즉 $P^{m + n} = P^{m} P^{n}$ 이라는 채프먼-콜모고로프 방정식에서 나온다.
시점 $n$ 의 상태 분포를 행벡터 $x^{(n)}$ 로 쓰면 $x^{(n + 1)} = x^{(n)} P$ , 따라서 $x^{(n)} = x^{(0)} P^{n}$ 이다. 위 예에서 오늘 맑으면( $x^{(0)} = (1, 0, 0)$ ) 이틀 뒤 분포는 $(0.57, 0.25, 0.18)$ , 사흘 뒤는 $(0.51, 0.268, 0.222)$ 이다.
연쇄는 상태를 꼭짓점, 0이 아닌 전이 확률을 가중치 있는 화살표로 그린 방향 그래프(상태 전이도)로도 나타낸다. 아래 상태 분류는 대부분 이 그래프의 연결 구조로 판정한다.

상태 분류

상태 $i$ 에서 $j$ 로 가는 확률이 양수인 경로가 있으면 " $j$ 는 $i$ 에서 도달 가능"하다고 하고, 서로 도달 가능하면 "통한다"(communicate)고 한다. 통하는 관계는 동치 관계라서 상태 공간을 통신 부류(communicating class)로 나눈다. 모든 상태가 하나의 부류에 속하면 기약(irreducible) 연쇄다.

분류	정의	비고
재귀(recurrent)	그 상태에서 출발하면 확률 1로 언젠가 다시 돌아온다	돌아오기까지 기대 시간이 유한하면 양재귀, 무한하면 영재귀. 유한 연쇄의 재귀 상태는 모두 양재귀다
일시(transient)	다시 돌아오지 못할 확률이 양수다	결국 유한 번만 방문한다
주기(period)	돌아올 수 있는 단계 수들의 최대공약수 $d$	$d = 1$ 이면 비주기(aperiodic), $d > 1$ 이면 주기적. 예: 두 상태를 번갈아 오가면 주기 2
흡수(absorbing)	한 번 들어가면 나오지 않는다( $p_{i i} = 1$ )	흡수 상태가 있고 모든 상태에서 흡수 상태에 도달할 수 있으면 흡수 연쇄
에르고딕(ergodic)	비주기이면서 양재귀인 상태	유한 기약 비주기 연쇄의 모든 상태가 여기에 해당한다

재귀·일시, 주기는 부류 속성이다. 같은 통신 부류의 상태는 모두 재귀이거나 모두 일시이며, 주기도 같다. 유한 연쇄에는 재귀 상태가 반드시 하나 이상 있다.

1차원 정수 위를 반반의 확률로 한 칸씩 오가는 단순 무작위 행보(random walk)는 모든 상태가 영재귀다. 2차원에서도 재귀지만 3차원 이상에서는 일시가 된다는 결과가 폴리아의 정리로 알려져 있다.

흡수 연쇄

흡수 상태들을 뒤로 모아 전이 행렬을 $P = (\begin{matrix} Q & R \\ 0 & I \end{matrix})$ 로 쓰면( $Q$ 는 일시 상태끼리의 전이), 기본 행렬 $N = (I - Q)^{- 1}$ 의 $(i, j)$ 성분은 $i$ 에서 출발해 흡수되기 전까지 $j$ 를 방문하는 기대 횟수다. 흡수까지 걸리는 기대 단계는 $N 𝟏$ , 각 흡수 상태로 끝날 확률은 $N R$ 이다. 가진 돈이 0이 되거나 목표액에 이르면 끝나는 도박꾼의 파산 문제가 대표적인 예다.

정상 분포와 수렴

확률 분포 $π$ 가 $π P = π$ 를 만족하면 정상 분포(stationary distribution)라 한다. 연쇄가 한 번 이 분포에 놓이면 그 뒤로도 분포가 바뀌지 않는다. 선형대수로 보면 $π$ 는 $P^{⊤}$ 의 고윳값 1에 대응하는 고유벡터를 합이 1이 되도록 정규화한 것이다. 확률 행렬의 고윳값 절댓값은 1을 넘지 않으며, 페론-프로베니우스 정리가 기약 연쇄에서 양의 정상 분포가 하나뿐임을 보장한다.

위 날씨 예에서 $π P = π$ 와 $π_{1} + π_{2} + π_{3} = 1$ 을 풀면 $π = (21 / 46, 13 / 46, 12 / 46) \approx (0.457, 0.283, 0.261)$ 이다. 오늘 날씨가 무엇이든 오래 지나면 맑을 확률은 약 45.7%로 수렴한다.

존재, 유일성, 수렴

조건	성질
기약 + 양재귀(유한 기약이면 자동)	정상 분포가 유일하게 존재하고 $π_{i} = 1 / m_{i}$ 다. $m_{i}$ 는 $i$ 에서 출발해 처음 돌아올 때까지의 기대 시간이다
기약 + 양재귀 + 비주기	어떤 초기 분포에서 출발해도 $P^{n}$ 의 모든 행이 $π$ 로 수렴한다(수렴 정리)
기약 + 양재귀(주기 있어도 됨)	에르고딕 정리: 한 경로에서 상태 $i$ 에 머문 시간 비율이 확률 1로 $π_{i}$ 에 수렴하고, 함수 $f$ 의 시간 평균 $\frac{1}{n} \sum_{t < n} f (X_{t})$ 가 공간 평균 $\sum_{i} π_{i} f (i)$ 로 수렴한다
주기적 연쇄	정상 분포는 있어도 $P^{n}$ 자체는 진동하며 수렴하지 않는다
기약이 아닌 연쇄	닫힌 재귀 부류마다 정상 분포가 따로 있어 유일하지 않을 수 있다

에르고딕 정리는 대수의 법칙을 독립이 아닌 표본으로 넓힌 것으로 볼 수 있다. MCMC가 "연쇄를 오래 돌린 뒤 표본 평균을 낸다"는 방식으로 기댓값을 구할 수 있는 근거다.

가역성과 혼합 시간

모든 $i, j$ 에 대해 $π_{i} p_{i j} = π_{j} p_{j i}$ (세부 균형, detailed balance)를 만족하면 $π$ 는 정상 분포이고, 연쇄는 시간을 거꾸로 돌려도 통계적으로 같은 가역(reversible) 연쇄다. 원하는 분포를 정상 분포로 갖는 연쇄를 설계할 때 이 조건을 맞추는 것이 가장 쉬운 방법이다.
정상 분포에 충분히 가까워지기까지 걸리는 단계 수를 혼합 시간(mixing time)이라 한다. 유한 연쇄에서는 두 번째로 큰 고윳값의 절댓값이 1에 가까울수록(스펙트럼 간격이 작을수록) 느리게 섞인다.

연속 시간 마르코프 연쇄

상태가 아무 시각에나 바뀔 수 있는 연속 시간 마르코프 연쇄(CTMC)는 전이 행렬 대신 생성 행렬(전이율 행렬) $Q$ 로 기술한다. 비대각 성분 $q_{i j} \geq 0$ 는 $i$ 에서 $j$ 로 넘어가는 비율, 대각 성분은 행의 합이 0이 되도록 $q_{i i} = - \sum_{j \neq i} q_{i j}$ 로 둔다.

상태 $i$ 에 머무는 시간은 비율 $- q_{i i}$ 인 지수 분포를 따른다. 기억 없는 성질을 가진 연속 분포가 지수 분포뿐이기 때문이다. 머문 뒤에는 $q_{i j} / (- q_{i i})$ 의 확률로 $j$ 로 넘어가는데, 이렇게 넘어간 상태만 모은 열을 내재 연쇄(embedded chain)라 한다.
시간 $t$ 뒤의 전이 확률은 $P (t) = e^{t Q}$ 이고, 정상 분포는 $π Q = 0$ 을 푼다.
포아송 과정, 출생·사망 과정, M/M/1 같은 대기행렬 모형이 대표 예다. 연속 시간 마르코프 과정 이론의 상당 부분은 콜모고로프가 1931년 논문에서 세웠다.^[1]

역사

연도	사건
1906	마르코프가 서로 의존하는 확률 변수에도 대수의 법칙이 성립함을 보이는 논문을 카잔 대학 물리수학회보에 발표. 마르코프 연쇄 연구의 시작으로 꼽힌다^[2] 당시 독립성이 대수의 법칙의 필요조건이라고 본 네크라소프의 주장을 반박하려는 동기가 있었다고 알려져 있다
1913	1월 23일 상트페테르부르크 과학 아카데미에서 푸시킨의 운문 소설 《예브게니 오네긴》 첫 장과 둘째 장 16연에서 뽑은 러시아 글자 20,000자를 모음·자음 두 상태의 연쇄로 분석한 결과를 발표. 모음 비율은 약 0.432였지만, 모음 다음에 모음이 올 확률은 0.128, 자음 다음에 모음이 올 확률은 0.663으로 크게 달라 글자들이 독립이 아님을 보였다^[3]
1931	콜모고로프가 연속 시간 마르코프 과정의 해석적 이론을 정리
1948	섀넌이 〈통신의 수학적 이론〉에서 영어 문장을 앞 글자·앞 단어에 의존하는 마르코프 과정으로 근사해 정보 엔트로피를 설명. 글자·단어 n-gram 근사로 문장을 만들어 보인 초기 사례다^[4]
1953	메트로폴리스 등이 마르코프 연쇄로 볼츠만 분포의 표본을 뽑는 메트로폴리스 알고리즘 발표^[5]
1970	헤이스팅스가 비대칭 제안 분포로 일반화(메트로폴리스-헤이스팅스)^[6]
1998	브린과 페이지가 웹 페이지 순위를 무작위 서퍼의 마르코프 연쇄로 정의한 페이지랭크를 발표^[7]

마르코프의 1913년 분석은 글자열을 확률 과정으로 다룬 것으로, 앞의 글자를 보고 다음 글자의 확률을 매긴다는 오늘날 언어 모델의 발상과 맞닿아 있다.

응용

페이지랭크

웹 서퍼가 지금 보는 페이지의 링크 중 하나를 무작위로 누르고, 가끔은 지루해져 아무 페이지로나 이동한다고 가정하면 서퍼의 위치는 마르코프 연쇄를 이룬다. 페이지랭크는 이 연쇄의 정상 분포, 즉 서퍼가 오래 돌아다닐 때 각 페이지에 머무는 비율이다. 원 논문은 링크를 따라갈 확률(감쇠 계수) $d$ 를 보통 0.85로 두었다. 무작위 이동 항은 링크 구조만으로는 기약·비주기가 아닐 수 있는 연쇄를 기약·비주기로 만들어 정상 분포가 유일하게 정해지게 하는 역할도 한다. 계산은 정규화된 링크 행렬의 주 고유벡터를 반복법으로 구하는 것과 같다.^[7] 문장 사이 유사도 그래프에 같은 방식을 적용한 것이 텍스트 랭크다.

마르코프 연쇄 몬테카를로

직접 표본을 뽑기 어려운 분포 $π$ (베이즈 사후 분포, 통계역학의 볼츠만 분포 등)가 있을 때, $π$ 를 정상 분포로 갖는 연쇄를 만들어 오래 돌리면 그 경로를 $π$ 의 표본처럼 쓸 수 있다. 메트로폴리스-헤이스팅스 알고리즘은 현재 상태 $x$ 에서 후보 $x^{'}$ 를 제안 분포 $q (x^{'} ∣ x)$ 로 뽑고, 확률

$α = \min (1, \frac{π (x^{'}) q (x ∣ x^{'})}{π (x) q (x^{'} ∣ x)})$

로 받아들인다. 이렇게 하면 세부 균형이 성립해 $π$ 가 정상 분포가 된다. $π$ 의 정규화 상수를 몰라도 비율만 있으면 되므로 베이즈 추론에 특히 유용하다.^[5]^[6] 변수를 하나씩 조건부 분포에서 다시 뽑는 깁스 표집도 같은 계열이며, 베이지안 네트워크의 근사 추론과 깁스 분포 모형에 쓰인다. 결과가 맞으려면 연쇄가 충분히 섞여야 하므로 초기 구간 버리기(burn-in), 수렴 진단이 실무의 핵심 문제다.

언어 모델과 텍스트 생성

n-gram 언어 모델은 다음 단어의 확률이 직전 $n - 1$ 개 단어에만 의존한다고 가정하는 $(n - 1)$ 차 마르코프 연쇄다. 말뭉치에서 단어 쌍·세 쌍의 빈도를 세어 전이 확률을 추정하고, 그 확률대로 다음 단어를 뽑으면 그럴듯한 문장이 만들어진다. 트랜스포머 기반 대형 언어 모델은 컨텍스트 윈도우 안의 이전 토큰 전체를 조건으로 삼으므로 짧은 고정 차수의 마르코프 가정에서 벗어나지만, 생성 과정 자체는 "현재까지의 문맥이라는 상태에서 다음 토큰을 확률적으로 뽑는" 형태로 이해할 수 있다(언어 모델 디코딩).

마르코프 연쇄를 바탕으로 한 모형들

모형	마르코프 연쇄에 더한 것	대표 용도
마르코프 연쇄	(기본) 상태를 직접 관측	날씨·인구 이동, 페이지랭크, MCMC
은닉 마르코프 모델(HMM)	상태는 보이지 않고, 상태마다 확률적으로 나오는 관측값만 보인다	음성 인식, 품사 태깅, 생물 서열 분석
마르코프 결정 프로세스(MDP)	행동과 보상. 전이 확률이 현재 상태와 행동에 달려 있다	강화 학습, 최적 제어
부분 관측 MDP(POMDP)	HMM처럼 상태를 직접 못 보는 MDP	로봇 계획, 불확실성 아래 의사결정
마르코프 랜덤 필드	시간 순서 대신 방향 없는 그래프 위의 이웃 의존	영상 잡음 제거, 이미지 분할

이 밖에 확산 모델의 순방향 과정은 데이터에 단계마다 가우스 잡음을 더하는 마르코프 연쇄이고, 생성은 그 역과정을 학습한 연쇄를 따라간다. 몬테카를로 트리 탐색과 Q-러닝도 환경을 마르코프 결정 프로세스로 가정한다.

그 밖의 분야

대기행렬과 네트워크 성능: 도착·서비스를 연속 시간 연쇄로 모형화(대기행렬 이론)
금융·경제: 신용 등급 전이 행렬, 소득 분포 모형
생물학: 개체군 유전학, DNA 서열의 염기 의존성
소프트웨어 테스트: 사용 패턴을 연쇄로 모형화해 테스트 경로를 뽑는 통계적 사용 테스트

파이썬 예시

앞의 날씨 연쇄로 여러 단계 전이, 정상 분포, 모의 실험을 계산한다.

import numpy as np

states = ["맑음", "흐림", "비"]
P = np.array([
    [0.7, 0.2, 0.1],   # 맑음 -> 맑음, 흐림, 비
    [0.3, 0.4, 0.3],   # 흐림 -> ...
    [0.2, 0.3, 0.5],   # 비   -> ...
])

# 1) n단계 전이 확률: 오늘 맑으면 3일 뒤 날씨 분포
x0 = np.array([1.0, 0.0, 0.0])
print("3일 뒤:", x0 @ np.linalg.matrix_power(P, 3))

# 2) 정상 분포: P^T의 고윳값 1에 해당하는 고유벡터를 합이 1이 되게 정규화
w, v = np.linalg.eig(P.T)
pi = np.real(v[:, np.argmin(np.abs(w - 1))])
pi = pi / pi.sum()
print("정상 분포:", pi.round(4))

# 3) 모의 실험: 오래 돌리면 각 상태에 머문 비율이 정상 분포에 가까워진다
rng = np.random.default_rng(0)
s, counts = 0, np.zeros(3)
for _ in range(100_000):
    s = rng.choice(3, p=P[s])
    counts[s] += 1
print("모의 실험 비율:", (counts / counts.sum()).round(4))

실행 결과는 다음과 같다. 모의 실험 비율이 정상 분포와 거의 같아지는 것이 에르고딕 정리의 내용이다.

3일 뒤: [0.51  0.268 0.222]
정상 분포: [0.4565 0.2826 0.2609]
모의 실험 비율: [0.4594 0.2812 0.2593]

한계

마르코프 성질은 가정이다. 실제 현상이 먼 과거에 의존하면(문장의 앞뒤 맥락, 계절성 있는 날씨) 상태를 넓혀야 하는데, 그러면 상태 수와 추정할 전이 확률이 기하급수로 늘고 데이터가 부족해진다. n-gram 모델이 겪은 희소성 문제가 대표적이다.
시간 동질성 가정도 현실과 어긋나기 쉽다. 전이 확률이 시간에 따라 변하면 모형을 다시 추정해야 한다.
MCMC에서는 연쇄가 언제 충분히 섞였는지 확실히 알기 어렵고, 봉우리가 여럿인 분포에서는 한 봉우리에 갇혀 잘못된 답을 낼 수 있다.

같이 보기

각주

↑ A. Kolmogoroff, 〈Über die analytischen Methoden in der Wahrscheinlichkeitsrechnung〉, Mathematische Annalen 104, 1931. doi:10.1007/BF01457949
↑ А. А. Марков, 〈Распространение закона больших чисел на величины, зависящие друг от друга〉(Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie drug ot druga), Известия Физико-математического общества при Казанском университете, 2-я серия, т. 15, 1906, pp. 135~156.
↑ A. A. Markov, 〈An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains〉(1913), David Link 외 영역, Science in Context 19(4), 2006, pp. 591~600. doi:10.1017/S0269889706001074
↑ C. E. Shannon, 〈A Mathematical Theory of Communication〉, Bell System Technical Journal 27, 1948. doi:10.1002/j.1538-7305.1948.tb01338.x
↑ ^5.0 ^5.1 N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, E. Teller, 〈Equation of State Calculations by Fast Computing Machines〉, Journal of Chemical Physics 21(6), 1953. doi:10.1063/1.1699114
↑ ^6.0 ^6.1 W. K. Hastings, 〈Monte Carlo sampling methods using Markov chains and their applications〉, Biometrika 57(1), 1970. doi:10.1093/biomet/57.1.97
↑ ^7.0 ^7.1 Sergey Brin, Lawrence Page, 〈The Anatomy of a Large-Scale Hypertextual Web Search Engine〉, Computer Networks and ISDN Systems 30, 1998. 스탠퍼드 공개본

참고 문헌

Charles M. Grinstead, J. Laurie Snell, 《Introduction to Probability》, American Mathematical Society, 1997. 11장 Markov Chains
James R. Norris, 《Markov Chains》, Cambridge University Press, 1997.
David A. Levin, Yuval Peres, Elizabeth L. Wilmer, 《Markov Chains and Mixing Times》, American Mathematical Society, 2009.

[1] A. Kolmogoroff, 〈Über die analytischen Methoden in der Wahrscheinlichkeitsrechnung〉, Mathematische Annalen 104, 1931. doi:10.1007/BF01457949

[2] А. А. Марков, 〈Распространение закона больших чисел на величины, зависящие друг от друга〉(Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie drug ot druga), Известия Физико-математического общества при Казанском университете, 2-я серия, т. 15, 1906, pp. 135~156.

[onegin-3] A. A. Markov, 〈An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains〉(1913), David Link 외 영역, Science in Context 19(4), 2006, pp. 591~600. doi:10.1017/S0269889706001074

[4] C. E. Shannon, 〈A Mathematical Theory of Communication〉, Bell System Technical Journal 27, 1948. doi:10.1002/j.1538-7305.1948.tb01338.x

[metro-5] 5.0 ^5.1 N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, E. Teller, 〈Equation of State Calculations by Fast Computing Machines〉, Journal of Chemical Physics 21(6), 1953. doi:10.1063/1.1699114

[hastings-6] 6.0 ^6.1 W. K. Hastings, 〈Monte Carlo sampling methods using Markov chains and their applications〉, Biometrika 57(1), 1970. doi:10.1093/biomet/57.1.97

[pagerank-7] 7.0 ^7.1 Sergey Brin, Lawrence Page, 〈The Anatomy of a Large-Scale Hypertextual Web Search Engine〉, Computer Networks and ISDN Systems 30, 1998. 스탠퍼드 공개본

[1]

[2]

[3]

[4]

[5]

[6]

[7]