📂Probability Theory

Types of States in Stochastic Processes

Definition

State space is a countable set of stochastic processes $\left\{ X_{t} \right\}$. Let $i,j$ be the states and let $p_{ij}$ be the transition probabilities.

1. If there exists $p_{ij}^{ ( n ) } > 0$ that satisfies $n \ge 0$, then $j$ is said to be accessible from $i$.
2. If $i$ and $j$ are mutually accessible, they are said to communicate.
3. The largest set of states that communicate with each other is called a class. If two states communicate, they belong to the same class.
4. $d = \gcd \left\{ n > 0 \mid p_{ii}^{(n)} > 0 \right\}$ is called the period and state $i$ is said to be $d$-periodic. If $d=1$, state $i$ is said to be aperiodic.

In a Markov chain, the probability of returning to $i$ after leaving it is $f_{i}$, and the number of steps taken is $\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) $$

5. 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$.
6. If $f_{i} = 1$, then $i$ is recurrent or persistent. $$ p_{ii}^{(n)} = 1 \text{ for some $n \ge 1$.} $$ If not recurrent, it is called transient.
7. If $E ( \tau_{i} ) < \infty$, state $i$ is said to be positive recurrent. If $E(\tau_{i}) = \infty$, it is called null. Here, $E$ is the expected value. $$ E(\tau_{i}) = \sum_{n} n f_{i}(n) $$
8. A state that is both positive recurrent and aperiodic is called ergodic.

---

• $\gcd$ denotes greatest common divisor.

Theorem

• [1] If $\displaystyle \sum_{n=1}^{\infty} p_{ii}^{(n)} = \infty$, then $i$ is recurrent.
• [2] If $\displaystyle \sum_{n=1}^{\infty} p_{ii}^{(n)} < \infty$, then $i$ is transient.

Explanation

Consider the following example of a Markov chain. Circles represent states and numbers on arrows represent transition probabilities.

• Accessible: No matter how many steps it takes, $C$ can be reached from $A$ and $B$, so $C$ is accessible from $A$ and $B$, but $A$ and $B$ are not accessible from $C$.
• $A$ and $B$ are mutually accessible and therefore communicate, but $C$ does not communicate with any state.
• $\left\{ A, B \right\}$ is a class. Also, $\left\{ C \right\}$ is a class. However, $\left\{ A \right\}$ is not the largest set of communicating states and thus cannot be a class. $\left\{ A, B, C \right\}$ is not a class because $C$ does not communicate with any other state.
• Periodic: Considering $B$ as an example, it can go to $A$ with probability $\displaystyle p_{BA} = {{1} \over {2}}$ and return to $B$ immediately with probability $\displaystyle p_{AB} = 1$, making its period $\gcd \left\{ 2, 4, 6, \cdots \right\} = 2$. $A$ and $C$ are aperiodic because they can return to themselves in one step.
• $C$ is aperiodic and positive recurrent since it inevitably returns to itself in a single step. Thus, it is ergodic. However, once $A$ and $B$ go to $C$, they can never return, demonstrating they cannot be positive recurrent despite being aperiodic. This provides further insight into the meaning of ’ergodic'.

Ergodic?

In fact, the more common pronunciation is closer to [ergɒdik].

Ergodicity means the property of a system maintaining its initial state over time. For state $C$, it remains the same no matter how many steps are taken, whereas $A$ and $B$ do not guarantee this. Thus, it is understandable that they cannot be described as ergodic.

As another example, consider the following random walk. The state space is the set of integers $\left\{ \cdots , -2 , -1, 0 , 1 , 2 , \cdots \right\}$, and the probability of moving left is $p$, and the probability of moving right is $(1-p)$.

• Irreducible: Since all states communicate with each other, there is only one class, making it irreducible.
• Recurrent: $f_{i} = 1$ implies that even if state $i$ is left, it will eventually return with infinite repetition, meaning it is recurrent. If $\displaystyle p={{1} \over {2}}$, the probability of returning to $i$ does not converge to $0$, making it recurrent. However, for other cases, the probability of returning decreases, making it transient.
• Even if the random walk is recurrent, there is no guarantee it will return within a finite number of repetitions. Thus, $E ( \tau_{i} ) = \infty$, making it impossible for the random walk to be positive recurrent. It is sufficient to understand ‘positive’ here as meaning that the expected value is not infinite. It signifies a ‘positive’ recurrent property rather than a numerical positivity.