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

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.

• Why do you think it is recurrent? Just because the probability of going down the chain is greater than going up doesn’t mean that it must happen? Consider the case where we just keep going up the chain. I’m not claiming this is the answer, but +1 for a nice question
– Vons
Jun 14, 2022 at 17:39
• @Jellyfish My intuition comes from gambling. If a casino game is played where the chance of making money is less than the chance of losing money, then you will certainly go down to $0$ no matter which state you start in. Therefore, using that logic, if we consider each state to be some quantity of money, then is it not the case that we will certainly go back down to $0$ eventually? Jun 14, 2022 at 17:53
• Maybe I'm missing something, but why are $p_1, p_2$ distinct things at all, if they're equal? Doesn't this mean rows 2/4 and 3/5 of your transition matrix expression could be conveniently combined into a single row, i.e. $p_1$ if $i \in \{1, \dots\}, j = i+1$, and $(1- p_1)$ if $i \in \{1, \dots\}, j = i-1$? Jun 15, 2022 at 1:01
• If Aaron Montgomery interpretation is correct , then a full proof is found in Norris Markov Chains p.15 Example 1.3.3 (Gamblers’ ruin) .
– C.C.
Jun 15, 2022 at 9:12

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

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