마르코프 연쇄

확률론에서 마르코프 연쇄(Марков 連鎖, 영어: Markov chain)는 이산 시간 확률 과정이다.

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

정의

확률 공간 $\Omega$와, 모든 집합이 가측 집합인 가측 공간 $E$가 주어졌다고 하자. 그렇다면, 메모리 k의 마르코프 연쇄는 다음 성질을 만족시키는 일련의 확률 변수 $X_{1},X_{2},\dots \colon \Omega \to E$이다.

만약 다음 식의 양변이 존재한다면,

${\begin{aligned}&\Pr(X_{n}=x_{n}|X_{n-1}=x_{n-1},\ldots ,X_{1}=x_{1})\\=&\Pr(X_{n}=x_{n}|X_{n-1}=x_{n-1},\ldots ,X_{n-K}=x_{n-K}).\end{aligned}}$

이 경우, $E$를 메모리 k의 마르코프 연쇄 $\{X_{i}\}$의 상태 공간(영어: state space)이라고 한다. 만약 메모리가 주어져 있지 않는 마르코프 연쇄는 메모리가 1인 마르코프 연쇄이다.

(메모리가 1인) 마르코프 연쇄는 이는 메모리가 없는 과정을 나타낸다. 과거의 상태가 알려져 있더라도, 이는 미래 상태의 조건부 기댓값에 영향을 미치지 않는다. 이러한 성질을 마르코프 성질(영어: Markov property)이라고 한다.

다음 성질을 만족시키는 마르코프 연쇄 $X_{i}\colon \Omega \to E$를 시간 동질 마르코프 연쇄(영어: time-homogeneous Markov chain)라고 한다. 모든 $i\in \mathbb {N}$, $x,y\in E$에 대하여,

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

다시 말해, 시간에 따라서 전이 확률은 변하지 않는다.

이와 유사하게, $i\in \mathbb {N}$ 대신 실변수 $t\in \mathbb {R}$에 의존하는 경우도 정의할 수 있다. 이 경우를 연속 마르코프 과정(영어: continuous Markov process)이라고 한다.

예

유향 그래프로 나타낸 시간 동질 마르코프 연쇄의 예

상태 공간이 (모든 부분집합이 측도가능한) 유한 집합이라고 하자. 이 경우, 시간 동질 마르코프 연쇄는 각 변에 0과 1 사이의 실수가 붙어 있는 유향 그래프로 표현된다. 이 경우 그래프는 다음과 같이 해석된다.

• 각 꼭짓점은 상태공간의 원소에 대응된다.
• 상태 $x_{1}\in E$에서 다른 상태 $x_{2}\in E$로 가는 변은 정확히 하나가 있으며, 이 변에 붙어 있는 값은 $\Pr(X_{n+1}=x_{2}|X_{n}=x_{1})$이다. 만약 이 확률이 0이라면 변을 생략할 수 있다.

이러한 그래프를 상태 다이어그램(영어: state diagram)이라고 한다.

역사

러시아의 수학자 안드레이 마르코프가 1906년에 도입하였다.

같이 보기

• 마르코프 결정 과정
• 마르코프 네트워크

참고 문헌

• Trivedi, Kishor S. (2002). 《Probability and Statistics with Reliability, Queueing, and Computer Science Applications》 (영어). John Wiley & Sons. ISBN 0-471-33341-7. 
• Bolch, G. (2006). (영어) 2판. John Wiley. ISBN 978-0-7923-9650-5. 
• Nummelin, E. (1984). 《General irreducible Markov chains and non-negative operators》 (영어). Cambridge University Press. ISBN 0-521-60494-X. 

외부 링크

• “Markov chain”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Markov process”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Markov chain, generalized”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Markov chain, recurrent”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Markov chain”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Markov process”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Markov sequence”. 《Wolfram MathWorld》 (영어). Wolfram Research.