# 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}$

<!--stackedit_data:
eyJoaXN0b3J5IjpbLTE5MTQyMzc0NzIsMTQxMDY5NDQ0LDE3OT
A5NDQ2NDcsMTg3MjEwMzU0MCwtNDcwMjQ1OTU1XX0=
-->