행렬 응용 : Markov Chain(2) - Stationary Distribution

이제, long-term 상황에서의 Markov Chain의 형태를 살펴보고자 한다. 특히, $n$이 커짐에 따라 Markov Chain이 각 상태(state)에서 보내는 시간의 비율을 알고자 한다. 보다 구체적으로, 다음과 같은 분포를 살펴보고자 한다.
$$ \pi^{(n)} = \begin{bmatrix} P(X_n = 0) & P(X_n = 1) & \cdots & \end{bmatrix} \quad as \,\,\, n \rightarrow \infty $$. 본 주제에 대해 더 잘 이해하기 위해, 예시를 먼저 살펴보고 이를 general case로 확대해보고자 한다. 

 

• 2개의 가능한 State, $S = \{0, 1\}$을 갖는 Markov Chain을 고려하자. Transition Matrix는 $P = \begin{bmatrix} 1-a & a \\ b & 1-b \end{bmatrix}$라고 가정한다. 이때, $a$와 $b$는 $0< a+b < 2$를 만족하는 $[0, 1]$ 구간 사이의 실수이다. System이 $\alpha$의 확률로 time $n=0$에서 state 0에 있다고 하자. 즉, 
  $$
  \pi^{(0)} = \begin{bmatrix} P(X_0 = 0) & P(X_0 = 1) \end{bmatrix} = \begin{bmatrix} \alpha & 1-\alpha \end{bmatrix} \quad \textrm{where} \,\, \alpha \in [0, 1].
  $$ 이제 아래의 과정을 통해 Limiting Distribution을 얻을 수 있다. 
  
  • (1) $$
    P^n = \frac{1}{a+b} \begin{bmatrix} b & a \\ b & a \end{bmatrix} + \frac{(1-a-b)^n}{a+b}\begin{bmatrix} a & -a \\ -b & b \end{bmatrix}
    $$
  • (2) $$
    \lim_{n\rightarrow \infty} P^n = \frac{1}{a+b} \begin{bmatrix} b & a \\ b & a \end{bmatrix}.
    $$ Since by the assumption $0 < a + b < 2$, it implies $-1 < 1-a-b < 1$. Thus, $\lim_{n \rightarrow \infty} (1-a-b)^n = 0$.
  • (3) $$
    \lim_{n\rightarrow \infty} \pi^{(n)} = \begin{bmatrix} \frac{b}{a+b} & \frac{a}{a+b} \end{bmatrix}
    $$ Since $\lim_{n\rightarrow \infty} \pi^{(n)} = \lim_{n\rightarrow \infty} [\pi^{(0)} P^n] = \pi^{(0)} \lim_{n\rightarrow \infty} P^n$.
  • 본 예제에서, $$
    \lim_{n\rightarrow \infty} \pi^{(n)} = \begin{bmatrix} \frac{b}{a+b} & \frac{a}{a+b} \end{bmatrix}
    $$가 Markov Chain의 limiting distribution이다. 보이는 바와 같이, limiting distribution은 초기 확률 $\alpha$ 혹은 $1-\alpha$에 의존하지 않는다. 즉, 다시말해 초기 상태 $X_0$은 $n$이 커짐에 따라 영향을 주지 않는다는 것이다. 
  • 따라서, $i= 1, 2$에 대해 아래와 같이 표현할 수 있다. $$
    \begin{aligned} \lim_{n\rightarrow \infty} P(X_n = 0 | X_0 = i) &= \frac{b}{a+b} \\
    \lim_{n\rightarrow \infty} P(X_n = 1 | X_0 = i) &= \frac{a}{a+b}
    \end{aligned}
    $$

▶ Limiting Distribution(극한분포) and Stationary Distribution(정상분포)

• Def : The probability distribution $\boldsymbol{\pi} = [\pi_0, \pi_1, \pi_2, \cdots]$ is called the limiting distribution of the Markov Chain $X_n$ if $$
  \begin{aligned}
  \pi_j = \lim_{n \rightarrow \infty} P(&X_n = j|X_0 = i) = \lim_{n \rightarrow \infty} p_{ij}^{(n)} \quad \textrm{for all  } i, j \in S, \\ \textrm{and we have } &\sum_{j \in S} \pi_j = 1.
  \end{aligned}
  $$
• 이는, 초기분포(상태)와 무관하게 존재하고, 임의의 초기분포 $\boldsymbol{\pi^{(0)}}$에 대해서, $\lim_{n \rightarrow \infty} \boldsymbol{\pi^{(0)}}P^n = \boldsymbol{\pi}$가 성립한다. 
• 이와 같이, Limiting Distribution(극한분포)가 존재한다면, 행렬의 각 행들이 같아질 때 까지 전이행렬을 거듭제곱함으로써 수치적으로 계산할 수 있다. 
• $\pi_j$는 long-term probability, 즉 마코프 체인이 오랜 전이 후에 상태 $j$에 도달하는 확률로 이해할 수 있다,
• 이때, $\boldsymbol{\pi} = \boldsymbol{\pi} P$를 만족하는 $\boldsymbol{\pi}$를 정상분포(Stationary Distriution)이라고 한다.
  If $\boldsymbol{\pi} = [\pi_j, j \in S]$ is limiting distribution for a Markov Chain, then we have
  $$
  \boldsymbol{\pi} = \lim_{n\rightarrow \infty} \boldsymbol{\pi}^{(n)} = \lim_{n\rightarrow \infty} [ \boldsymbol{\pi}^{(0)} P^n ]. 
  $$ Similary, 
  $$
  \begin{aligned}
  \boldsymbol{\pi} &= \lim_{n\rightarrow \infty} \boldsymbol{\pi}^{(n+1)} = \lim_{n\rightarrow \infty}\big[\boldsymbol{\pi}^{(0)}P^{n+1}\big] \\ &= \lim_{n\rightarrow \infty}\big[\boldsymbol{\pi}^{(0)}P^n P \big] = \big[\lim_{n\rightarrow \infty}\boldsymbol{\pi}^{(0)}P^n\big]P \\
  &= \boldsymbol{\pi} P.
  \end{aligned}
  $$
• 만약 초기분포가 Stationary distribution(정상분포)라면 마코프 체인으로부터 생성되는 모든 $X_0, X_1, \cdots$는 모두 같은 분포를 가지게 된다. $$
  \boldsymbol{\pi} P^n = (\boldsymbol{\pi}P)P^{n-1} = \boldsymbol{\pi}P^{n-1} = \cdots = \boldsymbol{\pi}P = \boldsymbol{\pi}.
  $$
• 따라서, 이 경우에 $X_n$의 분포는 모든 $n$에 대하여 동일하며, 그 분포는 $X_0$의 분포인 초기분포 $\boldsymbol{\pi}$와 같고, $(X_n, X_{n+1}, \cdots, X_{n+k})$에 대해서도 성립한다.
• 이런 이유로 정상분포를 불변분포(invariant distribution)라고 부르기도 한다. 
• 만약 극한분포(Limiting Distribution)가 존재하는 경우, 극한분포는 정상분포(Stationary distribution)가 되지만, 그 역은 성립하지 않는다. 

▶ Stationary Distribution을 갖는 경우 : 

• 전이행렬 $P$의 거듭제곱 중 하나의 행렬의 모든 원소들이 양수가 되는 경우(regular matrix), $P$는 유일한 정상분포를 갖는다. 
• $P^n$이 수렴하지 않는 마코프 체인도 존재하고, $P^n$이 서로 다른 행을 가진 행렬로 수렴하는 마코프 체인도 존재하며, 이 경우 극한분포는 존재하지 않는다. 
• 유한한 상태공간을 갖는 마코프 체인은 적어도 하나이상의 정상분포를 갖는다.
• Example : 

Markov Chain and Transition Matrix

• 위와 같은 Markov Chain과 Transition Matrix가 있다고 한다면, Stationary distribution은 다음과 같다.
  $$
  \begin{bmatrix} \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \end{bmatrix} \begin{bmatrix} 0.7 & 0.3 & 0.0 \\ 0.3 & 0.4 & 0.3 \\ 0.0 & 0.4 & 0.7 \end{bmatrix} = \begin{bmatrix} \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \end{bmatrix}
  $$ 
  이와 같이, (1/3, 1/3, 1/3) 벡터는 $P$를 몇번이고 곱해도 동일하게 남아있다. 
  
  •