마르코브 체인(MC)은 여러 개의 state들의 연결관계로 이루어진 그래프이다. MC의 state의 개수는 유한할 수도 있고 무한할 수도 있다.
Markov chain의 여러가지 상태의 정의에 대해서 알아보자. state란 다음 두 가지 의미 모두 쓰여 햇갈릴 수도 있다.
- Markov chain의 가장 작은 구성 요소이다. state
$i$ 는 그래프의 하나의 노드로 생각하면 된다. - state와 chain의 상태를 다룬다. 다음에 배울 Communicate는 state
$i$ 와$j$ 간의 상태를 의미하기도 하며 chain의 상태를 의미하기도 한다.
- state
$i$ 는 state$j$ 에 대해서 accessible : if 어떤 양수$n$ 에 대해서$P_{i, j}^n > 0$ 을 만족한다 - state
$i$ 가 state$j$ 에 대해서 accessible하고 state$j$ 가 state$i$ 에 대해서 accessible하다면 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은 "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라는 개념을 알아보기 전에 한가지 개념에 대해서 소개하려고 한다.
- 만약
$i$ 에서 출발해서$i$ 로 돌아오는 확률을 모두 합해도 1보다 작다면 즉$\sum_{t>=1}r_{i,i}^t < 1$ 을 만족할 때 state$i$ 는 transient하다고 한다. - Markov Chain에서 단 하나의 state라도 transient하다면 Chain을 transient하다고 한다.
- 만약
$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가 더 엄격한 기준이 된다.
-
$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) 마르코프 체인이란 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성질을 가집니다.
-
네이버 영어 사전에 따르면 얼고딕이란
"상당한 기간이 지난 후, 하나의 체계가 최초의 상태와 거의 비슷한 상태로 돌아가는 조건 하에 있는"
-
즉 충분한 시간이 지난후의 MC가 초기 상태의 MC와 거의 비슷하다는 말입니다.
-
정의 : aperiodic이면서 positive recurrent하다면 Ergodic한 성질을 가집니다. 또한 MC가 Ergodic하려면 MC에 있는 모든 상태들이 Ergodic해야 합니다.
-
따름 정리 finite, irreducible, aperiodic 한 MC는 ergodic합니다.
- 모든 finite MC는 두가지 성질을 가집니다.
- 최소한 하나의 state는 recurrent합니다.
- 모든 recurrent state는 positive recurrent합니다.
- Stationary는 말 그대로 안정된, 평형을 이룬 상태라고 생각할 수 있습니다.
- 현재 MC의 모든 State의 확률 분포를
$\pi$ 라고 할 때 상태 이동 벡터$P$ 에 대해서$\pi = \pi P$ 를 만족할 때 Stationary라고 합니다. - 상태 이동 벡터$P$는 1이란 시간후에(혹은 1 step후에) State
$i$ 에서 다른 State$j$ 로 이동할 확률$P_{i, j}$ 을 모든$i$ 와$j$ 에 대해서 대해서 모아놓은 벡터입니다. - 즉 Stationary 상태가 되면 아무리 많은 시간이 흘러도 계속해서 같은 확률분포를 갖게 됩니다.
- 유일한 상태 확률 분포
$\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 횟수를 말합니다.
- 적어도 하나의 state는 recurrent하다.
- 모든 회귀 상태(recurrent state)는 유한 회귀(positive recurrent)하다.
- state
$i$ 에서 state$j$ 로 가는 확률$P_{i,j}$ $\pi_{i}$