# Markov Chain positive recurrence [closed]

Consider a Markov Chain with an infinite state space $$\{ \dots, -1, 0, 1 , \dots \}$$, where the transition function is defined as follows. On each step, we sample a function $$f_{i_{n+1}}(x)$$ from $$f_1 : x \mapsto x + 2, \ \ \ f_2 : x \mapsto x - 1, \ \ \ f_3 : x \mapsto 0$$ (The sampling is done uniformly at each step, and is done independently between steps.) The state $$X_{n + 1}$$ is then given by $$f_{i_{n+1}} (X_n)$$.

If I know that the state $$0$$ is positive recurrent, how can I prove that all states are positive recurrent?

## closed as off-topic by NCh, Cesareo, stressed out, Eevee Trainer, mrtaurhoFeb 20 at 6:34

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – NCh, Cesareo, stressed out, Eevee Trainer, mrtaurho
If this question can be reworded to fit the rules in the help center, please edit the question.

• There is no way to prove this. This is wrong without additional assumptions. Consider the transition probabililties $p_{i0}=1$ from any state $i$ to $0$ and obtain that state $0$ is positive recurrent and any other state is transient. – NCh Feb 19 at 15:52
• @NCh My mistake, you are right. The Markov Chain is obtained by random iterations with functions $f_1(x)=x+2$, $f_2(x)=x−1$, $f_3(x)=0$. In each iteration step we choose function to iterate with equal probabilities $1/3$. And my question is: How can I show that this Markov Chain is positive recurrent? – Natalie_94 Feb 19 at 16:09
• Prove that all states communicate and then use that for irreducible Markov chain the states are recurrent or transient simultaneously. – NCh Feb 19 at 16:49
• Can I really prove that all states communicate when the state space is infinite? – Natalie_94 Feb 19 at 17:46

The key result is that if $$C$$ is a communicating class and there exists some state in $$C$$ that is positive recurrent, then all states in $$C$$ are positive recurrent. So if we can prove that (i) the Markov chain is irreducible and (ii) the $$0$$ state is positive recurrent, then we are done.

(i) To prove that the Markov chain is irreducible, it suffices to show that $$0$$ communicates with all states $$i \in \mathbb Z$$. (This would imply that all states $$i \in \mathbb Z$$ are in the same communicating class as $$0$$, which would imply that there is only one communicating class.) So we need to ask ourselves:

• Given $$i \in \mathbb Z$$, is there an $$n \geq 0$$ such that there is a non-zero probability of reaching state $$i$$ from state $$0$$ in $$n$$ steps? (Let's try some examples. For the case $$i = 6$$, there is a non-zero probability of reaching state $$6$$ from state $$0$$ in three steps: we need to choose $$f_1$$ three times. For the case $$i = 5$$, there is a non-zero probability of reaching state $$5$$ from state $$0$$ in four steps: we need to choose $$f_1$$ three times, then choose $$f_2$$. And so on. Hopefully you can work through the various cases.)

• Given $$i \in \mathbb Z$$, is there an $$n \geq 0$$ such that there is a non-zero probability of reaching state $$0$$ from state $$i$$ in $$n$$ steps? Obviously, the answer is yes: you would reach state $$0$$ in one step if you pick $$f_3$$.

(ii) To prove that state $$0$$ is recurrent, note that if you start from state $$0$$, then in order to fail to return from state $$0$$ after $$n$$ steps, you must avoid picking $$f_3$$ $$n$$ times. So if $$T_0$$ is the first return time to state $$0$$, then

$$P (T_0 > n \ | \ X_0 = 0) \leq (\tfrac 2 3 )^n.$$

Hence

$$P(T_0 = \infty | X_0 = 0) \leq \lim_{n \to \infty} (\tfrac 2 3 )^n = 0.$$

To prove positive recurrence, we need to show that the expectation $$\mathbb E[T_0 \ | \ X_0 = 0]$$ is finite. But

$$\mathbb E[T_0 \ | \ X_0 = 0] = \sum_{n=1}^\infty P(T_0 \geq n | X_0 = 0) \leq \sum_{n=1}^\infty (\tfrac 2 3)^{n-1} = \frac{1}{1 - \tfrac 2 3} < \infty.$$