마르코프 연쇄, Markov chain

마르코프 연쇄

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

마르코프 연쇄는 시간에 따른 시스템 상태의 변화를 나타낸다.
매 시간마다 시스템은 상태를 바꾸거나 같은 상태를 유지한다.
상태의 변화를 전이라 한다.

마르코프 성질은
과거와 현재 상태가 주어졌을 때의 미래 상태의 조건부 확률 분포가
과거 상태와는 독립적으로 현재 상태에 의해서만 결정된다는 걸 뜻한다.

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

즉, 

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

변이(Variant)

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

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

모든 n에 대해
Pr(Xn + 1 = x | Xn = y) = Pr(Xn = x | Xn − 1 = y)

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

모든 n에 대해