Recurrence of a state in an infinite state space for discrete markov chains

Question

Question

Let $(X_n)_{n\ge0}$ be a Markov Chain with stochastic matrix $P$, determine whether or not the state $0$ is recurrent when $p_1=p_2<0.5$ and $\gamma >0$. The stochastic matrix P is given by:

My Thoughts

Intuitively, the state $0$ seems to be recurrent.

I know that since we have one single irreducible communicating class, this means that if I can show that any of the states are recurrent, then this automatically implies that the state $0$ is also recurrent.

If I can show that for some $i \in \{{0,1,2...}\}$ that $P(T_i< \infty :X_0=i)=1$ then this is sufficient to show that a state $i$ is recurrent (where $T_i$ denotes the first passage time of the state $i$ starting from the state $i$.

I know that we are able to form recurrence relations to compute quantities such as expected hitting time or hitting probabilities, and I am wondering if I am able to use a similar argument in this case.

I would be grateful for any guidance. On a finite state space, these concepts are much clearer to me, as we can use the fact that a communicating class is closed to derive recurrence. However, this argument does not hold for infinite state spaces.

Answer 1

The first thing to notice if Aaron Montgomery’s comment is correct, is that this forms what is called a birth and death chain for states $1,2,\dots$ while state 0 has binomial probabilities of landing on the integers between 0 and 10. Let’s build on Aaron M’s hint using the 1.7 Birth and Death Processes from the source Introduction to Stochastic Processes (starting page 29 in the free preview). After reading that section, we can figure this much out:

$$\begin{split}P_0(T_0<\infty)&=P(0,0)+P(0,1)P_1(T_0<\infty)+\dots+P(0,10)P_{10}(T_0<\infty)\end{split}$$

This is just using the rules of conditional probability and definitions usually associated with Markov chain theory, but let me know if you need clarification.

It remains to use the formula $P_x(T_0<\infty)=\frac{\sum_{y=x}^\infty\gamma_y}{\sum_0^\infty \gamma_y}$, proved in the text, with $\gamma_y=\frac{q_1\dots q_y}{p_1\dots p_y}$ or, as the case here, $\left(\frac{1-p}p\right)^y$. For example, $P_3(T_0<\infty)=1-\frac{\gamma_0+\gamma_1+\gamma_2}{\sum_{y=0}^\infty\gamma_y}$. So all you have to do is check that $(1-p)/p+(1-p)^2/p^2+\dots$ diverges. I think it does since $p<0.5$. Thus, $P_0(T_0<\infty)=P(0,0)+P(0,1)+\dots+P(0,10)=1$ and 0 is a recurrent state. (To fully understand this answer, you’re going to need to read the section 1.7 in the linked book).

Answer 2

Assuming I'm not misunderstanding something about the problem (see my comment above), the chain is indeed recurrent; in fact, it's null recurrent.

HINTS: There are many arguments that you could use to show this, but I'll sketch some that use the tools you suggested. First, the steps away from $0$ are sort of a red herring and should be ignored. Instead, start the chain at any position $a$, and show that $\mathbb P(T_0 < \infty)$. One way you could do this is to choose some $b$ that is much larger than $a$ and consider the time required for the walk to hit either $0$ or $b$.

• Strategy 1: Compute $\mathbb P(T_0 < T_b)$, and let $b \to \infty$; if you can show that the previous probability tends to $1$, you have shown recurrence.

• Strategy 2: Compute $\mathbb E[T_{\{0, b\}}]$; if you can show that this is uniformly bounded across all $b$, you can shown that $\mathbb E[T_0] < \infty$ (which implies that $\mathbb P(T_0 < \infty) = 1$).

The point of these arguments is that they leverage your comfort zone, which is random walks on finite state spaces, by allowing you to worry only about what's going on between $0$ and $b$.

(Let me know if these hints are too vague and you need more.)