Recurrence and Transience

A fundamental question for Markov chains: starting from a state $i$ , will the chain return to $i$ infinitely often, or will it eventually leave $i$ forever? This dichotomy leads to the classification of states as recurrent or transient.

First return times

Definition1.1First return time

For a state $i \in S$ , the first return time to $i$ is

$\tau_i = \inf\{n \geq 1 : X_n = i\}.$

The return probability is

$f_{ii} = \mathbb{P}(\tau_i < \infty \mid X_0 = i).$

Intuitively, $f_{ii}$ is the probability that the chain ever returns to $i$ after starting from $i$ .

Definition1.2Recurrent and transient states

A state $i$ is recurrent if $f_{ii} = 1$ , i.e., starting from $i$ , the chain returns to $i$ with probability 1.

A state $i$ is transient if $f_{ii} < 1$ , i.e., there is positive probability the chain never returns to $i$ .

RemarkNumber of visits

Let $N_i = \sum_{n=0}^\infty \mathbf{1}_{X_n = i}$ be the total number of visits to state $i$ . Then:

$i$ is recurrent iff $\mathbb{P}(N_i = \infty \mid X_0 = i) = 1$ .
$i$ is transient iff $\mathbb{E}[N_i \mid X_0 = i] < \infty$ .

For transient states, the chain visits $i$ only finitely many times (a.s.).

Characterization via transition probabilities

Theorem1.1Recurrence via infinite series

A state $i$ is recurrent if and only if

$\sum_{n=0}^\infty p_{ii}^{(n)} = \infty.$

Otherwise, $i$ is transient.

Proof sketch: The expected number of visits to $i$ starting from $i$ is

$\mathbb{E}[N_i \mid X_0 = i] = \sum_{n=0}^\infty \mathbb{P}(X_n = i \mid X_0 = i) = \sum_{n=0}^\infty p_{ii}^{(n)}.$

For recurrent states, the chain returns infinitely often, so $\mathbb{E}[N_i \mid X_0 = i] = \infty$ . For transient states, $\mathbb{E}[N_i \mid X_0 = i] = 1/(1-f_{ii}) < \infty$ .

ExampleSimple random walk on Z

For the simple symmetric random walk on $\mathbb{Z}$ (with $p = 1/2$ ), Stirling's approximation gives

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

Hence,

$\sum_{n=0}^\infty p_{00}^{(2n)} \sim \sum_{n=1}^\infty \frac{1}{\sqrt{n}} = \infty.$

The origin is recurrent, and by translation invariance, every state is recurrent. The walk on $\mathbb{Z}$ is recurrent.

For $p \neq 1/2$ (asymmetric walk), the walk drifts to $\pm \infty$ and is transient.

ExampleRandom walk on Z^d

The simple symmetric random walk on $\mathbb{Z}^d$ is:

Recurrent for $d = 1, 2$ .
Transient for $d \geq 3$ .

This is Pólya's theorem (1921). In higher dimensions, the walk has "more room to escape" and does not return with probability 1.

Positive and null recurrence

Definition1.3Mean return time

For a recurrent state $i$ , the mean return time is

$\mu_i = \mathbb{E}[\tau_i \mid X_0 = i].$

State $i$ is positive recurrent if $\mu_i < \infty$ and null recurrent if $\mu_i = \infty$ .

Positive recurrence means the chain returns to $i$ quickly on average; null recurrence means returns occur infinitely often but with arbitrarily long gaps.

ExampleNull recurrence in dimension 1 and 2

Dimension 1: The symmetric random walk on $\mathbb{Z}$ is recurrent, but $\mathbb{E}[\tau_0 \mid X_0 = 0] = \infty$ . Hence, it is null recurrent.
Dimension 2: Similarly, the symmetric random walk on $\mathbb{Z}^2$ is null recurrent.
Dimension $\geq 3$ : The walk is transient, so the question of positive/null recurrence does not arise.

RemarkPositive recurrence and stationary distributions

For an irreducible Markov chain:

The chain is positive recurrent iff there exists a stationary distribution $\pi$ .
If positive recurrent, $\pi_i = 1/\mu_i$ .

Null recurrent and transient chains have no stationary distribution.

Class properties

Theorem1.2Recurrence is a class property

In an irreducible Markov chain, either all states are recurrent or all states are transient. Similarly, either all recurrent states are positive recurrent, or all are null recurrent.

This follows from the fact that in an irreducible chain, all states communicate, and the properties of recurrence/transience and positive/null recurrence are preserved under this communication.

ExampleFinite state space

Every irreducible Markov chain on a finite state space is positive recurrent. (If all states were transient, where would the chain go? It must return to some state infinitely often, contradicting transience.)

ExampleGalton-Watson branching process

A Galton-Watson branching process with offspring distribution $\{p_k\}$ can be viewed as a Markov chain on $S = \{0, 1, 2, \ldots\}$ (population size). State 0 is absorbing: $p_{00} = 1$ . If the mean offspring $\mu = \sum k p_k \leq 1$ , the process dies out (reaches 0) with probability 1. If $\mu > 1$ , there is positive probability of survival forever, so states $\geq 1$ are transient.

Hitting probabilities and absorption

Definition1.4Hitting probability

For states $i, j \in S$ , the hitting probability is

$h_{ij} = \mathbb{P}(\tau_j < \infty \mid X_0 = i),$

the probability of ever reaching $j$ starting from $i$ .

Theorem1.3Hitting probabilities satisfy a system of equations

The hitting probabilities $h_{ij}$ satisfy

$h_{ij} = \begin{cases} 1 & \text{if } i = j, \\ \sum_{k \in S} p_{ik} h_{kj} & \text{if } i \neq j. \end{cases}$

This is a linear system in the unknowns $h_{ij}$ (for fixed $j$ ).

ExampleGambler's ruin

A gambler starts with $k$ dollars and plays a game: win $1$ with probability $p$ , lose $1$ with probability $q = 1-p$ . The game stops when wealth reaches $0$ (ruin) or $N$ (target). Let $h_k$ be the probability of reaching $N$ before $0$ . Then:

$h_k = p h_{k+1} + q h_{k-1}, \quad h_0 = 0, \; h_N = 1.$

Solving this recurrence relation:

If $p = 1/2$ : $h_k = k/N$ .
If $p \neq 1/2$ : $h_k = \frac{1 - (q/p)^k}{1 - (q/p)^N}$ .

As $N \to \infty$ , if $p > 1/2$ , $h_k \to 1 - (q/p)^k > 0$ (positive probability of infinite wealth). If $p < 1/2$ , $h_k \to 0$ (ruin is certain).

Strong Markov property and renewal theory

The strong Markov property (restarting at a stopping time) allows us to decompose the chain's trajectory into i.i.d. excursions. This leads to a connection with renewal theory:

Let $T_1, T_2, \ldots$ be the successive return times to state $i$ .
Then $\{T_n - T_{n-1}\}$ are i.i.d. with distribution of $\tau_i$ .
The number of visits to $i$ up to time $n$ is approximately $n / \mu_i$ for positive recurrent states.

RemarkErgodic theorem for Markov chains

For an irreducible, aperiodic, positive recurrent chain with stationary distribution $\pi$ :

$\lim_{n \to \infty} \frac{1}{n} \sum_{k=0}^{n-1} \mathbf{1}_{X_k = j} = \pi_j \quad \text{a.s.}$

This is the Markov chain analogue of the strong law of large numbers. The long-run proportion of time in state $j$ equals $\pi_j = 1/\mu_j$ .

Summary

Recurrence and transience govern the long-run behavior of Markov chains:

Recurrent states: Visited infinitely often (a.s.).
Transient states: Visited only finitely many times (a.s.).
Positive recurrence: Recurrent with finite mean return time; admits a stationary distribution.
Null recurrence: Recurrent but mean return time is infinite; no stationary distribution.

Examples:

Symmetric random walk on $\mathbb{Z}$ : null recurrent.
Symmetric random walk on $\mathbb{Z}^2$ : null recurrent.
Symmetric random walk on $\mathbb{Z}^d$ ( $d \geq 3$ ): transient.
Any irreducible chain on a finite state space: positive recurrent.