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.

| cite | improve this answer | |
  • $\begingroup$ 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$. $\endgroup$ – Samantha Sep 8 '15 at 11:48
  • $\begingroup$ @Samantha: $\pi_2 = \left(\frac{2-1}{2}\right)^x \pi_1$. You're quite right. I'll fix that. $\endgroup$ – Patrick Stevens Sep 8 '15 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.