Summary

• First Step Analysis란 Markov Chain을 해결하기 위한 간단한 방법
• Markov Property를  이용해서 변수들의 특성을 빠르게 파악하는 방법

Prerequisite

• Absorbtion, Transition  개념 이해 필요함.
• Absorbtion  Status에 들어가게 되면 그 이후로는 이제 Status가 변하지 않는다.

Example

• 다음과 같은 전이행렬이 있따고 가정할 때 Absorbtion Status에 도달하기까지의 시간과 확률, 그리고 평균 기대시간을 구한다고 가정하다.

$$ \left[ \begin{array}{cc} 1 & 0 & 0 \\ P_{10} & P_{11} & P_{12} \\ 0 & 0 & 1 \end{array} \right] $$

식은 다음과 같이 정리할 수 있다.
$$T={n \ge 0 : X_n = 0 or X_n =2 }$$
$$U=P(X_T = 0 | X_0 = 1)$$
$$V=E[T|X_0=1]$$

각각 뜻을 보면 $T$는 $X$가 0 또는 2에 도달하는 상황까지 걸리는 시점, 즉 시간을 의미하고 $U$는 $X_0$시점에 1에서 시작했을 $T$시점에 0에 도달할 확률을 의미한다. 그리고 $V$는$X_0$에서 시작할 때 $T$의 평균 기대시간을 의미한다.

이 때   $U$는  $P_{10} \times 1 + P_{11} \times U + P_{12}\times 0$으로 계싼해볼 수 있다. $P_{10}$ 시점에 0으로 갈 경우 Absorbtion 되는 확률은 1이기 때문에 1이라고 하였고 $P_{11}$의 경우 원위치이기 때문에 확률은 $U$이며 $P_{12}$ 의 경우 2로 Absorbtion이 되었기 때문에 0에 도달할 확률은 0이 되고 이를 바탕으로 U를 정리하면 다음과 같이 식을 쓸 수 있다.
$$U ={{P_{10}} \over{1-P_{11}}} = {{P_{10}} \over {P_{10} + P_{12}}}$$

$V$도 비슷한 형태로 정리해보면 $V=1+P_{10}\times0 + P_{11} \times V + P_{12} \times 0$ 으로 볼 수 있고 이는 처음에 State 1에서 어떤 지점으로 갈지를 모르기 떄문에 이 부분에 대해서는 동일한 Probability로 간주하되 $P_{11}$은 원위치로 돌아오는 것이기 때문에 기댓값은 재귀형태로 V일 것이고 $P_{12}$는 현재 0으로 가는 것을 간주하고 있기 때문에 확률을 0으로 처리한다. 이를 V기준으로 정리하면 다음과 같다.
$$V = {{1} \over {1-P_{11}}}$$

이 때 Eacth Step은 모두 베르누이 시행으로 간주할 수 있다. 즉 Absorbtion을 성공으로 보고 나머지를 모두 실패로 보는 것이다. 그리고 이렇게 본다고 하면 Each Stepd에서 성공확률은 $1-P_{11}$이 되고 $V$, 즉 평균 기대값은 Absorbtion의 관점에서 기하분포형태로 움직이는 Random Variable이라고 볼 수 있다

References

• Introductory examples on first step analysis