Markov Chain positive recurrence 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?
 A: 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.$$
