Finding whether a Markov Chain is recurrent and positive recurrent

markov chains

I have the following Markov Chain with infinite state space $I=\{0,1,2,3,4,…\}$ and transition matrix
$$P = \begin{bmatrix}q_0 & p_0 & 0 & 0 & 0 & 0 & …\\q_1 & 0 & p_1 & 0 & 0 & 0 & …\\ q_2 & 0 & 0 & p_2 & 0 & 0 & … \\ q_3 & 0 & 0 & 0 & p_3 & 0 & … \\ … & … & … & … & … &… & …\end{bmatrix}$$
where $p_j\in (0,1) \forall j\ge0$

I have to find whether the chain is positive recurrent when $p_j=e^{-\frac{1}{(j+1)^2}}, p_j=e^{-\frac{1}{(j+1)}}$ or $p_j=1-\frac{1}{\sqrt{j+2}}$ where $j \ge 0$

My idea is the following,

I know that if I find a stationary distribution $\pi = \pi P$ the expected return time $m_i = E_i(T_i) = \frac{1}{\pi_i}$ has to be less than infinity.

Should I try to find the stationary distribution, or is there an easier way to solve find whether the chain is positive recurrent?

Thanks in advance!

Best Answer

In this setting, you can analyze precisely the distribution first return time to $0$, $\tau_0^+$ in term of which transience and (null and positive) recurrences are phrased, which is quite rare. This allows for a rather smooth and uncomplicated analysis.

Answer to the first question posted (with $p_j=e^{-\frac{1}{(j+1)^2}}$),

You can do much simpler by bounding from below the probability of escaping. Consider the first return time to $0$, $\tau_0^+$, and notice :

$$\mathbb P_0(\tau_0^+=\infty) \ge \mathbb P_0(X_j=j : j=1,2 \ldots) = \prod_j p_j >0,$$

the key point being that, due to the specific form the $p_j$ assume here, the infinite product does not vanish.

Summarizing,

  • the case $p_j=e^{-\frac{1}{(j+1)^2}}$ is transient

--

Answer to accomodate the cases added after the question has been edited:

To prove recurrence, a vanishing upper bound on $$\mathbb P_0(\tau_0^+ \ge k)= \prod_{j=0}^{k-1} p_j$$ is in order; assuming this up to the end, if this bound is further sommable, then you have proven positive recurrence since you know that

$$\mathbb E_0[\tau_0^+]=\sum_{k \ge 1} \mathbb P(\tau_0^+ \ge k)$$

holds for any integer valued random variable. Last, you will further need a lower bound on $\mathbb P(\tau_0^+ \ge k)$ that is not summable to prove null recurrence.

Doing the computation, we see that

  • the case $p_j=1-\frac{1}{\sqrt{j+2}}$ is positive recurrent,
  • the case $p_j=e^{-\frac{1}{(j+1)}}$ is null recurrent.
Related Question