2

The figure shows the Markov chain with the transition probabilities. I need to prove that it is null recurrent by showing $$ \sum_n p_{00}^{(n)} \to \infty$$ Showing the above is enough as I can show it is not positive recurrent as no stationary distribution exists for this reversible chain. However, I am unable to show that the sum diverges. For a random walk on the infinite line, we could directly write $p_{00}^{(2n)} = ^{2n}C_n (0.5)^{2n}$ but I am confused about how to proceed in this semi-infinite chain.

Markov Chain

Black Jack 21
  • 698
  • 6
  • 24

1 Answers1

3

If you've shown that the random walk on the infinite line is recurrent, you've shown that when you go from state $1$ to state $2$ in that random walk, you will return to state $1$ with probability $1$.

This means that when you go from state $1$ to state $2$ in the semi-infinite random walk, you will also return to state $1$ with probability $1$, because the states $\{2,3,4,\dots\}$ can't distinguish the infinite and semi-infinite line. (Before returning to $1$, a random walk on the infinite line will never visit $\{0,-1,-2,-3,\dots\}$, so it doesn't matter if those states actually exist.)

Therefore the random walk on the semi-infinite line is also recurrent.

Misha Lavrov
  • 142,276