# Markov chain with infinitely many states

I am stumped on the following infinite Markov Chain.

Given the this transition matrix for a Markov chain, how do I determine what values of $x$ the chain is positive recurrent/null recurrent/transient? The chain is clearly aperiodic and irreducible, but I am not sure how to determine it is positive recurrent. Ultimately, I want to find the long run probabilities.

$\left( \begin{array} q1-(\frac12)^x & (\frac12)^x & 0&0&0&0&... \\ 1-(\frac23)^x & 0 & (\frac23)^x&0&0&0&... \\ 1-(\frac34)^x & 0 & 0&(\frac34)^x&0&0&... \\ 1-(\frac45)^x & 0 & 0&0&(\frac45)^x&0&... \\ ... & ... \\ ... & ... \\ \end{array} \right)$

Any help will be appreciated! Thank you!

Obviously if $x=0$ then the chain marches off to infinity, so we'll suppose that $x>0$. Then all the states have the same recurrence status because all the states communicate.

Let's suppose first that the chain is positive recurrent. To find the stationary distribution $(\pi_i)_{i \in \mathbb{N}}$, note that the probability we are in state $i \not = 1$ at time $n$ is just $$\left( \frac{i-1}{i} \right)^x \mathbb{P}(\text{we are in state i-1 at time n-1})$$

That is, $\pi_i = \left(\frac{i-1}{i} \right)^x \pi_{i-1}$, so $\pi_i = \left( \frac{1}{i} \right)^x \pi_1$ for $i > 1$.

Since $\pi$ is a distribution, we have $$\pi_1 \left(1+\sum_{i=2}^{\infty} \left( \frac{1}{i} \right) ^x \right) = 1$$

This sum never converges for any $x \leq 1$, so in fact there can't be a stationary distribution. Therefore the chain can't be positive recurrent if $x \leq 1$. If, on the other hand, $x > 1$, then the sum does converge, so if $x>1$ and the chain is positive recurrent, then we've found the stationary distribution.

Is the chain transient or null-recurrent? We examine the state $1$. The probability that "after some time we stop ever hitting $1$" is just $\left(\frac{1}{2} \right)^x \times \left( \frac{2}{3} \right)^x \times \dots$, which of course converges to 0. Therefore the chain is recurrent no matter what $x > 0$ is.

Hence if $x=0$, the chain is transient. If $0 < x \leq 1$, the chain is null-recurrent. If $x > 1$ then it's probably positive-recurrent. I'm still working on proving that the chain actually does tend to the stationary distribution above; with that done, the result is proved.

• Sorry, having trouble figuring out how you got $\pi_i = \left( \frac{2}{i} \right)^x \pi_1$ for $i > 1$, I keep getting $\pi_i = \left( \frac{1}{i} \right)^x \pi_1$ for $i > 1$. – Samantha Sep 8 '15 at 11:48
• @Samantha: $\pi_2 = \left(\frac{2-1}{2}\right)^x \pi_1$. You're quite right. I'll fix that. – Patrick Stevens Sep 8 '15 at 11:50