Types of States in Stochastic Processes
Definitions
Given a probability process $\left\{ X_{t} \right\}$ with a countable set as its state space, let’s say $i,j$ are states, and $p_{ij}$ are transition probabilities.
- If there exists $n \ge 0$ that satisfies $p_{ij}^{ ( n ) } > 0$, $j$ is said to be accessible from $i$.
- If $i$ and $j$ are accessible to each other, they are said to communicate.
- The largest set of states that communicate with each other is called a class. Two states that communicate are said to be in the same class.
- $d = \gcd \left\{ n > 0 \mid p_{ii}^{(n)} > 0 \right\}$ is called the period, and $i$ is said to be $d$-periodic if $d=1$, it is aperiodic.
In a Markov chain, let the probability of leaving $i$ and then returning to $i$ be $f_{i}$, and the number of times this happens be $\tau_{i}$ recurrent time. $$ f_{i}(\tau_{i}) = P(X_{1} \ne i, X_{2} \ne i, \dots, X_{n-1}\ne i, X_{n} = i | X_{0} = i) $$
If a Markov chain has only one class, it is said to be irreducible. In other words, for all states $i,j$, there exists $m \ge 0$ that satisfies $p_{ij}^{ (m) } >0$.
If $f_{i} = 1$, then $i$ is recurrent or persistent. $$ p_{ii}^{(n)} = 1 \text{ for some $n \ge 1$.} $$ 리커런트 하지 않으면 트랜젼트하다고 한다.
$E ( \tau_{i} ) < \infty$ 면 $i$ 가 포지티브 리커런트라고 한다. $E(\tau_{i}) = \infty$이면 널이라 한다. 여기서 $E$는 기대값이다. $$ E(\tau_{i}) = \sum_{n} n f_{i}(n) $$
포지티브 리커런트면서 어피리어딕이면 에르고딕이라 한다.
- $\gcd$ 는 최대공약수를 의미한다.
정리
- [1] $\displaystyle \sum_{n=1}^{\infty} p_{ii}^{(n)} = \infty$ 이면 $i$ 는 리커런트다.
- [2] $\displaystyle \sum_{n=1}^{\infty} p_{ii}^{(n)} < \infty$ 이면 $i$ 는 트랜젼트다.
설명
예로써 다음의 마코프 체인을 생각해보자. 원은 스테이트, 화살표에 적힌 수는 전이 확률을 나타낸다.
- 접근할 수 있는: 몇 번이 걸리든 $A$ 와 $B$ 는 $C$ 로 갈 수 있으므로 $C$ 는 $A$ 와 $B$ 로부터 억세서블이지만, $A$ 와 $B$ 는 $C$ 에서 억세서블이 아니다.
- $A$ 와 $B$ 는 서로 억세서블하므로 커뮤니케이트지만, $C$ 는 커뮤니케이트한 스테이트가 없다.
- $\left{ A, B \right}$ 는 클래스다. 또한 $\left{ C \right}$ 역시 클래스다. 하지만 $\left{ A \right}$ 는 커뮤니케이트한 스테이트의 집합 중 가장 큰 집합이 아니므로 클래스가 될 수 없다. $\left{ A, B, C \right}$ 는 $C$ 가 다른 스테이트와 커뮤니케이트하지 않아 클래스가 될 수 없다.
- 주기적인: $B$ 를 예로써 생각해보면 $\displaystyle p_{BA} = {{1} \over {2}}$ 의 확률로 $A$ 에 갔다가 바로 $\displaystyle p_{AB} = {{1} \over {4}}$ 의 확률로 $B$ 로 돌아올 수 있기 때문에 주기는 $\gcd \left{ 2, 4, 6, \cdots \right} = 2$ 고, $A$ 와 $C$ 은 한 스텝만에 자기 자신으로 바로 돌아올 수 있기 때문에 어피리어딕이다.
- $C$ 는 어피리어딕인데다가 반드시 한번만에 돌아오므로 포지티브 리커런트다. 따라서 에르고딕인데, $A$ 와 $B$ 는 한번 $C$ 로 빠져버리면 두 번 다시 돌아올 수 없다. 따라서 어피리이딕이지만 포지티브 리커런트가 될 수 없다. 이러한 점에서 ‘에르고딕’의 의미를 다시 생각해볼 수 있다.
에르고딕?
에르고딕성이란 ‘처음의 상태가 시간이 지난 후에도 계속 유지되는 성질’을 말하는데, $C$ 는 아무리 많은 스텝을 거쳐도 처음 그대로인 반면 $A$ 와 $B$ 는 이를 보장할 수 없어 에르고딕이라는 말을 쓸 수 없다고 이해해도 무방하다.
또한 다른 예로써 다음의 랜덤 워크를 생각해보자. 상태공간은 정수의 집합 $\left{ \cdots , -2 , -1, 0 , 1 , 2 , \cdots \right}$ 이고, 왼쪽으로 갈 확률은 $p$, 오른쪽으로 갈 확률은 $(1-p)$ 다.
- 분해할 수 없는: 모든 스테이트는 서로 커뮤니케이트하므로 단 하나의 클래스를 가지며, 따라서 일리듀서블이다.
- 재귀적인: $f_{i} = 1$ 이라는 말은 $i$ 를 떠났더라도 무한히 반복하면 언젠간 반드시 $i$ 로 돌아온다는 뜻이다. $\displaystyle p={{1} \over {2}}$ 일 경우 $i$ 를 떠났더라도 다시 돌아올 확률이 $0$ 으로 수렴할 일이 없으므로 리커런트하다. 하지만 그 외엔 점점 돌아올 확률이 줄어가기 때문에 트랜젼트가 된다.
- 만약 랜덤워크가 리커런트하더라도 유한한 반복 내에 돌아온다는 보장은 없다. 따라서 $E ( \tau_{i} ) = \infty$ and thus, a random walk cannot be positive recurrent. “Positive” here can be understood as not infinite in expectation. The term “positive” contrary to recurrent does not imply the numerical positivity, but a positive notion.