마르코프 연쇄(Markov chain)는 확률론에서 정의되는 이산 시간 확률 과정(discrete-time stochastic process)의 하나이다. 시간에 따라 계(system)의 상태가 변화하는 과정을 확률적으로 모델링하며, 매 시간마다 계는 상태를 바꾸거나 같은 상태를 유지한다. 상태의 변화를 전이(transition)라고 한다.
마르코프 연쇄의 핵심은 마르코프 성질(Markov property)에 있다. 이는 과거와 현재 상태가 주어졌을 때 미래 상태의 조건부 확률 분포가 과거 상태와는 독립적으로, 오직 현재 상태에 의해서만 결정된다는 성질을 의미한다. 다시 말해, "미래는 오직 현재에만 의존하며 과거에는 의존하지 않는다"는 무기억성(memorylessness)을 가진다. 이러한 특성 때문에 마르코프 연쇄는 메모리 1의 확률 과정으로 분류된다.
수학적으로, 상태 공간 $E$와 확률 공간 $\Omega$가 주어졌을 때, 일련의 확률 변수 $X_1, X_2, \dots : \Omega \to E$가 다음 조건을 만족하면 이를 마르코프 연쇄라고 정의한다.
$$ \Pr(X_n = x_n \mid X_{n-1} = x_{n-1}, \dots, X_1 = x_1) = \Pr(X_n = x_n \mid X_{n-1} = x_{n-1}) $$
즉, $n$번째 상태의 확률은 직전 상태 $X_{n-1}$에만 의존한다.
시간이 지나도 전이 확률이 변하지 않는 경우를 시간 동질 마르코프 연쇄(time-homogeneous Markov chain)라고 한다. 상태 공간이 유한 집합인 시간 동질 마르코프 연쇄는 각 변(edge)에 0과 1 사이의 전이 확률이 할당된 유향 그래프(directed graph)로 표현할 수 있으며, 이를 상태 다이어그램(state diagram)이라고 부른다.
마르코프 연쇄는 러시아의 수학자 안드레이 마르코프(Andrey Markov, 1856–1922)가 1906년에 처음 도입하였다. 마르코프는 대수의 법칙을 상호 의존적인 확률 변수로 확장하는 연구 과정에서 이 개념을 제시하였다.
마르코프 연쇄는 현대에 이르러 다양한 분야에서 활용된다. 대표적인 응용 분야로는 구글의 페이지랭크(PageRank) 알고리즘, 자연어 처리(NLP)에서의 언어 모델링, 통신 네트워크 모델링, 강화 학습, 마르코프 연쇄 몬테카를로(MCMC) 방법, 생물정보학, 경제학 및 금융 모델링 등이 있다. 마르코프 연쇄의 개념을 확장한 것으로는 마르코프 결정 과정(Markov decision process)과 마르코프 네트워크(Markov network) 등이 있다.
