Recurrence of infinite markov chain

Question

I have a Markov chain with state space $S=\{0,1,2...\}$ and a sequence of positive numbers $p_1,p_2,...$ where $\sum p_i=1$. The transition probabilities are based on these where

$p(x,x-1)=1, x>0$

$p(0,x)=p_x, x>0$

Is this chain recurrent? What conditions on $p_x$ would make it positively recurrent?

---

I've figured that this means I have a Markov Chain where state 0 can go to any other state with probability $p_x$ but any other state will automatically go to the previous state until it gets back to state 0 and the process starts over. My feeling is that this MC is recurrent because there is zero probability that it will run off, it will always return back down the chain (please help me with the reasoning here).

I also feel like it would be positively recurrent if all $p_x$ where equal but I'm not even sure how to say that since x goes to infinity which would make all $p_x=0$..

Any help or direction would be greatly appreciated. I'm still trying to get a grasp on infinite markov chains.

Answer 1

Well, as you point out, the chain is constructed so that $0$ is recurrent. Then just notice that recurrence is a class property.

Answer 2

Indeed the transition probabilities from state $0$ must go to zero eventually upon reaching some state N. More specifically, (a bit obvious perhaps) all these transition probabilities from state 0 to all other states must sum to one to be properly defined. Just like you said, $\Sigma{p_i}=1$. You can also see this by thinking of matrix $P$ as row stochastic (rows sum to one).

Perhaps also interesting is to look at aperiodicity. Aperiodicity is achieved when all states are aperiodic. Look at all ways such that a state can reach itself with a different number of steps. If the greatest common divisor of all these number of steps is equal to one, the state is aperiodic.

Here, from every state $0,...,N$, we can only return to itself with a number of steps that is a multiple of 2. This implies that the Markov Chain is periodic with period two and cannot be ergodic which needs both the positive recurrence and the aperiodicity. As you might know ergodicity is considered very useful. Uni-chain Markov Chains which also have desirable properties do not require aperiodicity.

How to make a Markov Chain easily aperiodic when modeling? Here just add a tiny probability $p_{i,i}>i$ would make state $i$ aperiodic. You can in fact just always do this for any arbitrary state, just keep track that $P$ stays row stochastic.

I hope this overdue answer provides more insight and a bit of a refresher if you are still using Markov Chains!

Answer 3

The chain is recurrent. Note that the chain irreducible, for any $x> 0, 0 \leadsto x $ as $ p_{0,x} = p_x > 0 $. Also, $ x \leadsto 0 $ since $ p_{x, 0}^{(x)} = p_{x, x-1} \cdot p_{x-1, x-2} \dotsm p_{2, 1} \cdot p_{1, 0} = 1 > 0 $.

Since recurrence is a class property (and the chain is irreducible), it is enough to show $ f_{00}^{\star} = \sum_{ n = 1}^{ \infty } f_{00}^{(n)} = 1 $ where $ f_{ii}^{(n)} $ is probability that first return happens at time $n $, i.e., \begin{equation*} f_{ii}^{(n)} = \mathbb{P} ( X_n = i, X_k \neq i \text{ for } 1 \leq k < n \mid X_0 = i ) \end{equation*} for $ n \geq 1 $.

We can compute $ f_{00}^{(n)} $ explicitly in this case. Note, $ f_{00}^{(1)} = \mathbb{P} ( X_1 = 0 \mid X_0 = 0 ) = p_{0,0} = p_0 $ (say). For $ n \geq 2 $, we have \begin{align*} f_{00}^{(n)} & = \mathbb{P} ( X_n = 0, X_k \neq i \text{ for } 1 \leq k < n \mid X_0 = 0 ) \\ & = \mathbb{P} ( X_1 = n-1, X_2 = n-2, \dotsc, X_{n-2} = 2, X_{n-1} = 1, X_n = 0 \mid X_0 = 0 ) \\ & = p_{0, n-1} \cdot p_{n-1, n-2} \dotsm p_{2, 1} \cdot p_{1, 0} = p_{n-1}. \end{align*} Thus, we have \begin{equation*} f_{00}^{\star} = \sum_{ n = 1}^{\infty} f_{00}^{(n)} = p_0 + \sum_{ n = 2}^{\infty} p_{n-1} = p_0 + \sum_{ n = 1}^{\infty} p_{n} = \sum_{ n = 0}^{\infty} p_{0,n} = 1. \end{equation*}

In this case, it is easy to decide whether the chain is positive recurrent (again a class property) or not. Note, \begin{align*} \sum_{ n = 1}^{\infty} n f_{00}^{(n)} & = 1 . p_0 + \sum_{ n = 2}^{\infty} n p_{n-1} = p_0 + \sum_{ n = 2}^{\infty} p_{n-1} + \sum_{ n = 2}^{\infty} (n-1) p_{n-1} \\ & = 1 + \sum_{ n = 1}^{\infty } n p_n . \end{align*} Thus, $ \sum_{ n = 1}^{\infty} n f_{00}^{(n)} < \infty $ if an only if $ \sum_{ n = 1}^{\infty } n p_n < \infty $. So, the chain is positive recurrent if and only $ \sum_{ n = 1}^{\infty } n p_n < \infty $.