[Markov Chains] Chapman-Kolmogorov Equations (체프만-콜모고로프 방정식)

Chapman-Kolmogorov Equation: Transition Rules for Stochastic Processes

앞서 one-step transition probability \( P_{ij} \)을 정의했다.

이제 일반화하여 \( n \)-step transition probability(n단계 전이확률)를 \( P_{ij}^n \)로 표기하고 정의할 것이다.

state \( i \)에서 \( n \)번의 추가 전이를 거쳐 state \( j  \)에 있을 확률을 \( P_{ij}^n \)로 정의한다. 즉,

\[ P_{ij}^n = P(X_{n+k} = j \mid X_k = i), \quad n \ge 0,\ i,j \ge 0 \]

당연히 \( n=1 \)인 경우에는 \( P_{ij}^1 = P_{ij} \) 이다.

위 방정식은 다음과 같이 확장할 수 있다.

\[ P_{ij}^{n+m} = \sum_{k=0}^{\infty} P_{ik}^n P_{kj}^m, \quad n, m \ge 0 \]

이는 상태 \( i \)에서 \( n + m \)번의 전이를 거쳐 상태 \( j \)로 도달할 확률이다. 

이때 \( n \)번째 전이상태인 \( k \)를 거치는 경우를 고려한다.

따라서 모든 중간 상태 \( k \)에 대해 합산하면 \( n + m \)번의 전이를 거쳐 \( j \)가 될 확률을 얻을 수 있다.

 

\begin{align} P_{ij}^{n+m} &= P(X_{n+m} = j \mid X_0 = i)  \\ &= \sum_{k=0}^{\infty}P(X_{n+m} = j, X_n = k \mid X_0 = i) \\ &= \sum_{k=0}^{\infty}P(X_{n+m}=j \mid X_n = k, X_0 = i) P(X_n = k \mid X_0 = i) \\ &= \sum_{k=0}^{\infty}P_{kj}^m P_{ik}^n \end{align}

\( P^{(n)} \)를 n-step 전이확률 \( P_{ij}^n \)의 행렬이라 하자. 그러며 위 식에 따라

\[ P^{(n+m)} = P^{(n)} P^{(m)} \]

특히, \( P^{(2)} = P^{(1 + 1)} = P \cdot P = P^2 \)이고

induction으로 \( P^{(n)} = P^{(n-1 + 1)} = P^{(n-1)} \cdot P = P^n \)

를 유도할 수 있다.

Example 1

주머니에는 항상 공이 2개 있자. 공의 색깔은 빨간색과 파란색이다. 각 단계에서 공 하나를 무작위로 선택한 후, 새 공으로 바꾼다. 새 공이 바뀐공(원래 공)과 같은 색일 확률이 0.8이고, 반대 색일 확률이 0.2이다. 맨 처음 주머니에는 두개의 빨간공이 있을 때, 다섯번째로 선택된 공이(교체된 공이 아님) 빨간색일 확률은?

 

solution)

주머니에 존재하는 공들의 상태는 (R, R), (R, B), (B, B) 이렇게 3가지가 가능하다. 

\( X_n \)을 \( n \)번째 단계에서 (새 공으로 바꾸기 전) 빨간공의 개수라 하자.

그러면 초기 상태는 \( X_0 = 2 \) 이다.

 

(R, R)에서 빨간공을 선택할 확률은 1이고, 새 공이 빨강/파랑일 확률은 각각 0.8, 0.2이다. 

마찬가지로 (B, B)에서 파란공을 선택할 확률은 1이고, 새 공이 빨강/파랑일 확률은 0.2, 0.8이다.

(R, R)에서 (B, B) 또는 (B, B)에서 (R, R)로 가는 경우는 없으므로 확률이 0이다.

(R, B)에서 전이될 수 있는 상태는 (R, R), (R, B), (B, B) 세가지이다.

(R, B)에서 (R, R)이 되려면 파란공을 선택하고, 새 공이 빨간색(반대되는 색)이므로 (0.5)(0.2) = 0.1

(R, B)에서 (B, B)가 되려면 빨간공을 선택하고, 새 공이 파란색(반대되는 색)이므로 (0.5)(0.2) = 0.1

(R, B)에서 (R, B)가 되려면 빨간공을 선택하고 새 공이 빨간색인 경우와, 파란공을 선택하고 새 공이 파란색인 경우의 합이므로 (0.5)(0.8) + (0.5)(0.8) = 0.8 (여사건으로도 구할 수 있다.)

따라서 전이확률은

\[ P = \begin{bmatrix} 0.8 & 0.2 & 0 \\ 0.1 & 0.8 & 0.1 \\ 0 & 0.2 & 0.8 \end{bmatrix} \]

(상태 \( i \)를 주머니 속의 빨간공의 개수로 정의한다.)

 

5번째 공을 선택했을 때(새 공으로 교체 하기 전) 빨간색일 확률을 구하려면, 4번째 단계의 모든 상태에서 빨간공이 선택될 확률을 더하면 된다.

\[ P^4 = \begin{bmatrix} 0.4872 & 0.4352 & 0776 \\ 0.2176 & 0.5648 & 0.2176 \\ 0776 & 0.4352 & 0.4872 \end{bmatrix}  \]

 

\( X_0 = 2 \)이므로 \( P^4 \)의 2번째 row인 \( [0.0776,\ 0.4352,\ 0.4852] \)에 주목한다.

상태 \( i \)에서 빨간공을 선택할 확률은 각각 \( 0, 0.5, 1 \)이므로 (\( i=0, 1, 2 \))

정답은 \( (0)(0.0776) + (0.5)(0.4352) + (1)(0.4852) = 0.7048 \)

따라서 5번째 단계에서 빨간공을 선택할 확률은 0.7048(약 70%)이다.

 

Example 2

8개의 항아리(urn)에 9개의 공을 순차적으로 한 개씩 분배한다고 하자. 각 공이 항아리중 하나에 동일할 확률로 들어간다. 9개의 공이 모두 분배된 후, 정확히 3개의 항아리만 비어있지 않을 확률은?

 

solution)

\( X_n \)을 \( n \)개의 공이 분배된 후 비어있지 않은 항아리의 개수라고 하자. 

그러면 상태는 \( i = 0, 1, \dots, 8 \)인 마르로프 체인이 되고, 가능한 전이확률은 \( P_{i,i} = i/8 \)이고 \( P_{i, i+1} = 1 - i/8 \)이다. 즉

\[ P_{i,i} = i / 8 = 1 - P_{i, i+ 1} \]

우리가 구하고자 하는 확률은 \( P^9_{0, 3} \)이고, \( P_{0, 1} = 1 \)이므로 \( P^9_{0,3} = P^8_{1, 3} \)과 같다.

또한, 3개의 항아리가 차 있느 경우만 필요하기 때문에 상태 \( i=4, 5, 6, 7, 8 \)을 하나의 상태로 합쳐서 간주할 수 있다. 

그러므로 상태 \( 1, 2, 3, 4 \)를 가진 마르코프 체인의 전이확률은 다음과 같다.

\begin{bmatrix} 1/8 & 7/8 & 0 & 0 \\ 0 & 2/8 & 6/8 & 0 \\ 0 & 0 & 3/8 & 5/8 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}

\( P^2 = P \cdot P \)이고,  \( P^4 = P^2 \cdot P^2 \)이므로

\[ P^4 = \begin{bmatrix} 0.0002 & 0.0256 & 0.2563 & 0.7178 \\ 0 & 0.0039 & 0.0952 & 0.9009 \\ 0 & 0 & 0.0198 & 0.9802 \\ 0 & 0 & 0 & 1 \end{bmatrix} \]

따라서 \( P^8_{1,3} \)은 \( P^4 \)의 \( 1 \)번 row와 \( 3 \)번 column의 곱셈이므로

\[ P_{1,3}^8 = (0.0002)(0.2563) + (0.0256)(0.0952) + (0.2563)(0.0198) + (0.7178)(0) = 0.00756 \]

 

Unconditional Distribution (무조건부 확률)

\( P^n_{ij} \)는 초기 상태(시간 \(n = 0\))는 \( i \)일때  시간 \( n \)에 상태가 \( j \)일 확률이다. 이는 마르코프체인에서 기본적으로 고려하는 확률이다.

만약, 초기 상태(initial state)가 주어지지않은 상태에서 시간 \( n \)에 상태가 \( j \)일 확률을 구해보자.

그럴려면 초기 상태 분포 \( \alpha_i \equiv P(X_0 = i) \)를 정의해야한다.

초기 상태 분포는 모든 상태 \( i \)에서 확률의 합이 1이 되어야하므로 \( \sum_{i=0}^{\infty} \alpha_i = 1 \) 이다.

무조건부확률(unconditional probability)는 초기 상태 분포의 조건부 확률의 합이다. 즉

\[ P(X_n = j) = \sum_{i=0}^{\infty}P(X_n=j \mid X_0=i) P(X_0=i) = \sum_{i=0}^{\infty}P_{ij}^n \alpha_i \]

 

\( \mathcal{A} \)를 상태들의 집합(a set of states)이라 하고, 마르코프 체인이 시간 \( m \) 안에 한번이라도 도달할 확률을 계산해보자.

상태 \( i \notin \mathcal{A} \)가 주어질 때, 우리는 다음의 확률 \( \beta \)을 구하고자 한다.

\[ \beta = P(X_k \in \mathcal{A} \text{ for some } k = 1, \dots, m \mid X_0 = i) \]

이 확률을 구하기 위해 새로운 마르코프 체인 \( \{ W_n, n \ge 0 \} \)을 도입한다.

이 새 마르코프 체인의 상태는 \( \mathcal{A} \)에 있는 상태와 추가적인 상태(additional states; 실제 예제에서는 다른 이름을 이용하지만 여기서는 A라고 하겠다) 이렇게 2개가 존재한다.

\( N \)을 마르코프체인 \( \{ X_n \} \)이 처음으로 어떤 상태집합 \( \mathcal{A} \)에 도달하는 시간이라 하자. 즉

\[ N = \begin{cases} \min \{n: X_n \in \mathcal{A} \} \\ \infty ( X_n \notin \mathcal{A} \text{ for all } n ) \end{cases} \]

 

새로운 마르코프 체인의 상태는 원래상태를 유지하는 \( X_n \)과 \( A \)에 도달 후 계속 \( A \)로 전환 및 유지하는 경우로 나뉜다. 즉,

\[ W_n = \begin{cases} X_n, & \text{if } n < N \\ A, & \text{if } n \ge N \end{cases} \]

 

이제, 새로운 마르코프 체인의 전이확률을 \( Q \)라 하면 다음과 같다.

\( Q_{i,j} = P_{i,j} \) if \( i \notin \mathcal{A},\ j \notin \mathcal{A} \) (기존 체인의 전이확률 그대로 이용)

\( Q_{i, A} = \sum_{j \in \mathcal{A}} P_{i,j} \) if \( i \notin \mathcal{A} \) (상태 \( i \)에서 \( \mathcal{A} \)의 모든 상태로 전이될 확률의 합 )

\( Q_{A, A} = 1 \) (상태 \( A \)에서는 스스로 전이)

원래의 마르코프 체인이 시간이 \( m \)일때 까지 \( \mathcal{A} \)에 진입한다는 것은, 새로운 마르코프 체인에서 시간 \( m \)일때 상태가 \( A \)이므로, 다음과 같다.

\begin{align} P(X_k \in \mathcal{A} \text{ for some }k=1, \dots, m \mid X_0 = i ) \\ = P(W_m=A \mid X_0=i) = P(W_m=A \mid W_0 = i) = Q_{i, A}^m \end{align}