Recurrence and transience of states

Remarks

Let $p^{(n)}_{ii}$ be the diagonal entries of the $n$-th power of the transition matrix. 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 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. 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.