---
tag: FHC702B2R7
kind: definition
name: Recurrence and transience of states
msc: [60J10]
defines: PBZTBWZ4GS
uses: [033TJBZDG0, 0F462493EA, 04VZE3FZXF, 0KRH5157WP]
sources:
  - url: https://en.wikipedia.org/wiki/Discrete-time_Markov_chain
---

## Definition

Let $(X_n)_{n \ge 0}$ be a time-homogeneous [[Markov chain|033TJBZDG0]] on a countable state space $S$.
For a state $i \in S$, write $P_i$ and $E_i$ for probability and expectation when $X_0 = i$.
Let $T_i = \inf\set{n \ge 1 : X_n = i}$ be the first return time to $i$, with $\inf \emptyset = \infty$.

1. The state $i$ is *recurrent* if $P_i(T_i < \infty) = 1$.
2. The state $i$ is *transient* if $P_i(T_i < \infty) < 1$.
3. A recurrent state $i$ is *positive recurrent* if $E_i[T_i] < \infty$, and *null recurrent* if $E_i[T_i] = \infty$.

## Remarks

Let $p^{(n)}_{ii}$ be the diagonal entries of the $n$-th power of the [[transition matrix|0F462493EA]].
Then $i$ is recurrent if and only if $\sum_{n \ge 1} p^{(n)}_{ii} = \infty$, and this sum is the expected number of returns to $i$.
Example: for the simple [[random walk|04VZE3FZXF]] on $\Z$, $p^{(2n)}_{00} = \binom{2n}{n} 4^{-n}$, which behaves like $1/\sqrt{\pi n}$.
The sum diverges, so $0$ is recurrent; it is null recurrent, since this walk has no [[stationary distribution|0KRH5157WP]].
Non-example: for the walk on $\Z$ that steps $+1$ with probability $p \ne 1/2$ and $-1$ with probability $q = 1 - p$, one has $p^{(2n)}_{00} = \binom{2n}{n} (pq)^n \le (4pq)^n$.
Since $4pq < 1$, the sum converges and $0$ is transient, so clause 1 fails.
In an irreducible chain, either all states are transient, or all are null recurrent, or all are positive recurrent.
An irreducible chain has a stationary distribution if and only if its states are positive recurrent.