Markov Chain (마르코프 체인)

1. 개념

Markov chain은 Markov 성질(특정 상태의 확률은 오직 과거의 상태에 의존하는 것)을 가진 이산확률과정(Discrete-time Stochastic Process)이다. 예를 들어, 오늘의 날씨가 맑다면 내일의 날씨는 맑을지 비가 내릴지를 확률적으로 표현할 수 있다.

 

여러 상태들($x_1, x_2, x_3, ...$)이 있고, $x_i$에서 $x_j$로 이동할 조건부 확률분포(transition distribution) $T(x_j|x_i)$가 주어져 있어서 매턴마다 이 확률 값에 따라 상태들 사이를 이동하는 것을 말한다. 이는 확률이 정해져 있으므로 "특정조건"을 만족할 때는 일정한 패턴이 나타나게 된다. 예를 들어, "100번 이동했다면 평균적으로 3번은 출발점에 돌아온다"라는 것과 같다.

 

또한 Markov Chain은 어떤 지점에서 시작하더라도, 상태 사이를 충분히 많은 횟수 이동하게 되면 각 상태의 방문횟수의 비율이 일정한 값으로 수렴하게 된다. 다시 말해, 상태들의 방문횟수의 비율이 특정 확률분포로 수렴하게 되고 우리는 이 분포를 stationary distribution이라 부른다.

 

 

2. 수식

이산형 확률 변수 X와 유한한 이산형 state space를 가진 X의 sequence(수열), 즉 이산 확률 과정(Discrete-time Stochastic Process)을 고려한다.

Discrete-time Stochastic Process

 

이때 확률 변수 X가 다음과 같은 식을 만족한다면, 우리는 이 확률 과정을 마르코프 체인(Markov Chain)이라 부른다.

 

이 관계식은 0번째부터 t번째 까지의 모든 data(; 과거)가 있을 때, (t+1)번째 데이터(; 미래)는 t 번째 데이터에만 영향을 받는다는 뜻이다. 즉, 마코프 체인의 확률 과정은 미래가 과거와는 독립이고 오로지 직전 시점에만 영향을 받는다는 것이다.

​

여기서 핵심은 특정 시점의 상태 확률은 단지 그 이전 상태에만 의존한다는 것이다. 다시 말해, 한 상태에서 다른 상태로의 전이(transition)는 그동안 상태 전이에 대한 긴 이력(history)을 필요로 하지 않고 바로 직전 상태에서의 전이로 추정할 수 있다는 뜻이다.

 

3. 구성 요소

(Finite discrete) State Space

 

$ X = {1,2,3,...,N} $

 

• 상태를 나타내는 공간 (N = 카테고리 갯수 = 상태의 갯수)
• $x^t$를 t 시점에서의 날씨 상태라고 가정하고 날씨 상태를 (1 = 맑음 , 2 = 흐림, 3 = 비)와 같이 정의하면, State Space는 {1, 2, 3}이다.

 

Transition Probabiltiy (Matrix)

 

$ P_{ij}^{(t)} = P(x^{t+1}=j|x^{t}=i)$

$(\sum_{j\in x}^{}P_{ij}^{(t)} = 1) $

 

• 전이 확률은 t 시점의 i번째 state에서 (t+1)시점의 j번째 state로 변화하는 확률이다.
• 오늘 날씨가 맑을때 내일 날씨는 흐릴 확률 : $ Pr( 흐림 | 맑음 ) = Pr( x^{(t+1)} = 2 | x^t = 1) = P_{12}$

 

Stationary Probability

$\pi (j) = \sum_{i\in x}^{}\pi(i)P_{ij}$

 

t → ∞ 가 되면, 즉 시간이 충분히 흐르면, 다시말해 transition probability를 이용해서 내일 맑을 확률과 흐릴 확률 그리고 비가올 확률을 계산할 수 있다. 그리고 다시 그 값을 이용해 모레의 날씨의 확률 분포를 계산할 수 있다. 이 과정을 계속 반복하다 보면 어느 순간 부터 그날의 날씨 확률분포가 그 전날과 같아 지는 때가 온다. 즉, transition probability를 따르는 확률이 고정적으로 생기게 되는 것이다. 그렇게 되면 그 확률은 이제 이전 확률에 영향을 받지 않게 된다. 우리는 이렇게 고정되어 움직이지 않아 평형 상태에 도달한 날씨의 확률 분포를 "Stationary probability"라고 부른다.