Stochastic walk on $\mathbb{N}$ is recurrent Markov chain

Question

We have a stochastic walk on $\mathbb{N}$ with $p_{i,i-1}=1$ for $i\geq 1$ and $p_{0,i}=p_i>0$ for all $i\geq 0$. Further we have $\sum p_i=1$ and $\sum ip_i<\infty$.

How do I show that this Markov chain is recurrent?

I know that recurrent means that starting in state $i$ the chain will once return to $i$, or $\mathbb{P}(\cup_{t=1}^\infty\{X_t=i\}|X_0=i)=1$.
Further the chain is as follows, from each state we go with probability $1$ to the previous state and from $0$ we can go to any other state. So trivially, 0 is recurrent; and any other state $i$ will go to zero from which it can go to a state larger than $i$ and thus return to $i$. But how can I show this formally?

Answer 1

In your Markov chain, there is a non-zero probability to get from any state in $\mathbb{N}$ to any other state in $\mathbb{N}$. (Check the details). This means that your Markov chain is irreducible. If you show that one state in an irreducible Markov chain is recurrent, that means that the entire Markov chain is a recurrent chain. Since you have shown that $0$ is a recurrent state, this implies that the entire Markov chain is recurrent.

To find the steady-state distribution, try solving the global balance equations, $$ \sum_{j \in \mathbb{N} - \{i\}} \pi_i p_{i,j} = \sum_{j \in \mathbb{N} - \{i\}} \pi_j p_{j,i}. $$

Answer 2

The chain is irreducible as $p_{0i}>0$ for all $i$ and $p_{i-1,i}>0$ for all $i>0$, and is positive recurrent as the expected time between visits to $0$ is $$\sum_{i=0}^\infty (i+1)p_i<\infty. $$ Therefore a unique stationary distribution exists.

The global balance equations are $$\pi_{n+1}+p_n\pi_0 = \pi_n, $$ which yields the recurrence $\pi_{n+1} = \pi_n-p_n\pi_0.$ By inspection we see that $$\pi_{n+1} = \pi_0\left(1-\sum_{i=0}^n p_i\right),\quad n\geqslant0. $$ Writing $1-\sum_{i=0}^n p_i = \sum_{i=n+1}^\infty p_i$ and using $\sum_{i=0}^\infty\pi_i = 1$, we have $$1 = \pi_0\left(1 + \sum_{n=0}^\infty\sum_{i=n+1}^\infty p_i\right). $$ The $p_i$ are nonnegative, so using Tonelli's theorem we compute $$\sum_{n=0}^\infty\sum_{i=n+1}^\infty p_i = \sum_{i=1}^\infty \sum_{n=1}^i p_i = \sum_{i=1}^\infty ip_i<\infty. $$ It follows that $$\pi_0 = \frac1{1+\sum_{i=1}^\infty ip_i} $$ and hence $$\pi_{n+1} = \frac{\sum_{i=n+1}^\infty p_i}{1+\sum_{i=1}^\infty ip_i},\quad n\geqslant0. $$