# Determine if the following Markov chain is positive recurrent, null recurrent or transcient.

We consider the Markov Chain with transition probabilities $$p(i,0)=\frac{1}{i^2 +2},\qquad p(i,i+1)= \frac{i^2 +1}{i^2 +2}.$$

Determine if this Markov chain is positive recurrent, null recurrent or transcient.

My attempt: Since all states are connected to $$0$$, then it is sufficient to determine if $$0$$ is a positive recurring state. Consider $$T_{0}$$ the hitting time, that is $$T_{0}=\inf\left\{m\geq 1\: :\: X_{m}=0\right\}.$$ Note that $$\mathbb{P}(T_{0}=n|X_{0}=0)=\left(\frac{1}{2}\times\frac{2}{3}\times\cdots\times\frac{(n-2)^2+1}{(n-2)^{2}+2}\right)\left(\frac{1}{(n-1)^{2}+2}\right)$$ Therefore, we have $$\mathbb{E}(T_{0}|X_{0}=0)=\sum_{n=1}^{\infty}n\times \left(\frac{1}{2}\times\frac{2}{3}\times\cdots\times\frac{(n-2)^2+1}{(n-2)^{2}+2}\right)\left(\frac{1}{(n-1)^{2}+2}\right).$$ I need to determine if this series converges or diverges. I have tried to limit it superiorly and inferiorly but I have not found good bounds.

• My intuition is that this chain is transient because $p(i,i+1)$ is increasing with $i$ and $p(i,0)$ is decreasing with $i$. But I will have to take a closer look at the problem tomorrow. – Math1000 Dec 4 '19 at 8:13
• @Math1000 I think you're right, though the essential fact is maybe not just that $p(i, 0)$ is decreasing, but that it is in fact summable. I'm working on a complete answer right now. – Aaron Montgomery Dec 4 '19 at 15:47

The chain is actually transient.

First, let me address your question about the sum: because of the transience of the chain, if you correctly compute $$\mathbb E[T_0 \mid X_0 = 0]$$ you would apparently get $$\infty$$. This will be a disappointing result, of course, because it won't settle the original question; you will only know that the chain is not positive recurrent, but it could still be either null recurrent or transient.

Proof of transience: There is precisely one path that starts at $$0$$, leaves, and does not return; it's the path for which all steps are to the right. The probability of this path is equal to $$\prod_{i=0}^{\infty}\frac{i^2 + 1}{i^2 + 2},$$ whence recurrence is equivalent to that product being $$0$$. We'll check by turning the product into a sum via a logarithm: $$\log \left(\prod_{i=0}^{\infty}\frac{i^2 + 1}{i^2 + 2} \right) = \sum_{i=0}^{\infty} \log \left(\frac{i^2 + 1}{i^2 + 2} \right) \tag{\bigstar}$$ I claim the sum converges to a negative number instead of diverging to $$-\infty$$, as follows. If we negate the terms we have $$\log \left( \frac{i^2 + 2}{i^2 + 1} \right) = \log \left(1 + \frac{1}{i^2 + 1} \right).$$ Note that for $$x > 0$$, we have $$\log(1 + x) < x$$; hence, we have $$\log \left( \frac{i^2 + 2}{i^2 + 1} \right) < \frac{1}{i^2 + 1}$$ and since the right side is summable, so also is the left.

This implies that the sum in ($$\bigstar$$) converges to a finite negative number (instead of diverging to $$-\infty$$), so the the infinite product above it is therefore positive, and the chain is transient.

Here's another way to see the transience of the chain. I'm not sure if it's cleaner either conceptually or computationally; I'll leave that decision to the reader.

Consider a chain started at state $$n \neq 0$$, and for let $$A_k$$ denote the event that the walk takes exactly $$k$$ steps to the right (from state $$n$$) before then taking one step back to $$0$$. Clearly $$\mathbb P(A_0) = \frac{1}{n^2 + 2}$$, and you can verify that for $$k \geq 1$$, $$\mathbb P(A_k) = \left[\prod_{i=0}^{k-1} \frac{(n+i)^2+1}{(n+i)^2 + 2}\right] \frac{1}{(n+k)^2+2} \leq \frac{1}{(n+k)^2 + 2}.$$ Note that $$\{T_0 < \infty\}$$ can be expressed as a disjoint union $$\cup_{k=0}^{\infty} A_k$$, so $$\mathbb P(T_0 < \infty \mid X_0 = n) = \sum_{k=0}^{\infty} \mathbb P (A_k) \leq \sum_{k=0}^{\infty} \frac{1}{(n+k)^2 + 2} = \sum_{k=n}^{\infty} \frac{1}{k^2 + 2}. \tag{\bigstar \bigstar}$$ Since the full series $$\sum_{k=0}^{\infty} \frac{1}{k^2 + 2}$$ converges, this implies that the rightmost side of ($$\bigstar \bigstar$$) can be made arbitrarily small; in particular, it can be made less than $$1$$. This implies that there is some $$n$$ for which a chain started there has a probability less than $$1$$ of ever returning to $$0$$, which proves the transience of the chain (since it is irreducible).

• Great answer. I was busy today and did not have time to get around to looking at this problem. But I don't think I would have produced such a fine result. – Math1000 Dec 5 '19 at 3:07