Ferkans — Interactive Telecom Tutor

Why Classify States?

Not all states in a Markov chain behave the same way. Some states are visited infinitely often; others are visited only finitely many times and then abandoned forever. Some states can reach every other state; others are trapped in subsets. Understanding this structural decomposition is essential before asking questions about long-run behavior: convergence theorems apply only to chains with the right structural properties.

Definition:
Accessible and Communicating States

State $j$ is accessible from state $i$ (written $i \to j$ ) if there exists $n \geq 0$ such that $p_{ij}^{(n)} > 0$ .

States $i$ and $j$ communicate (written $i \leftrightarrow j$ ) if $i \to j$ and $j \to i$ .

Communication is an equivalence relation on $\mathcal{S}$ : it is reflexive ( $i \leftrightarrow i$ since $p_{ii}^{(0)} = 1$ ), symmetric (by definition), and transitive (by Chapman-Kolmogorov).

The equivalence classes under $\leftrightarrow$ are called communicating classes. If there is only one communicating class (every state communicates with every other), the chain is irreducible.

,

Definition:
Irreducible Markov Chain

A DTMC is irreducible if for every pair of states $i, j \in \mathcal{S}$ , we have $i \leftrightarrow j$ . Equivalently, the state space consists of a single communicating class.

If the chain is not irreducible, the state space decomposes into communicating classes $C_1, C_2, \ldots$ , and the long-run behavior can be analyzed class by class.

Irreducible

A Markov chain is irreducible if every state can be reached from every other state with positive probability in some finite number of steps.

Definition:
Recurrent and Transient States

Define the return probability of state $i$ :

$f_{ii} = \mathbb{P}(\exists\, n \geq 1 : X_n = i \mid X_0 = i).$

State $i$ is:

Recurrent if $f_{ii} = 1$ (the chain returns to $i$ with certainty).
Transient if $f_{ii} < 1$ (there is positive probability of never returning).

Equivalently, $i$ is recurrent if and only if $\sum_{n=0}^{\infty} p_{ii}^{(n)} = \infty$ , and transient if and only if $\sum_{n=0}^{\infty} p_{ii}^{(n)} < \infty$ .

A recurrent state is visited infinitely often (with probability 1). A transient state is visited only finitely many times. The expected number of visits to a transient state $i$ , starting from $i$ , is $1/(1 - f_{ii}) < \infty$ .

,

Recurrent state

A state $i$ is recurrent if a chain starting at $i$ returns to $i$ with probability 1. Equivalently, $\sum_{n=0}^{\infty} p_{ii}^{(n)} = \infty$ .

Related: Recurrent and Transient States

Theorem: Recurrence and Transience Criterion

Let $\{X_n\}$ be an irreducible DTMC. Then either all states are recurrent or all states are transient. That is, recurrence and transience are class properties of an irreducible chain.

If $i$ is recurrent and $i \leftrightarrow j$ , then the chain must visit $j$ on its way between visits to $i$ , so $j$ is also visited infinitely often.

Proof

Setup

Suppose $i$ is recurrent and $i \leftrightarrow j$ . We must show $j$ is recurrent. Since $i \to j$ , there exists $m$ with $p_{ij}^{(m)} > 0$ . Since $j \to i$ , there exists $\ell$ with $p_{ji}^{(\ell)} > 0$ .

Bound the return sum for $j$

By Chapman-Kolmogorov: $p_{jj}^{(m + n + \ell)} \geq p_{ji}^{(\ell)} \, p_{ii}^{(n)} \, p_{ij}^{(m)}.$

Summing over $n$ : $\sum_{n=0}^{\infty} p_{jj}^{(m + n + \ell)} \geq p_{ji}^{(\ell)} \left(\sum_{n=0}^{\infty} p_{ii}^{(n)}\right) p_{ij}^{(m)} = \infty,$

since $i$ is recurrent ( $\sum_n p_{ii}^{(n)} = \infty$ ) and the constants $p_{ji}^{(\ell)}, p_{ij}^{(m)} > 0$ .

Conclude

Since $\sum_n p_{jj}^{(n)} = \infty$ , state $j$ is recurrent. The same argument with reversed roles shows: if $i$ is transient, then so is $j$ . $\blacksquare$

,

Definition:
Period of a State

The period of state $i$ is

$d(i) = \gcd\{n \geq 1 : p_{ii}^{(n)} > 0\}.$

If $d(i) = 1$ , the state is aperiodic. If $d(i) > 1$ , it is periodic with period $d(i)$ .

An irreducible chain has a common period for all states (periodicity is a class property). If an irreducible chain is aperiodic, we call the entire chain aperiodic.

A sufficient condition for aperiodicity: if $p_{ii} > 0$ for some state $i$ in an irreducible chain, then the entire chain is aperiodic (since $1 \in \{n : p_{ii}^{(n)} > 0\}$ forces $\gcd = 1$ ).

,

Aperiodic

A state $i$ (or an irreducible chain) is aperiodic if $\gcd\{n \geq 1 : p_{ii}^{(n)} > 0\} = 1$ . Aperiodicity ensures the chain does not cycle deterministically among subsets of states.

Related: Period of a State

Example: Gambler's Ruin

A gambler starts with $\$i$ and bets $\$1$ on each round of a fair game ( $p = q = 1/2$ ). The gambler stops when reaching $\$0$ (ruin) or $\$N$ (goal). Model this as a DTMC on $\mathcal{S} = \{0, 1, \ldots, N\}$ and classify the states.

Solution

Identify the transition probabilities

For $1 \leq i \leq N-1$ : $p_{i,i+1} = p = 1/2$ and $p_{i,i-1} = q = 1/2$ . States 0 and $N$ are absorbing: $p_{00} = 1$ and $p_{NN} = 1$ .

Identify communicating classes

States $\{1, 2, \ldots, N-1\}$ form one communicating class (each can reach its neighbors). State $\{0\}$ is a communicating class by itself, as is $\{N\}$ . The chain is not irreducible.

Classify recurrence and transience

The absorbing states $0$ and $N$ are recurrent (once entered, never left). The interior states $\{1, \ldots, N-1\}$ are transient: starting from any interior state, the gambler eventually reaches 0 or $N$ with probability 1 and never returns to the interior.

Ruin probability

For a fair game ( $p = 1/2$ ), the probability of ruin starting from state $i$ is: $\mathbb{P}(\text{ruin} \mid X_0 = i) = 1 - \frac{i}{N}.$

This is derived by solving the system $r_i = \frac{1}{2} r_{i-1} + \frac{1}{2} r_{i+1}$ with $r_0 = 1, r_N = 0$ .

,

Example: Simple Random Walk on $\mathbb{Z}$

Consider the simple symmetric random walk on $\mathbb{Z}$ : at each step, move right with probability $1/2$ and left with probability $1/2$ . Is this chain irreducible? Is it recurrent or transient?

Solution

Check irreducibility

From any state $i$ , we can reach any state $j$ in $|j - i|$ steps (with positive probability). So the chain is irreducible.

Check recurrence

We need $\sum_{n=0}^{\infty} p_{00}^{(n)}$ . Note $p_{00}^{(2n)} = \binom{2n}{n} (1/2)^{2n}$ and $p_{00}^{(2n+1)} = 0$ (the walk has period 2, but we check the sum regardless).

By Stirling's approximation, $\binom{2n}{n} \approx \frac{4^n}{\sqrt{\pi n}}$ , so

$p_{00}^{(2n)} \approx \frac{1}{\sqrt{\pi n}}.$

Since $\sum_{n=1}^{\infty} \frac{1}{\sqrt{n}} = \infty$ , the series diverges.

Conclusion

The simple symmetric random walk on $\mathbb{Z}$ is recurrent. Despite wandering to arbitrarily large values, it returns to the origin infinitely often.

Remark: The same walk in $\mathbb{Z}^d$ is recurrent for $d \leq 2$ (Polya, 1921) and transient for $d \geq 3$ . This is one of the most celebrated results in probability theory.

,

Gambler's Ruin: Sample Path Simulation

Simulate sample paths of the gambler's ruin problem. Observe how the gambler's fortune evolves and how the ruin probability depends on the initial fortune $i$ , the target $N$ , and the win probability $p$ .

Parameters

Initial fortune i10

Target N20

Win probability p0.5

Number of paths5

Communicating Classes and Periodicity

Explore how the structure of the transition matrix determines communicating classes and periodicity. Select from several example chains to see their class decomposition, or enter a custom matrix.

Parameters

Example chain

Select a pre-built example or choose custom

Common Mistake: Finite Irreducible Chains Are Always Recurrent

Mistake:

Trying to check recurrence for a finite irreducible chain by summing $\sum_n p_{ii}^{(n)}$ . This is unnecessary work.

Correction:

Every finite irreducible Markov chain is automatically recurrent. Transience is only possible for chains on infinite state spaces (like the random walk on $\mathbb{Z}^3$ ). For finite chains, focus on periodicity and the stationary distribution.

Common Mistake: Reading Period from the Transition Diagram

Mistake:

Concluding that a chain has period 2 because "it looks like it alternates" in the transition diagram, without computing $\gcd\{n : p_{ii}^{(n)} > 0\}$ .

Correction:

Always compute the period formally. A single self-loop ( $p_{ii} > 0$ ) anywhere in an irreducible chain makes the entire chain aperiodic, regardless of how the rest of the diagram looks.

Recurrent vs Transient States

Property	Recurrent	Transient
Return probability $f_{ii}$	$f_{ii} = 1$	$f_{ii} < 1$
$\sum_n p_{ii}^{(n)}$	$= \infty$	$< \infty$
Number of visits	Infinite (a.s.)	Finite (a.s.)
Finite irreducible chain?	Always recurrent	Impossible
Random walk on $\mathbb{Z}^d$	$d = 1, 2$ : recurrent	$d \geq 3$ : transient

Quick Check

Consider a DTMC on $\{1, 2, 3\}$ with transition matrix $\mathbf{P} = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$ . What is the period of this chain?

1 (aperiodic)

2

3

6

Correction:

3

The chain cycles deterministically $1 \to 2 \to 3 \to 1$ , returning to each state every 3 steps. $\gcd\{3, 6, 9, \ldots\} = 3$ .

Key Takeaway

States decompose into communicating classes. Within an irreducible chain, all states share the same recurrence/transience and the same period. For finite irreducible chains, all states are recurrent — transience requires an infinite state space. Aperiodicity ( $d = 1$ ) and irreducibility together guarantee convergence to a unique stationary distribution (Section 3).

Classification of States

Why Classify States?

Definition: Accessible and Communicating States

Definition: Irreducible Markov Chain

Irreducible

Definition: Recurrent and Transient States

Recurrent state

Theorem: Recurrence and Transience Criterion

Setup

Bound the return sum for $j$

Conclude

Definition: Period of a State

Aperiodic

Example: Gambler's Ruin

Identify the transition probabilities

Identify communicating classes

Classify recurrence and transience

Ruin probability

Example: Simple Random Walk on Z\mathbb{Z}Z

Check irreducibility

Check recurrence

Conclusion

Gambler's Ruin: Sample Path Simulation

Parameters

Communicating Classes and Periodicity

Parameters

Common Mistake: Finite Irreducible Chains Are Always Recurrent

Common Mistake: Reading Period from the Transition Diagram

Recurrent vs Transient States

Quick Check

Key Takeaway

Definition:
Accessible and Communicating States

Definition:
Irreducible Markov Chain

Definition:
Recurrent and Transient States

Definition:
Period of a State

Example: Simple Random Walk on $\mathbb{Z}$