32. 마코프 체인_2(Markov Chains Continued)

본 글은 Havard University Statistics 110 강의를 듣고 정리한 내용입니다.

• 마코프 체인은 어떤 상태에서든 유한한 단계를 거쳐 다른 상태로 가는 것이 가능(확률 > 0)할 때, Irreducible이라고 한다. (from anywhere to anywhere)
• 재귀상태(recurrent state)는 어떤 상태에서 시작해서 그 상태로 돌아올 확률이 1인 경우를 말한다.
• 상태의 수가 유한한 irreducible한 마코프 체인은 모든 상태가 재귀적이다.

1. irreducible, 모든 상태는 recurrent하다
2. reducible하지만, 1-2-3과 4-5-6을 각각 irreducible한 체인으로 볼 수 있다.
   1. 3에서 6으로 가는 길을 만들게 되면 1-2-3은 일시적이고(transient) 4-5-6은 재귀적(recurrent)하다
3. 0이나 3으로 가면 평생 머물게 된다(흡수 상태) 1, 2는 일시적, 0, 3은 재귀적.
   1. 도박꾼의 파산문제를 마코프 체인 형채로 표현
4. 주기적 연쇄

정상분포(Stationarity Distribution)

defn) 확률벡터 ​s​⃗​​ 는 ​s​⃗​​Q=​s​⃗​​ 를 만족할 때 정상(stationary)인 상태라고 한다.

Thm) irreducible하고 유한한 갯수의 마코프 체인은

1. 정상분포가 존재한다.
2. 정상분포가 유일하게 존재한다.
3. s_i = 1/r_i 만족시키는 r_i가 존재한다.(r_i는 i에서 시작했을 때, i까지 돌아가는데 걸리는 평균 시간)
   1. 장기적 연쇄가 1/10 이라는 것은 다시 돌아오는데 평균 10단계가 걸린다는 것을 의미한다.
4. 주기성이 없는 경우 가정. 만약 Q^m 이 어떤 m에 대해서 모든 원소가 양수인 행렬일 때, n이 무한으로 갈 때, 

\[P(X_n=i)\rightarrow s_i\]

 

확률분포  X에 대한 PMF는 s_i에 수렴한다.

 ⇔ 모든 확률벡터  ​t​⃗​​ 에 대하여t​⃗​​ Q​n​​→​s​⃗​​ 를 만족한다. (t는 어떠한 확률분포여도 상관없다)

가역 마코프 체인

defn) 전이행렬 Q = (q_ij)를 가지는 마코프 연쇄가 있을 때, 모든 i, j에 대하여 아래 식을 만족하면 가역적( reversible)이라고 한다.

\[ s_iq_{ij} = s_jq_{ji}\]

Thm) s​⃗​ 에 에 대하여 가역적일 때, s​⃗​​ 는 정상분포를 따른다.

증명)

모든  i, j에 대해

\[ s_iq_{ij} = s_jq_{ji}\]

가 성립할 때, 

\[ \sum_{i}^{}s_iq_{ij} = \sum_{i}^{}s_jq_{ji} = s_j\sum_{i}^{}q_{ji} = s_j\]

∵ Q의 한 행의 합은 1이기 때문이다.

\[ \therefore \vec{s}Q = \vec{s}\]

Random Walk on an Undirected

무방향 네트워크 random walk

d_i : i의 degree라고 했을 때, (d1 =2, d2 = 2, d3 = 3, d4 =1) 
\[ d_iq_{ij} = d_jq_{ji}\]
증명) i와 j가 같지 않을 때, q_ij와 q_ji는 둘다 0이거나 둘다 0이 아니다.
둘다 0인 경우, 등식은 성립

둘다 0이 아닌 경우, 모서리 {i, j}가 존재할 때, \[  q_{ij} = \frac{1}{d_i}\]

위 식에 의해 양변이 1이되어 등식이 성립한다.
1, 2, ..., M의 꼭짓점들과 degree di가 있을 때, \[\vec{s} = \frac{d_i}{\sum_{j}d_j}\]
위 식의 s​⃗​ 에 는 stationary하다.

출처: https://www.edwith.org/ai152