이제 확장된 추이확률에 대해 생각해보자.
n-step 추이확률
-
지금까지의 추이확률은 1개의 상태 간 확률을 나타냈다.
-
이제 n개의 상태를 건너뛰었을 때의 추이확률을 생각해보자.
가령 X_t = a일 떄, X_{t+n} = b일 확률을 얼마인가?
\begin{align*}
P_{xy} &= P(X_1 = y~|~X_0 = x)
\\[10pt]
P_{xy}(s) &= P(X_1 = y~|~X_0 = x)
\\[10pt]
f_{xy}(s) &=
P(X_1 \neq y, \cdots,
X_{s-1} \neq y,~X_s = y~|~X_0 = x)
\end{align*}
- P_{xy} : 상태 x에서 1번만에 상태 y로 갈 확률
- P_{xy}(s) : 상태 x에서 s번만에 상태 y로 갈 확률
- f_{xy}(s) : 상태 x에서 처음으로 s번만에 상태 y로 갈 확률
이 중에서 f_{xy}(s)를 유심히 살펴보자.
\begin{align*}
f_{xy}(m) &=
P(X_1 \neq y, \cdots,
X_{m-1} \neq y,~X_m = y~|~X_0 = x)
\\[10pt]
f_{xy}(1) &= P(X_1 = y~|~X_0 = x) = P_{xy}(1)
\\[10pt]
f_{xy}(2) &= P(X_1 \neq y,
X_2 = y~|~X_0 = x)
\end{align*}
잘 보면 결국 추이확률의 분해가 가능하다는 것을 볼 수 있다.
이를 공식화한 것이 바로 채프만-콜모고로프 방정식이다.
채프만-콜로고로프 방정식
\sum_{k \neq j} P_{ij}(n) =
P_{ik}(n)P_{kj}(k-n)
\begin{align*}
f_{xy}(k) &= \sum_{k \neq j}
~P_{ik}(1)~f_{kj}(n) \\[15pt]
\end{align*}
f_{ij}(m) =
P_{ij}(m) - \sum_{k=1}^{m-1}
f_{ij}(m-k)~P_{jj}(k)~I(m \le 2)
행렬로 표현하면 다음과 같다.
\underline{P}^{m} =
\sum_{k=1}^{n}~F(k)
~D(\underline{P}^{m-k})
재귀와 평균도달시간
확장된 추이확률을 이용해 다시 원래의 상태로 돌아가는 것을 생각해보자.
가령 X_t = a일 떄 X_{t+n} = a일 확률, n번만에 집에 갈 확률은 얼마인가?
{f_{ii}}^{*} = \sum_{m=0}^{\infty}~f_{ii}(m)
- {f_{ii}}^{*} = 상태 i에 1~m번만에 도달 = 상태 i에 최소 1번은 도달
- {({f_{ii}}^{*})}^2 = 상태 i에 최소 2회 도달
{({f_{ii}}^{*})}^2 =
{f_{ii}}^{*}~
\sum_{k=1}^{\infty} f_{11}(k)
- {({f_{ii}}^{*})}^k = 상태 i에 최소 k회 도달
k에 극한을 취한 경우 다음과 같이 쓰기도 한다.
\lim\limits_{k \to \infty}{({f_{ii}}^{*})}^k =
I({f_{ii}}^{*} = 1)
이는 상태 i에 무한 번 도달함을 의미한다.
- f_{ij}