[확률]Markov Process

Markov Chain

마르코브 체인(MC)은 여러 개의 state들의 연결관계로 이루어진 그래프이다. MC의 state의 개수는 유한할 수도 있고 무한할 수도 있다.

State of chain

Markov chain의 여러가지 상태의 정의에 대해서 알아보자. state란 다음 두 가지 의미 모두 쓰여 햇갈릴 수도 있다.

1. Markov chain의 가장 작은 구성 요소이다. state $i$는 그래프의 하나의 노드로 생각하면 된다.
2. state와 chain의 상태를 다룬다. 다음에 배울 Communicate는 state $i$와 $j$간의 상태를 의미하기도 하며 chain의 상태를 의미하기도 한다.

Accessible

• state $i$는 state $j$에 대해서 accessible : if 어떤 양수 $n$에 대해서 $P_{i, j}^n > 0$을 만족한다
• state $i$가 state $j$에 대해서 accessible하고 state $j$가 state $i$에 대해서 accessible하다면 communicate라고 한다.

Communicate

• 두 state $i, j$간에 이동할 수 있는 경로가 있다면 두 state가 commnicate하다고 말한다.
• communicate란 개념은 state들을 구분된 집합으로 나누게 되는데 집합 내의 모든 state간에 communicate하다면 그 Markov Chain을 communicate class라고 한다.
• 만약 A 클래스에서 B 클래스로 가는 경로가 있다면 A 클래스에서 B클래스로 이동하는 것은 가능하나 이 경우 다시 A클래스로는 돌아갈 수 없다.
• B클래스에서 A클래스로 갈 수 있다면 A와 B간에 communicate 성질을 만족하기 때문에 구분된 집합이 아니게 되기 때문이다.
• Markov chain은 irreducible하다. 만약 모든 state가 하나의 communicate 클래스에 존재한다면.

irreducible

• 캠브리지 영어사전에 따르면 irreducible은 “imposible to make smaller or simpler” 라고 나와있다.
• 더 단순화 할 수 없다는 의미는 그래프(graph)를 더 이상 나눌수 없다는 의미이다.
• 그래프를 단순화(reducible)할 수 있다는 것은 하나의 그래프를 두 개 이상의 communicate 클래스로 나눌 수 있다는 의미이다. 즉 어떤 state $i$가 state $j$에 대해서 accessible 하지 않은 경우가 있다는 의미이다.
• 강하게 결합된 그래프(Strongly connected graph)라는 개념이 있는데 어떤 노드들 간에도 서로 이동할 수 있는 경로가 존재한다는 뜻이고 이는 하나의 communicate 클래스를 의미한다.
• MC(Markov chain)이 irreducible하다는 것은 모든 state가 더 이상 나눌 수 없는 하나의 communicate 클래스에 존재한다는 것. 다른 말로 강하게 결합된 그래프라는 것이다.

다음 배울 Transient와 recurrent라는 개념을 알아보기 전에 한가지 개념에 대해서 소개하려고 한다.
$r_{i,j}^t$는 state $i$에서 출발해 $j$를 목표로 이동하는 데 state $j$에 step $t$만에 처음 도착할 확률을 의미한다.
수학적으로 표현하면 좀 복잡하지만 방금 한 말을 다시 바꾸어 표현하면 다음과 같다.

$r_{i,j}^t = Pr(X_t = j$ and for $1 < s < t -1, X_s \ne j | X_0 = i)$

Transient

• 만약 $i$에서 출발해서 $i$로 돌아오는 확률을 모두 합해도 1보다 작다면 즉 $\sum_{t>=1}r_{i,i}^t < 1$을 만족할 때 state $i$ 는 transient하다고 한다.
• Markov Chain에서 단 하나의 state라도 transient하다면 Chain을 transient하다고 한다.

Recurrent

• 만약 $i$에서 출발해서 $i$로 돌아오는 확률을 모두 합해서 1이 된다면 즉 $\sum_{t>=1}r_{i,i}^t = 1$을 만족할 때 state $i$ 는 recurrent하다고 한다.
• state $i$가 recurrent하다면 $i$에서 100번 출발한다면 결국 다시 $i$로 100번 돌아온다는 것이다.
• recurrent state $i$에 대해서 $h_{i,i}$는 $i$에서 출발해서 $i$로 몇 번의 step만에 돌아올지에 대한 예상 step이다. 수학적 용어로 기댓값(Expectation)이라고 한다. step $t$에 각각의 확률 $r_{i,i}^t$를 곱한 값들을 모두 합하면 기대값이 된다.
• $h_{i,i} = \sum_{t>=1}t\times r_{i,i}^t$
• Markov Chain의 모든 state가 recurrent하다면 Chain을 recurrent하다고 한다.
• 다시말해 transient보다 recurrent가 더 엄격한 기준이 된다.

Positive Recurrent

• $h_{i,i} < \infty$를 만족하면 유한 회귀(Positive Recurrent)라고 한다.
• 그렇지 않다면 무한 회귀(null Recurrent)라고 한다.
• 일반적인 경우에는 유한 회귀를 따르기 때문에 무한 회귀의 예를 들어보겠다. 좋은 예를 들기 위해서 state $i$에 대해서 $\sum_{t\rightarrow\infty}r_{i,i}^t = 1$ 즉 t가 무한대로 가서 recurrent를 만족하는 경우를 생각해본다. step $t$번 만에 자신으로 돌아오는 확률 $r_{i,i}^t$에 step $t$를 곱해주었을 때 상수값이 나오고 이를 무한히 더하는 형태를 생각해 보려고 한다.
• State $i$는 $1\over{i+1}$ 확률로 state 1으로 돌아오고, $i\over{i + 1}$ 확률로 state $i+1$로 이동한다고 하자.
• state 1에서 시작해 t번의 스텝후에 자신에게 돌아오지 않을 확률은 ${1\over 2}\times{2\over 3}\times{3\over 4}\times\cdots\times{t\over {t+1}}={1\over {t+1}}$이 됩니다.
• 즉 t가 무한히 증가한다면 자기 자신에게 돌아오지 않은 확률은 0에 수렴합니다. 따라서 recurrent 성질을 가집니다.
• 이제 자기 자신에게 돌아오는데 몇 번의 스텝이 필요할지 구해보려고 합니다. $r_{i,i}^t=$ $1 \over {t({t + 1})}$이 나오는데 이는 step $t-1$까지는 자신에게 돌아오지 않을 확률 $1\over t$에 step $t$에서 step 1으로 돌아올 확률인 $1\over {t + 1}$을 곱해주어 구합니다.
• $h_{i,i}^t = \sum_{t=1}^\infty t\times r_{i,i}^t$ 식에 대입해주면 $h_{i,i}^t = \sum_{t>=1} {1\over {t + 1}}$로 정의되고 전개해주면 무한대로 발산한다는 것을 알 수 있습니다.

Periodic

• 주기를 갖는(Periodic) 마르코프 체인이란 state $i$에서 출발해서 state $i$로 돌아오는 step이 주기적으로 반복된다는 것이다. 수학적으로는 다음과 같이 정의된다. 만약 state $j$가 $p> 1$를 만족하는 p에 대해서 $s/p = 0$을 만족하지 않는 한 $Pr(X_{t + s} = j | X_{t} = j) = 0$인 p가 존재한다면 periodic이라고 합니다.
• 하나의 state가 Periodic하다면 MC는 Periodic 성질을 가집니다.
• periodic하지 않다면 aperiodic성질을 가집니다.

Ergodic

• 네이버 영어 사전에 따르면 얼고딕이란

  “상당한 기간이 지난 후, 하나의 체계가 최초의 상태와 거의 비슷한 상태로 돌아가는 조건 하에 있는”

• 즉 충분한 시간이 지난후의 MC가 초기 상태의 MC와 거의 비슷하다는 말입니다.

• 정의 : aperiodic이면서 positive recurrent하다면 Ergodic한 성질을 가집니다. 또한 MC가 Ergodic하려면 MC에 있는 모든 상태들이 Ergodic해야 합니다.

• 따름 정리 finite, irreducible, aperiodic 한 MC는 ergodic합니다.

추가 정리

• 모든 finite MC는 두가지 성질을 가집니다.
• 최소한 하나의 state는 recurrent합니다.
• 모든 recurrent state는 positive recurrent합니다.

time reversibiltiy

Stationary

• Stationary는 말 그대로 안정된, 평형을 이룬 상태라고 생각할 수 있습니다.
• 현재 MC의 모든 State의 확률 분포를 $\pi$라고 할 때 상태 이동 벡터 $P$에 대해서 $\pi = \pi P$를 만족할 때 Stationary라고 합니다.
• 상태 이동 벡터$P$는 1이란 시간후에(혹은 1 step후에) State $i$에서 다른 State $j$로 이동할 확률 $P_{i, j}$을 모든 $i$와 $j$에 대해서 대해서 모아놓은 벡터입니다.
• 즉 Stationary 상태가 되면 아무리 많은 시간이 흘러도 계속해서 같은 확률분포를 갖게 됩니다.

정리 1 Any finite, irreducible, ergodic한 MC

• 유일한 상태 확률 분포 $\pi$를 갖습니다.
• 모든 $i, j$에 대해서 $\lim_{t\rightarrow\infty}P_{i,j}$는 항상 0이 아니며 이는 모든 $j$ 에 대해서 해당됩니다.
• $\pi_i = 1/ h_{i,i} = \lim_{t\rightarrow\infty}P_{j,i}^t$
• $h_{i,i}$는 state $i$에서 시작해 $i$로 되돌아올 때까지 걸리는 평균 step 횟수를 말합니다.

따라오는 정리들

유한한 상태를 갖는 MC에 대해서

• 적어도 하나의 state는 recurrent하다.
• 모든 회귀 상태(recurrent state)는 유한 회귀(positive recurrent)하다.

Cut Set

• state $i$ 에서 state $j$로 가는 확률 $P_{i,j}$
• $\pi_{i}$