마르코프 체인 (Markov Chains) 이해하기 앞서 필요한 개념
확률과정
확률과정 Xt = {X0, X1, X2... Xt}는 시간이 경과함에 따라 시스템의 상태가 어떻게 변화하는지를 나타내는 수리적 표현
어떤 시점에서 고정된 값을 갖는 것이 아니라, 여러 가능한 값 중 하나의 값을 확률적으로 갖는 것을 의미한다.
상태는 이산적이며 상태공간은 유한하다고 가정
확률과정의 분류 [시스템 상태 (이산, 연속) / 관측 시점(이산, 연속)]
(1) 이산시간 이산상태 확률과정
(2) 이산시간 연속상태 확률과정
(3) 연속시간 이산상태 확률과정
(4) 연속시간 연속상태 확률과정
연속 상태를 이산 상태로 변환할 수 있다.
ex) 온도 10~20도 -> 상태 1로 인코딩
마르코프 체인
다음 두 가지 조건을 만족하는 확률과정을 마르코프 체인이라고 한다.
(1) 시간은 이산적으로 변한다.
(2) 마르코프 성질: 시간 (t+1)에 사건이 발생할 확률이, 시간 t에 발생한 사건에만 영향을 받는다.
-> 과거의 상태와 현재의 상태가 주어졌을 때,
미래의 상태에 대한 조건부 확률분포는 과거의 상태에 독립이고 현재의 상태에만 의존한다.
마르코프 성질을 만족할 때,
1. 이산 상태 확률과정이면 마르코프 체인
2. 연속 상태 확률과정이면 마르코프 프로세스
전이 확률 (transition probability) (1단계)
마르코프 체인에서 조건부 확률 P(X_t+1 =j / X_t = i)을 전이 확률이라 한다.
정상 전이 확률 (stationary transition probability)
임의의 t에 대해 P(X_t+1 =j / X_t = i) = P(X_1 =j / X_0= i)이 성립하면 정상 전이 확률이라 한다.
향후 모든 전이확률은 정상이라고 가정하며, 1단계 전이확률은 다음과 같이 표현한다.
-> p_ij
n단계 전이확률
임의의 시점에서 상태 i에 있던 시스템이 n단계 전이 후 상태 j에 있을 조건부 확률
P(X_t+n =j / X_t = i) = p_ij ^ (n)
특정 시스템이 마르코프 성질을 만족하면 마르코프 체인으로 모형화 할 수 있고,
이때 전이 행렬 또는 상태전이도로 나타낼 수 있다.
전이 행렬을 전이 확률로 이루어져 있으며, 모든 전이행렬의 각 행의 합은 1이다.
Chapman-Kolmogorov 방정식
1단계 전이확률을 이용하여 n단계 전이확률을 구하는 식
중간 단계인 m단계에서 어떤 상태에 있는지에 대해 조건화한 식이다.
간단하게 얘기하면, n단계 전이행렬은 1단계 전이행렬을 n번 곱하면 얻을 수 있다는 의미이다.
마르코프 체인의 매우 중요한 성질은 t가 커짐에 따라 확률이 일정한 값으로 수렴한다는 것이다.
즉 상태행렬 P(n)는 어떤 행렬 P로 수렴한다.
이 P를 안정상태의 확률행렬이라고 한다.
도달 가능 (accessible)
p_ij ^ n > 0 인 n이 존재하면 도달 가능하다고 표현한다.
시스템이 상태 i에서 시작하였을 때 궁극적으로 상태 j에 도달할 수 있다는 것을 의미.
교통 가능 (communication)
상태 j가 상태 i로부터 도달가능하고, 상태 i는 상태 j로부터 도달가능하면 상태 i와 상태 j는 서로 교통 가능하다고 표현한다.
- 모든 상태는 자기 자신과 교통 가능 (n=0일때)
- 상태 i가 상태 j와 교통 가능하면 상태 j는 상태 i 와 교통가능 (i <-> j)
- 상태 i가 상태 j와 교통 가능하고, 상태 j가 상태 k와 교통 가능하면 상태 i는 상태 k와 교통가능 (i -> j -> k)
마르코프 체인을 구성하는 모든 상태는 서로 교통가능한 상태들로 이루어진 집단(communicating class)으로 분류 가능.
마르코프 체인을 구성하는 집단이 하나 뿐일 경우 이를 기약(irreducible)이라 한다. 이 경우 모든 상태가 서로 교통 가능.
상태의 분류
➀ 일시상태(transient state): 만약 과정이 어떤 상태를 떠난 후 그 상태로 다시는 돌아오지 않을 수 있다면 그 상태를 일시상태라 함(돌아올 수도 있지만 다시는 돌아오지 않을 확률이 0보다 큰 상태를 말함)
➁재귀상태(recurrent state): 만약 과정이 어떤 상태를 떠난 후 그 상태로 반드시 돌아온다면 그 상태를 재귀상태라 함
➂ 흡수상태(absorbing state): 만약 과정이 어떤 상태에 들어온 후 다시는 그 상태를 떠날 수 없다면 그 상태를 흡수상태라 함. 흡수상태는 재귀상태의 일종이며 상태 i가 흡수상태이면 p_ii = 1
집단특성(class property)
동일 집단(class)에 속하는 상태는 모두 특정 성질을 갖거나 갖지 않거나 하는 성질
상태 i의 주기(period)
p_ii^n > 0 을 만족하는 모든 양수 n의 최대공약수를 상태 i의 주기라 한다
-주기가 1인 상태를 비주기적(aperiodic)이라 함
-주기성은 집단특성이다
-연속시간은 늘 비주기적이다.
에르고딕(ergodic)
- 유한상태 마코프체인에서 비주기적(주기=1) 재귀상태를 에르고딕 상태라 한다
- 모든 상태가 에르고딕 상태일 때 마코프체인은 에르고딕이라고 한다
마르코프 체인의 극한확률 (안정상태확률)
마코프체인이 기약이고 에르고딕하면 다음과 같은 극한확률(π_j)이 존재하고 상태 i와 독립이다
안정 상태 확률
ㅠj는 다음과 같은 안정 상태 방정식(steady state equation)을 유일하게 만족한다
식 (*)에서 한 개의 식은 여분(redundant) 이므로 식 하나를 제외하고 풀어야 한다.
π = (π0, π1, ... πM)으로 두고, 식 (*)를 행렬로 표현하면 π = πP
π = (π0,π1, ...πM)을 안정상태확률이라 한다.
안정상태확률이란 많은 수의 전이 후에 과정이 어떤 상태 j에 있을 확률이 초기상태에 무관하게 ㅠj임을 의미한다
마코프체인의 극한확률이 존재하기 위한 조건은 기약과 에르고딕(재귀적, 비주기적)이다.
만약 비주기적이라는 조건이 없다면, 극한확률은 존재하지 않는다.