1
$\begingroup$

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?

$\endgroup$

closed as off-topic by NCh, Cesareo, stressed out, Eevee Trainer, mrtaurho Feb 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.

  • 1
    $\begingroup$ 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. $\endgroup$ – NCh Feb 19 at 15:52
  • $\begingroup$ @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? $\endgroup$ – Natalie_94 Feb 19 at 16:09
  • $\begingroup$ Prove that all states communicate and then use that for irreducible Markov chain the states are recurrent or transient simultaneously. $\endgroup$ – NCh Feb 19 at 16:49
  • $\begingroup$ Can I really prove that all states communicate when the state space is infinite? $\endgroup$ – Natalie_94 Feb 19 at 17:46
1
$\begingroup$

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.$$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.