도달가능 및 상호도달가능 (Accessible and Communicate)
기본적으로 이항 관계(링크)에 대한 부분을 알고 있으면 도움된다.
• 도달가능 (accessible)
만일 상태 $ i $ 에서 시작하여 결국 상태 $ j $ 에 도착할 확률이 $ 0 $ 보다 크면, 즉 $ P_{ij}^{(n)} > 0 $ 인 $ n \in \mathbb{Z}_+ $ 이 존재하면 상태 $ j $ 는 상태 $ i $ 에서 도달가능하다고 하며, $ i \to j $ 라 표기한다.
• 상호도달가능 (communicate)
만일 상태 $ i $ 와 상태 $ j $ 에 대하여 $ P_{ij}^{(n)} > 0 $ 과 $ P_{ji}^{(m)} > 0 $ 인 $ m, n \in \mathbb{Z}_+ $ 이 존재하면 $ i $ 와 $ j $ 는 상호도달가능하다고 하며, $ i \leftrightarrow j $ 라고 표기한다.
상호도달가능은 동치관계(equivalence relation)이다. 즉 다음 조건을 만족한다.
- 모든 $ i $ 에 대하여 $ i \leftrightarrow i $, 즉 반사적(reflexive)이다.
- $ i \leftrightarrow j \Longrightarrow j \leftrightarrow i $, 즉 대칭적(symmetric)이다.
- $ i \leftrightarrow j \land j \leftrightarrow k \Longrightarrow i \leftrightarrow k $, 즉 전이적(transitive)이다.
• 동치류 (equivalent class)
동치류는 상호도달가능한 모든 상태들의 모음이다. 예를 들어 아래와 같은 전이행렬 $ P $ 가 있다면 $ P $ 는 동치류 $ \{ 0, 1 \} $ 과 $ \{ 2, 3 \} $ 을 갖는다.
$$ P = \begin{bmatrix} 1/2 & 1/2 & 0 & 0 \\ 1/2 & 1/2 & 0 & 0 \\ 0 & 0 & 3/4 & 1/4 \\ 0 & 0 & 1/4 & 3/4 \end{bmatrix} $$
기약적 및 비기약적 (Irreducible and Reducible)
• 기약적 (irreducible)
만약 모든 임의의 상태쌍 $ i $ 와 $ j $ 에 대하여 $ P_{ij}^{(n)} > 0 $ 인 $ n \in \mathbb{Z}_+ $ 이 존재하면 전이행렬 $ Q $ 를 갖는 마르코프 연쇄를 기약적이라 한다. 즉 분할 불가하다.
다시 생각해본다면 오직 한 개의 동치류만 있으면, 즉 모든 상태들이 상호도달가능하면 기약적 마르코프 연쇄이다.
• 비기약적 (reducible)
기약적이지 않은 마르코프 연쇄는 비기약적이라 한다. 즉 분할 가능하다.
재귀적 및 일시적 (Recurrent and Transient)
• 돌아올 확률
마르코프 연쇄가 궁극적으로 상태 $ i $ 로 돌아올 확률 $ f_i $ 는 다음과 같다.
$$ f_i = P(X_n = i \text{ for some } n \geq 1 \mid X_0 = i) $$
• 재귀적 (recurrent)
만일 $ f_i = 1 $ 이라면 상태 $ i $ 를 재귀적 혹은 지속적(persistent)이라 한다.
상태 $ i $ 가 재귀적이고 $ i \leftrightarrow j $ 이면 $ j $ 는 재귀적이다.
만약 유한 상태공간을 갖는 마르코프 연쇄가 기약적이라면 모든 상태는 재귀적이다. 단 역은 성립하지 않는다. 즉 모든 상태가 재귀적이라 해서 유한 기약 마르코프 연쇄는 아니다.
모든 상태가 재귀적이 아니라 가정하자. 그렇다면 궁극적으로 모든 상태를 떠날 것이며, 따라서 연쇄가 성립하지 않는다. 그러므로 적어도 한 상태는 재귀적이어야 한다.
따라서 일반성에 손상 없이 상태 $1$ 이 재귀적이라고 가정하고, 임의의 다른 상태 $ i $ 를 보자. 기약성의 정의에 의해, 어떤 $ n \in \mathbb{Z}_+ $ 에 대하여 $ P_{1i}^{(n)} > 0 $ 이다. 그러므로 연쇄가 상태 $1$ 에 있을 때 $ n $ 단계 후 상태 $ i $ 에 있을 양의 확률이 존재한다. 연쇄가 상태 $1$ 을 무한히 자주 방문하므로, 연쇄가 상태 $1$ 에서 시작하여 결국 상태 $ i $ 에 도달한다는 것은 자명하다.
상태 $ 1 $ 에 방문하는 것을 최대 $ n $ 단계 안에 상태 $ i $ 에 도달 가능한 시행으로 간주해보자. 그렇다면 상태 $ i $ 에서 시작하면 상태 $ 1 $ 이 재귀적이므로 연쇄는 상태 $ 1 $ 에 돌아올 것이고, 같은 논리에 의해 다시 상태 $ i $ 에 도달할 것이다.
귀납법에 의해 연쇄는 상태 $ i $ 를 무한히 자주 방문할 것이고, 이때 $ i $ 가 임의의 $ i $ 였으므로 모든 상태가 재귀적이라 할 수 있다.
• 일시적 (transient)
만일 $ f_i < 1 $ 이면 상태 $ i $ 를 일시적이라 한다. 이것은 만일 연쇄가 $ i $ 에서 떠나면 다시 $ i $ 로 돌아오지 않을 확률이 $ 0 $ 보다 크다는 것을 의미한다. 즉 $ i $ 에서 $ i $ 로 못 돌아올 가능성이 있는 것이다. 따라서 상태 $ i $ 를 떠날 양의 확률이 존재하는 한 연쇄는 궁극적으로는 영원히 $ i $ 를 떠날 것이다.
유한상태 마르코프 연쇄에서 모든 상태는 일시적일 수 없다. 또한 동치류의 어떤 한 상태가 일시적이면 다른 모든 상태들도 일시적이다.
• 돌아오는 횟수
$ X_0 = i $ 라 하고, $ N $ 을 마르코프 연쇄가 상태 $ i $ 를 영원히 떠나기 전까지 상태 $ i $ 에 머무르는 횟수라 하자. 여기서 $ X_0 = i $ 이므로 $ N \geq 1 $ 이다. 그렇다면 다음이 성립한다.
$$ \text{State } i \text{ is recurrent } \Longleftrightarrow E(N) = \infty $$
$$ \text{State } i \text{ is transient } \Longleftrightarrow E(N) < \infty $$
만일 $ i $ 가 재귀적이라면 연쇄가 무한히 $ i $ 로 돌아온다. 따라서 $ E(N) = \infty $ 이다.
그렇지 않은 경우, 즉 $ i $ 가 일시적이라 해보자. 그렇다면 다음과 같다.
$ P(N = 1) = 1 - f_i \\ P(N = 2) = f_i (1-f_i) \\ \qquad \vdots \\ P(N = k) = f_i^{k-1} (1-f_i) $
즉 $ N \sim \text{Geom} (1-f_i) $ 이고, $ f_i < 1 $ 이다. 따라서 다음이 성립한다.
$ E(N) = 1 / (1-f_i) < \infty $
$$ \text{State } i \text{ is recurrent } \Longleftrightarrow \sum_{n=1}^\infty P_{ii}^{(n)} = \infty $$
$$ \text{State } i \text{ is transient } \Longleftrightarrow \sum_{n=1}^\infty P_{ii}^{(n)} < \infty $$
표시확률변수 $I_n $ 을 다음과 같이 정의하자.
$ I_n = \begin{cases} 1, & \quad \text{ if } X_n = i \\ 0, & \quad \text{ otherwise } \end{cases} $
그렇다면 $ \sum_{n=1}^\infty I_n $ 으로 정의된 $ N $ 은 $ i $ 로 돌아오는 횟수이다.
$ \sum_{n=1}^\infty P_{ii}^{(n)} = \sum_{n=1}^\infty P(X_n = i \mid X_0 = i) $
$ = \sum_{n=1}^\infty E(I_n \mid X_0 = i) $
$ = E \left( \sum_{n=1}^\infty I_n \mid X_0 = i \right) $
$ = E ( N \mid X_0 = i ) $
$ = \infty $
주기 (Period)
마르코프 연쇄의 상태 $ i $ 의 주기 $ d(i) $ 는 $ i $ 에서 시작할 때 $ i $ 로 돌아올 수 있는 가능한 단계 수들의 최대공약수이다. 즉 다음과 같다. 만일 $ i $ 에서 시작하여 $ i $ 로 돌아오는 것이 불가능하다면 $ d(i) = \infty $ 이다.
$$ d(i) = \gcd \{ n : P_{ii}^{(n)} \} $$
상태의 주기가 $ 1 $ 이면 상태를 비주기적(aperiodic)이라 하고, 아니라면 주기적(periodic)이라 한다.
마르코프 연쇄의 모든 상태가 비주기적이라면 연쇄 자체를 비주기적이라 하고, 비주기적이 아니라면, 즉 하나의 상태라도 주기적이라면 마르코프 연쇄 자체를 주기적이라 한다.
만약 마르코프 연쇄가 기약적이라면 모든 상태의 주기는 동일하다.
