[Markov Chains] 장기 확률 (limiting probabilities, period, ergodic, stationary probability)

Markov Chain and its Stationary Distribution

two-staet Markov chain의 전이확률이 다음과 같다고 하자.

\[P = \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix} \]

이제 \( P^4 \)와 \( P^8 \)을 계산해보면 다음과 같다.

\[ P^4 = \begin{bmatrix} 0.5749 & 0.4251 \\ 0.5668 & 0.4332 \end{bmatrix}, \ P^8 = \begin{bmatrix} 0.572 & 0.428 \\ 0.570 & 0.430 \end{bmatrix} \]

이는 \( P^8 \)이 \( P^4 \)와 거의 동일하다는(identical) 것을 의미한다.

또한, \( P^8 \)의 행(row)들 역시 거의 동일한 값(identical entries)을 가지는 것 처럼 보인다.

 

사실, \( P_{ij}^n \)가 \( n \to \infty \)일 때 어떤 값으로 수렴하는 것처럼 보이며, 이 값은 모든 \( i \)에 대해 동일하다.

즉, 많은 수의 전이를 거친 후 process가 상태 \( j \)에 있을 확률의 극한값이 존재한느 것으로 보이고, 이는 초기 상태와 무관하다. 

이러한 직관을 명확히 하기 전에, 마르코프 체인의 상태와 관련된 두가지 속성을 생각해보자.

 

Period (주기)

상태 \( i \)의 전이확률 \( P_{ii}^n = 0 \)이 되는 모든 \(  n \)에 대하여  \( d \)로 나누어 떨어지지 않을 때마다 성립하고, 이 성질을 가진 \( d \) 중 가장 큰 정수를 period(주기)라고 한다.

※ \( d = \gcd (T(x) ),\ T(x) = \{n \ge 1: P_{ij}^n > 0 \} \) 으로 표기할 수 있다.

\( i \)에서 다시 \( i \)로 돌아오는 시점이 \( 2, 4, 6, 8, \dots, \) 이라면 상태 \( i \)는 주기 \( d=2 \)를 가진다고 한다.

특별히, 주기 \( d=1 \)인 경우 aperiodic(비주기적)이라고 한다.

주기는 클래스 속성이라는 것을 증명할 수 있다. 

즉 \( i \)가 주기 \( d \)를 가지고 \( i \leftrightarrow j\)인 경우, \( j \) 역시 주기가 \( d \)이다.

 

Positive Recurrence (양의 재귀성), Ergodic(에르고딕)

상태 \( i \)가 recurrent일 때, \( i \)에서 시작하여 프로세스가 다시 상태 \( i \)로 돌아오는데 걸리는 시간이 유한하다면, \( i \)는 positive recurrent(양의 재귀)라고 한다. 

recurrent이면서 positive recurrent가 아닌 상태도 존재하지만, 유한 상태 마르코프 체인에서는 모든 재귀상태가 양의 재귀적임을 증명할 수 있다. 

그리고, 양의 재귀적이고 비주기적인 상태는 ergodic(에르고딕)이라고 한다.

 

irreducible ergodic Markov chain(가역 에르고딕 마르코프 체인)에서 \( \lim_{n \to \infty} P_{ij}^n \)의 값은 존재하며 \( i \)에 독립적이다. 또한, 아래와 같이 정의할때,
\[ \pi_j = \lim_{n \to \infty} P_{ij}^n,\ j \ge 0 \]
\( \pi_j \)는 다음 방적식을 만족하는 유일하고(unique) 음이 아닌 해(nonnegative solution)이다.
\[ \pi_j = \sum_{i=0}^{\infty}\pi_i P_{ij},\ j \ge 0, \quad \sum_{j=0}^{\infty}\pi_j = 1 \]

 

Example

날씨를 two-state Markov chain으로 정의한 경우를 생각해보자.

\( \alpha \)는 오늘 비가 왔을 때, 내일도 비가 올 확률이고, \( \beta \)는 오늘 비가 오지 않았을 때, 내일 비가 올 확률이다. 

즉 비가오는 상태를 0, 비가 오지 않은 상태를 1이라 하면 전이확률은 다음과 같다.

\[ P = \begin{bmatrix} \alpha & 1 - \alpha \\ \beta & 1 - \beta \end{bmatrix} \]

이제 각 row의 확률의 극한값을 각각 \( \pi_0,\ \pi_1 \)이라 하자.

그러면 다음의 연립방정식을 풀면 된다.

\begin{align} \pi_0 &= \alpha \pi_0 + \beta\pi_1 \\ \pi_1 &=(1-\alpha)\pi_0 + (1-\beta)\pi_1 \\ \pi_0 + \pi_1 &= 1 \end{align}

연립방정식의 해는 다음과 같다.

\[ \pi_0 = \cfrac{\beta}{1 - \alpha + \beta},\ \pi_1 = \cfrac{1 - \alpha}{1 - \alpha + \beta} \]

\( \alpha = 0.7\)이고 \( \beta = 0.4 \)이므로 대입하면 \( \pi_0 = 4/7,\ \pi_2 = 3/7 \) 이다.

 

장기적으로 비율 \( \pi_j \)는 종종 stationary probability(정상 확률)이라 한다.

이는 초기 상태가 \( \pi_j \)에 따라 선택되었다면, 시간 \( n \)에서 상태  \( j \)에 있을 확률 또한 항상 \( \pi_j \)와 같기 때문이다.

그러므로 다음이 성립한다.

\( P(X_0 = j) = \pi_j \)이면, 모든 \(n, j \ge 0 \)에 대하여 \( P(X_n = j) = \pi_j \) 이다.

 

수학적 귀납법으로 증명할 수 있다.

\( n - 1 \)에 대해 성립한다고 하면 다음과 같은데, 

\begin{align} P(X_n = j) &= \sum_{i} P(X_n = j \mid X_{n-1} = i) P(X_{n-1} = i) \\ &= \sum_{ij}P_{ij} \pi_i \\ &= \pi_j \end{align}

 

\( \{X_n, n \ge 1 \}  \)가 irreducible Markov chain with stationary probabilies \( \pi_j \)를 가진다고 하자. 그리고 state space에서 정의된 \( r \)이 유계함수(bounded function)이라면, 확률 1로 다음이 성립한다.
\[ \lim_{N \to \infty} \frac{\sum_{n=1}^{N}r(X_n)}{N} = \sum_{j}^{\infty}r(j)\pi_j \]

 

proof)

시간 \( 1, 2, \dots, N \)동안 마르코프 체인이 상태 \( j \)에 머문 시간을 \( a_j(N) \)이라 하자.

그러면 다음이 성립한다

\[ \sum_{n=1}^{N} r(X_n) = \sum_{j=0}^{\infty}a_j(N)r(j) \]

그리고 \( \frac{a_j(N)}{N} \to \pi_j \)임을 이용하여 증명한다.

 

interpretation(해석)

위 식은 다음의 뜻을 가진다.

마르코프 체인이 상태 \( j \)에 있을 때마다 보상을 \( r(j) \)만큼 받는다고 하면, 단위 시간당 평균 보상이 \( \sum_{j}r(j)\pi_j \)라는 뜻이다.

 

Example

한 사용자가 특정 3개의 웹사이트 A, B, C를 방문한다고 하자.

사용자의 행동은 마르코프 체인으로 모델링되고, 다음과 같이 상태전이확률이 주어진다.

(0:A, 1:B, 2:C)

\[ P = \begin{bmatrix} 0.2 & 0.5 & 0.3 \\ 0.1 & 0.4 & 0.5 \\ 0.3 & 0.3 & 0.4 \end{bmatrix} \]

그리고 각 페이지를 방문할 때마다 다음의 수익이 주어진다고 하자.

\[ r(A)=10,\ r(B) = 5,\ r(C) = 2 \]

이때, 장기적으로 단위시간당 평균수익을 구해보자.

 

먼저, 정상확률 \( \pi \)를 구하자.

\begin{align} \pi_A &= 0.2 \pi_A + 0.1\pi_B + 0.3\pi_C \\ \pi_B &= 0.5\pi_A + 0.4\pi_B + 0.3\pi_C \\ \pi_C &= 0.3\pi_A + 0.5\pi_B + 0.4 \pi_C \\ \pi_A + \pi_B + \pi_C &= 1 \end{align}

 

이를 풀면

\[ \pi = [0.2039,\ 0.3786,\ 0.4175] \]

따라서 단위시간당 평균 수익은 \( 4.77 \) 이다.

 

Matrix form and Computation

\( n \)개의 상태를 가지는 유한 상태 마르코프 체인의 정상 분포를 \( pi \)라 하면, 다음 방정식을 만족하는 확률분포이다.

\[ \pi P = \pi \]

여기서 \( P \)는 \( n \times n \) 상태 전이 행렬, \( \pi = [\pi_1,\ \pi_2, \ \dots, \pi_n] \)는 정상확률을 나타내는 행벡터(row vector) 이다.

 

이를 다시 작성하면

\[ \pi (P - I) = 0 \]

이다. \( I \)는 \( n \times n \) 단위 행렬이다.

row vecor 대신에 column vector로 나타내면

\[ (P^T - I)\pi^T = 0 \]

이고, \( n \)개의 상태에 대해 \( n \)개의 방정식을 가지는 동차 연립방정식이다.

 

한편, 정상 분포는 확률분포이므로 \( \sum_{i=1}^{n} \pi_i = 1 \) 을 만족해야한다.

그리고 기존 방정식 중 하나는 종속이므로, 하나를 제거해도 시스템 정보가 손실되지 않는다.

직관적으로 각 전이확률의 합이 1이므로, \( P \)는 선형종속이다.

(행렬 \( P^T - I \)의 모든 행의 합이 0이므로, 한 행은 나머지 \( n - 1\)개의 행으로 표현 가능하다. 따라서 rank=\(n-1\)이다.)

따라서 행렬 \( P^T - I \)의 마지막 행을 \( [1, 1, \dots, 1] \)로 대체한다.

그리고 \( b = [0, 0, \dots, 0, 1] \)로 설정하여 정규화 조건을 반영한다.

수정된 방정식은 다음과 같다.

\[ A \pi^T = b \]

따라서 정상분포는 

\[ \pi^T = A^{-1}b \]

이다.

※ 당연히, \( P \)는 irreducible ergodic Markov chain의 상태전이확률이어야 한다.