Determine recurrence and transience on an infinite state space

markov chainsmarkov-processprobabilityprobability theorystochastic-processes

Consider a Markov chain with state space $S = {0, 1, 2, . . .}$ and transition probabilities $\{p_{ij}\}$ given by
\begin{equation*}
\left\{
\begin{array}{rl}
p_{i,i-1} = 1, & \forall i \geq 1,\\ p_{0,i} = q_i & \forall i \geq 1.
\end{array} \right. \end{equation*}

with $\sum_{i=1}^{\infty} q_i = 1$ and $q_i > 0 \ \forall i \geq 1$. Determine which states are recurrent.

Intuitively, I think all states are recurrent, but my proof gives me the opposite answer: all states are transient…Anyway, here is my approach:
For the state $0$: $p_{00}^{(n)} = q_{n-1}p_{n-1,n-2}p_{n-2,n-3}…p_{1,0} = q_{n-1} \cdot (n-1) \cdot 1 = q_{n-1}$ for $n=2,3,4,…$. Thus, $\sum_{n=1}^{\infty} p_{00}^{(n)} = \sum_{n=2}^{\infty} p_{00}^{(n)} = \sum_{n=2}^{\infty} q_{n-1} = \sum_{n=1}^{\infty} q_{n} = 1 < \infty.$ This shows that the state $0$ is transient. Further, it is easy to prove that the Markov chain is indeed irreducible, which then implies that all states are transient.

What is wrong with my argument? Any help is greatly appreciated!

Best Answer

Every state is recurrent because the chain is irreducible and $0$ is recurrent; $0$ is recurrent because no matter where you go from $0$ you will go to some state $i$ after which you will return to $0$ in $i$ additional steps. It follows from irreducibility that the whole chain is also recurrent.

Intuitively, without thinking about abstract Markov chain theory, you can explain the recurrence of the entire chain as follows. Beginning at $i$, you will return to zero, and then you will get a trial with probability $\sum_{j=i}^\infty q_j$ to reach $i$ at some point in the next excursion. If you fail, then you return to zero and get another independent trial with the same success probability. Thus you get infinitely many independent trials with a fixed success probability so there will be a success almost surely.

That being said, this chain can definitely be null recurrent. Indeed the expected return time to $0$ is $\sum_i (i+1) q_i$ (one jump to leave, $i$ to come back), which can easily be infinite for instance if $q_i=\frac{1}{\zeta(\alpha)} \frac{1}{i^\alpha}$ and $1<\alpha \leq 2$.