0

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!

Nikola
  • 1,558

1 Answers1

4

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.
Olivier
  • 1,191
  • Doesn't that answer the question whether the chain is recurrent? It might be the case that the chain is null recurrent and not positive recurrent? In this case that might be true, but I'm looking for a general way to find whether the chain is positive recurrent. – Nikola Aug 14 '19 at 12:27
  • I've added an edit for cases where the chain might not be transient and has to be classified as either null recurrent, or positive recurrent. – Nikola Aug 14 '19 at 12:50
  • @Nikola This answer is looking at $\mathbb{P}_0(\tau_0^+=\infty)$, not $\mathbb{E}[\tau_0^+]$, so it shows transience, not just the failure of positive recurrence. – Ian Aug 14 '19 at 12:53
  • @Nikola nothing to add to Ian's clear point. What you get here is transience $P_0(\tau_0^+=\infty)>0$, which excludes any kind of recurrence $P_0(\tau_0^+=\infty)=0$ : positive $E_0[\tau_0^+]<\infty$, or null $E_0[\tau_0^+]=\infty$. – Olivier Aug 14 '19 at 12:55
  • I will point out though that this answer only actually applies as is to the first case in the question. The argument is still useful in the other cases, but it doesn't fully answer them. – Ian Aug 14 '19 at 15:50
  • I updated my answer according to your suggestion. – Olivier Aug 14 '19 at 16:09
  • I didn't realize those were edited in after your answer had been posted, my bad. Now that your answer is complete I have also removed mine. – Ian Aug 14 '19 at 16:48