[Statistics 110] Lecture 32: Markov Chains Continued

Markov Chains States

(2),(3)를 보면 특정 state에서 다른 특정 state로는 절대 갈 수 없다. 이러한 상태를 reducible이라고 하고 (1)번과 같이 그렇지 않은 상태를 irreducible이라고 부른다.

어떤 state에서 다시 해당 state로 돌아오는 확률이 1일 때, recurrent state(재귀 상태)라고 부른다.

→ state 수가 유한하고 irreducible한 마르코프 체인은 모든 state가 recurrent state

recurrent state의 반대 개념은 transient state(일시적 상태) (2)번 예시에서 3에서 6으로 가는 루트가 생긴다면 1,2,3은 transient state.

(3)번 예시에서 0이나 3에 도달하면 그 상태에 영원히 머물게 되는데 이러한 state를 Absorbing state(흡수 상태)라고 부른다. (Gambler’s Ruin에서 파산 상태)

Stationarity

$\vec sQ = \vec s$를 만족하면 Stationary 상태라고 한다.

Irreducible하고 유한개의 recurrent state를 가진 마르코프 체인은

• Stationary state $\vec s$가 항상 유일하게 존재
• $s_i = \frac 1 r_i$를 만족시키는 $r_i$가 존재($r_i$는 $i$에서 다시 $i$로 돌아가는데 걸리는 시간)
  • 마르코프 체인에서 장기간 연쇄가 총 시간의 1/10을 i state에서 머무른다는 것은 곧 i에서 i로 돌아오는데 평균 10 step이 걸린다는 직관
• 어떤 $m$에 대해 $Q^m$의 원소가 모두 양수면 $n \rightarrow \inf$이면 $P(X_n=i) \rightarrow s_i$.
  • 시작점에 상관없이 step이 많아지면 Stationary distribution에 수렴

Reversible Markov Chains

$Q$ 전이행렬을 가지는 마르코프 체인은 모든 상태 i,j에 대해 $s_iq_{ij}=s_jq_{ji}$를 만족하면 reversible하다고 한다.

$\vec s$가 reversible하면 $\vec s$는 stationary

증명)

$$ \sum_i s_iq_{ij} = \sum_i s_jq_{ji} \\ \sum_i s_iq_{ij}= s_j\sum_i q_{ji} = s_j $$

무방향 네트워크 random walk

$d_i$를 $i$ state의 차수(edge 수)라고 하면 $d_iq_{ij}=d_jq_{ji}$를 만족함을 보여라.

undirected이기 때문에 $i\ne j$라면 두 q는 모두 0이거나 0이 아님.

$q_{ij} = \frac 1d_i$이기 때문에 명제의 증명이 되었고 따라서 $\vec s = \frac{d_i}{\sum_jd_j}$인 $\vec s$는 stationary

 

Reference

[0] https://www.youtube.com/playlist?list=PL2SOU6wwxB0uwwH80KTQ6ht66KWxbzTIo