[Markov Chains] 여러가지 상태 분류 (accessible, communicate, irreducible, recurrent, transient)

Classification of States

Accessible, Communicate, Irreducible

어떤 음이 아닌 수 \( n \ge \)에 대하여 \( P_{ij}^n > 0\)이면 상태 \( j \)는 \( i \)로부터 accessible(도달 가능)하다고 한다.

만약 \( j \)가 \( i \)로부터 not accessible하다면, 

\begin{align} P(\text{ever enter }j \mid \text{start in }i) &= P\bigg( \bigcup_{n=0}^{\infty}\{X_n = j \} \mid X_0 = i \bigg) \\ &\le \sum_{n=0}^{\infty}P(X_n = j \mid X_0 = i) = \sum_{n=0}^{\infty}P_{ij}^n = 0 \end{align}

 

두 상태 \( i \)와 \( j \)가 서로 accessible하다면, 이를 communicate(통신)라고 하고 \( i \leftrightarrow j \) 로 표기한다.

communicate의 정의에 따라, state 자기 자신으로 communicate하므로 \( P_{ii}^0 = 1 \) 이다.

communication은 아래 3가지 성질을 가진다. 

• 상태 \( i \)는 상태 \( i \)와 communicate 하다.
• \( i \)가 \( j \)와 communicate하다면, \( j \)와 \( i \)도 communicate하다.
• \( i \)와 \( j \)가 communicate하고, \( j \)와 \( k \)가 communicate하면, \( i \)와 \( k \)도 communicate하다.

1번과 2번의 성질은 communicate의 정의로부터 이해가능하고, 3번 성질은 Chapman-Kolmogorov equation으로부터 유도 가능하다.

 

두개의 상태가 communicate하다면 이들은 같은 class에 있다고 한다. (in the same class)

서로 다른 상태 클래스는 동일하거나(identical) 서로 교집합이 없음(disjoint)을 알 수 있다. 

즉, communication의 개념은 상태 공간(state space)를 여러개의 독립된 class로 나누는 역할을 한다.

만약 하나의 class만 존재하여 모든 상태가 서로 communicate하다면, 이 마르코프 체인은 irreducible(기약적)이라 한다.

Example

세개의 상태 \( 0, 1, 2 \)를 갖는 마르코프 체인의 전이확률행렬이 다음과 같다고 하자.

\[ P = \begin{bmatrix} 1/2 & 1/2 & 0 \\ 1/2 & 1/4 & 1/4 \\ 0 & 1/3 & 2/3 \end{bmatrix} \]

이 마르코프 체인은 0에서 1로(1/2의 확률로 도달), 그리고 1에서 2로 (1/4의 확률로) 도달 가능하다. 

마찬가지로 2에서 1로, 1에서 0으로 도달가능하므로 3개의 상태들은 같은 클래스에 존재한다.

그러므로 위 마르코프 체인은 irreducible하다.

 

4개의 상태 \( 0,1,2,3 \)을 갖는 마르코프 체인의 전이확률행렬이 다음과 같다고 하자.

\[ P = \begin{bmatrix} 1/2 & 1/2 & 0 & 0 \\ 1/2 & 1/2 & 0 & 0 \\ 1/4 & 1/4 & 1/4 & 1/4 \\ 0 & 0 & 0 & 1 \end{bmatrix} \]

이 마르코프체인의 클래스는 {0, 1}, {2}, {3} 이렇게 3개이다.

상태 2에서 상태 0, 1로는 도달가능하지만, 0과 1에서는 2로 도달가능하지 않기 때문에 communicate하지 않다.

그리고 상태3은 absorbing state이므로 어떠한 상태에서 3으로 도달할 수 없다.

 

 

Recurrent, Transient

상태 \( i \)에 대해 \( f_i \)를 \( i \)에서 시작하여 \( i \)로 다시 도달할 확률이라 하자.

만약 \( f_i = 1 \)이라면 \( i \)를 recurrent state(재귀 상태, 재발 상태)라고 하고, \( f_i < 1 \)이면 transient state(일시 상태, 일시적 상태)라고 한다.

\( i \)가 recurrent state라고 하자. 그러면 체인에 따라 \( i \)는 결국 재방문할 것이고, 이를 반복적용하면 \( i \)로 무한히 자주 다시 재방문할 것이다. 

\( i \)가 transient state라고 하자. 이때 \( i \)에 도달할 때 마다 다시는 그 상태에 도달하지 못할 확률이 \( 1 - f_i \)라는 양의 값을 갖는다. 따라서 \( i \)에서 시작하여 정확히 \( n \)시점 동안 \( i \)에 있을 확률은 \( f_i^{(n-1)}(1 - f_i ) \)가 된다. 즉 \( i \)가 transient라면, \( i \)에 머무르는 시간의 길이는 평균이 \( \cfrac{1}{1-f_i} \)인 기하분포를 따르게 된다.

위 두가지를 전이행렬로 나타내면 recurrnet state의 경우 \( \sum_{n=1}^{\infty}P_{ii}^n = \infty \)이고, transient state의 경우 \( \sum_{i=1}^{\infty}P_{ii}^{\infty} < \infty \) 이다.

 

즉, transient state는 유한한 횟수만 방분된다는 사실이다. (그래서 이름이 transient이다.)

유한상태(finite-state)를 가지는 마르코프체인에서 모든 상태가 transient일 수는 없다는 결론을 얻을 수 있다.

이를 증명하기 위해 상태가 \( 0, 1, \dots, M \)이라 하고 모든 상태가 transient라고 하자. 

그렇다면 일정 시간 이후에는 \( 0 \)이 방문되지 않을 것이고, 또 시간이 흐르면 상태 \( 1 \)이 방문되지 않는다. 

이런식으로 진행하면 유한한 시간 \( T \) 이후에는 어떤 상태도 방문되지 않는다. 

그러나 마르코프 프로세스는 시간 \( T \) 이후에도 어떤 상태에 있어야 하므로 모순이다. 

따라서 (finite-state Markov Chain에서는) 적어도 하나의 상태는 recurrent state임이 증명된다.

 

\( i \)가 recurrent이고, \( i \)와 \( j \)가 communicate라면, \( j \) 역시 recurrent 이다.

Proof) 

\( i \leftrightarrow j \)이므로 \( P_{ij}^k > 0\)이고 \( P_{ji}^m > 0 \) 을 만족하는 어떤 정수 \( k, m \)가 존재한다.

임의의 정수 \( n \)에 대하여 \( P_{jj}^{m+n+k} \ge P_{ji}^m P_{ii}^n P_{ij}^k \) 이다.

양변에 모든 \( n \)에 대하여 합계를 구하면 부등호도 유지된다.

그런데 \( i \)가 recurrent이므로 \( n \)을 무한히 합계를 구하면 무한으로 발산한다. 

\[ \sum_{n=1}^{\infty}P_{jj}^{m+n+k} \ge P_{ji}^m P_{ij}^k \sum_{n=1}^{\infty}P_{ii}^n = \infty \]

따라서 \( j \) 역시 무한으로 발산하므로 recurrent하다.

 

유사한 방법으로, \( i \)가 transient리고 \( i \leftrightarrow j \)이면, \( j \) 역시 transient하다.

 

위 정리와 유한 마르코프 체인의 모든 상태가 transient일 수 없다는 사실을 종합하면, 다음의 결론을 얻는다.

"유한하고 기약적인 마르코프 체인의 모든 상태는 재발 상태이다"

(all states of a finite irreducible Markov chain are recurrent)

 

Example

5개의 상태를 갖는 마르코프 체인의 전이확률이 다음과 같다.

\[ P = \begin{bmatrix} 1/2 & 1/2 & 0 & 0 & 0 \\ 1/2 &1/2 & 0 & 0 & 0 \\ 0 & 0 & 1/2 & 1/2 & 0 \\ 0 & 0 & 1/2 & 1/2 & 0 \\ 1/4 & 1/4 & 0 & 0 & 1/2 \end{bmatrix} \]

이 체인은 3개의 클래스를 갖는다: {0, 1}, {2, 3}, {4}

상태4는 transient state이고, 나머지 0~3은 recurrent state이다.

 

또, 아래 체인은 상태가 4개이다.

\[ P = \begin{bmatrix} 0 & 0 & 1/2 & 1/2 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix} \]

모든 state들은 서로 communicate이고, 이 마르코프체인은 상태가 4개인 유한상태이므로 모든 상태들은 recurrent하다.

 

Example: Random Walk

state space가 \( i=0, \pm 1, \pm 2, \dots \)인 마르코프 체인의 전이확률이 다음과 같다고 하자.

\[ P_{i, i + 1} = p = 1 - P_{i, i - 1}, \quad i = 0, \pm 1, \pm 2, \dots, 0 < p < 1 \]

이 마르코프 체인은 랜덤워크이다. 

모든 state들이 clearly communicate하기 때문에, 모든 state들은 all recurrent하거나, all transient이어야 한다.

그러니까 \( \sum_{n=1}^{\infty}P_{00}^n \)의 값이 무한으로 발산하는지, 아니면 무한이 아닌 값으로 수렴하는지 확인해보자.

0에서 0으로 돌아오려면 반드시 짝수번이어야한다. (1달러씩 얻거나 잃는 도박이라고 생각하자. 0원에서 0원의 상태로 돌아오기 위해선 같은 수의 승리/패배가 쌓여야한다.)

\[ P_{00}^{2n-1} = 0, \quad P_{00}^{2n} = \binom{2n}{n}p^n (1-p)^{n} = \cfrac{(2n)!}{n! n!} (p(1-p))^n, \quad n=1, 2, 3, \dots \]

Stirling 근사를 이용하여 \( n! = n^{n + 1/2} e^{-n} \sqrt{2 \pi } \) 근사식을 구하면

\[ P_{00}^{2n} \approx \cfrac{(4p(1-p))^n}{\sqrt{\pi n}} \]

무한급수 수렴판정법을 이용하면 (생략) \( p = 1/2 \)인 경우에만 발산한다.

따라서 \( p = 1/2 \) 이면 chain is recurrent하고, \( p \neq 1/2 \)이면 transient하다.

 

참고로 위 랜덤워크에서 \( p = 1/2 \)이면 symmetric random walk라고 부른다.

위 예시는 상태가 1차원이지만, 2차원 이상으로 확장할 수 있다.

(2차원 랜덤워크는 격자판에서 상, 하, 좌, 우로 이동하는 것으로 비유를 들 수 있다.)

2차원 랜덤워크가 recurrent하려면 \( (i, j) \)에서 \( (i+1,j), (i-1, j), (i, j+1), (i, j-1) \)로 전이할 확률이 모두 \( 1/4 \)이면 된다.

※ 3차원 이상의 symmetric random walk는 \( p \) 값에 관계없이 항상 transient하다.

(3차원 랜덤워크는 3차원 격자공간 상에서 앞, 뒤, 좌, 우, 위, 아래 6방향으로 이동하는 것으로 비유를 들 수 있다.)