마르코프 연쇄

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

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

정의[편집]

확률공간 \Omega가측공간 E가 주어졌다고 하자. 그렇다면, 메모리 k의 마르코프 연쇄는 다음 성질을 만족시키는 일련의 확률변수 X_1,X_2,\dots\colon\Omega\to E이다.

만약 다음 식의 양변이 존재한다면,
\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})

이 경우, 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년 도입하였다.[1]

참고 문헌[편집]

  1. (러시아어) Markov, A.A. (1906년). Распростпаненіе закона большихъ чиселъ на величиы, забисящія другъ отъ друга. 《Известия физико-математического общества при Императорском Казанском университете》 15 (4): 135–156. JFM 37.0265.01.
  • Kishor S. Trivedi, Probability and Statistics with Reliability, Queueing, and Computer Science Applications, John Wiley & Sons, Inc. New York, 2002. ISBN 0-471-33341-7.
  • G.Bolch, S.Greiner, H.de Meer and K.S.Trivedi, Queueing Networks and Markov Chains, John Wiley, 2nd edition, 2006. ISBN 978-0-7923-9650-5
  • E. Nummelin. "General irreducible Markov chains and non-negative operators". Cambridge University Press, 1984, 2004. ISBN 0-521-60494-X

바깥 고리[편집]