Markov Chain Applications

○The Gambler's Ruin Problem

 ▷Gambler와 Casino의 확률 계산

 

 ▶규칙

  ▷Gambler의 돈 i, Casino의 자산 N

  ▷Gambler의 승 (p): i+1 / Casino의 승 (1-p=q): i-1

  ▷Gambler의 돈이 0이 되거나 N이 되면 게임을 더 이상 진행할 수 없음. (1의 확률로 loop)

 

 ▶확률

  ▷P_i = pPi+1 + qPi-1

   ▷P_i+1 - P_i = q/p (P_i - P_i-1)

   ▷P₀ = 0

  ▷등비수열의 합 공식( a(rⁿ) / (r-1) )에 의해 다음과 같이 정리 가능하다.

 

○Mean Time Spent in Transient State

 ▷Transient State에서 머무는 시간

 

 ▶s_ij : State i 에서 시작해서, j에서 머무는 평균 시간

  ▷P_T : Transition -> Transition State으로 이동하는 확률들

  ▷δ_i,j = 1 (i = j) / δ_i,j = 0 (i ≠ j) - 처음에 있는 1번 계산

  ▷S_ij = δ_i,j + Σ_k (P_ik s_kj)

   ▷이를 Martix 계산으로 풀면 다음과 같다.

 

 

 

○Time Reversible Markov Chains

 ▷| (i -> i+1로의 transition 수) - (i+1 -> i로의 transition 수)| ≤ 1