1

For my course on Markov chains, we have to think about the following problem:

Consider the irreducible Markov chain with $P$ on the state space $S={0,1,2,...}$, with $p_{0,1}=1$, $p_{n,n+1}=1/(n+1)^2$ and $p_{n,0}=1-p_{n,n+1}$ for $n\geq 1$ (all other entries are zero). Check whether this Markov chain is transient or recurrent (Hint: $\prod_{n=2}^{\infty}(1-1/n^2)=1/2)$.

One way we've seen to prove recurrence of a Markov chain is the lemma of Pakes, which says that if for an irreducible Markov chain there exists a state $\bar{i}$ and a $\delta >0$ such that $\forall i > \bar{i}: D_i < -\delta$, then the chain is positive recurrent. The drift $D_i$ of state $i$ is defined as $D_i = \sum_{k=-i}^{\infty}k\,p_{k,k+i}$. For this specific Markov chain, we would have for all $i>0$ that $D_i = -i(1-1/(i+1)^2)+1/(i+1)^2=\frac{-i^3-2i^2+1}{(i+1)^2}$.
For me it seems to be clear from this that the lemma of Pakes is fulfilled. The above expression for the drift will become more and more negative as $i$ increases, so it is easy to pick a $\delta$ and $\bar{i}$ such that $\forall i > \bar{i}: D_i < -\delta$.

My problem however is that, despite the fact this seems the most straight-forward way to proceed, I made no use of the given hint whatsoever and I could not think of any other method to prove recurrence or transience in which the product in the hint (or any infinite product at all) would show up. My question now is twofold:

  • Is the above way of proving positive recurrence correct or did I use the lemma of Pakes in the wrong way?
  • In what method to prove recurrence or transience of this chain does the product of the hint show up?
StakkerMakker
  • 25
  • Is it possible that there is a typo in the problem? It is too easy, and would be more interesting if $p_{n,n+1}=1-1/(n+1)^2$ not $p_{n,n+1}=1/(n+1)^2$. –  Jan 05 '16 at 21:30
  • This is how the problem was given on the paper of exercises, but of course it is possible that they made a mistake in typing it down. However, even if we change that aspect, what method of proving recurrence or transience would make use of the hint that is given? – StakkerMakker Jan 05 '16 at 22:02
  • The hint is not at all useful for the question as given, only if modified as I suggest. –  Jan 05 '16 at 22:07

1 Answers1

1

I will assume that $p_{n,n+1}=1-1/(n+1)^2,$ not $p_{n,n+1}=1/(n+1)^2.$

Suppose you start at state $1$, i.e., $X_0=1$, and let $T_1=\inf(n\geq 1: X_n=1)$ be the return time to the starting position. The escape probability satisfies $$\mathbb{E}(T_1=\infty)\geq p(1,2)p(2,3)p(3,4)\cdots={1\over 2}>0.$$ Since the escape probability is bigger than zero, the chain is transient.

  • Could you maybe explain the concept of the "escape probablity" a little bit, because I don't think we have seen something like this (yet)? – StakkerMakker Jan 05 '16 at 22:12
  • It just means the probability of the chain going off to infinity. If this occurs, of course, the chain might not return to its starting position. –  Jan 05 '16 at 22:13
  • I see. And am I correct in saying that the reason it is greater or equal to $p(1,2)p(2,3)p(3,4)...$ is that this product represents just one possible way in which the chain could go to infinity, so the escape probability contains at least this? – StakkerMakker Jan 05 '16 at 22:18
  • Yes, that is correct. –  Jan 05 '16 at 22:23
  • I see, thank you for your answer. – StakkerMakker Jan 05 '16 at 22:24