마르코프 연쇄

마르코프 연쇄(Markov chain)는 마르코프 성질을 가진 이산 시간 확률 과정이다. 러시아 수학자인 안드레이 마르코프의 이름에서 왔다.

마르코프 연쇄는 시간에 따른 시스템 상태의 변화를 나타낸다. 매 시간마다 시스템은 상태를 바꾸거나 같은 상태를 유지한다. 상태의 변화를 전이라 한다. 마르코프 성질은 과거와 현재 상태가 주어졌을 때의 미래 상태의 조건부 확률 분포가 과거 상태와는 독립적으로 현재 상태에 의해서만 결정된다는 걸 뜻한다.

정의

마르코프 연쇄는 마르코프 성질을 가진 랜덤변수 $X_1, X_2, X_3$의 수열이고 현재의 상태는 과거의 상태와 미래의 상태와는 독립적이다. 즉,

$\Pr(X_{n+1} = x | X_n = x_n , \ldots , X_1 = x_1 )=\Pr(X_{n+1} = x | X_n = x_n)$

$X_i$는 연쇄의 상태공간(state space)라 불리는 셀 수 있는 집합 S의 원소이다. 마르코프 연쇄는 종종 edge가 한 상태에서 다른 상태로 갈 수 있는 확률로 표시(label)이 된 방향그래프(directed graph)로 종종 표현된다.

변이(Variant)

연속 시간 마르코프 과정은 연속 인덱스를 가진다.

시간 균질적(Time-homogeos) 마르코프 체인(또는, 시간 균질 전이 확률(time-homogeneous transition probabilities))은 다음과 같다. 모든 $n$에 대해

$\Pr(X_{n+1} = x | X_n = y )=\Pr(X_{n} = x | X_{n-1} = y)$

유한 $m$차 마르코프 체인(또는 메모리 $m$을 가진 마르코프 체인)은 다음과 같다. 모든 $n$에 대해

$\begin{align} &\Pr(X_n = x_n | X_{n-1} = x_{n-1}, X_{n-2}=x_{n-2}, \ldots ,X_{1}=x_{1}) \\ =&\Pr(X_n = x_n | X_{n-1} = x_{n-1}, X_{n-2}=x_{n-2}, \ldots ,X_{n-m}=x_{n-m}) \end{align}$