Here is a question in my problem set which is quite challenging for me:

Suppose $\{X_n\}$ is a Discrete Markov chain with state space $S$ and transition matrix $P$ and no absorbing state ($P_{ii} < 1, \forall i \in S$). Define a new matrix $P'$ by $P'_{ii} = 0, \forall i \in S$ and $P'_{ij} = \frac{P_{ij}}{1 - P_{ii}}$.

Show that $P'$ is a transition matrix and let $\{Y_n\}$ be a DTMC with transition matrix $P'$, argue that $\{X_n\}$ is transient/recurrent $\iff$ $\{Y_n\}$ is transient/recurrent.

The first part is easy and for the $\iff$ proof, my idea is to show $\sum_{n}^{\infty}P_{ii}^{(n)} = \infty \iff \sum_{n}^{\infty} P_{ii}^{'(n)} = \infty$ and $\sum_{n}^{\infty}P_{ii}^{(n)} < \infty \iff \sum_{n}^{\infty} P_{ii}^{'(n)} < \infty$

But I cannot figure out the relation between $P_{ii}^{(n)}$ and $P_{ii}^{'(n)}$, need some help, thanks!


Notice that $P'_{ij} \geq P_{ij}$ whenever $i \neq j$. Therefore, for any two states $i_0,i_n$ and any path $i_0,\dots,i_n$ such that $i_t \neq i_{t+1}$ for all $t$, the probability to observe that path under $P'$ is at least as high as to observe it under $P$. So now choose some path with $i_0=i_n$ which has positive probability under $P$ and use it to conclude that $P'^{(n)}_{i_0 i_0}>0$.

You can adapt this proof to get the reverse implication.

The intuition is that for recurrence vs. transience, if you started at $i$ and are guaranteed to leave $j$ sooner or later anyway, the time it took to wait there has nothing to do with whether you will eventually get back to $i$. So for studying recurrence it is sufficient to prune all self-loops out of the graph (except for absorbing states of course).

For positive recurrence vs. null recurrence this is no longer the case; it can happen that this "pruned" chain is positive recurrent when the original chain was null recurrent.

  • $\begingroup$ Thank you very much! I think your first paragraph is say : "once there is a path ($i_0,\ldots,i_0$)" in $\{X_n\}$, we have higher probability to reproduce the path in $\{Y_n\}$, but the converse is true? Could you involve more details? $\endgroup$ – user370220 Oct 10 '17 at 18:30
  • $\begingroup$ @ZHANGYUE The probability to see such a path under $P$ is generally smaller than under $P'$, but you can nevertheless show that it is not zero if it wasn't zero for $P'$. $\endgroup$ – Ian Oct 10 '17 at 18:30
  • $\begingroup$ @lan Thanks for your interpretation, could you formulize the proof a little bit? Since I am really struggling convert this intuition to rigorous proof :( $\endgroup$ – user370220 Oct 10 '17 at 18:49
  • $\begingroup$ @ZHANGYUE If you understand the sketch in the first paragraph, the adaptation is not really difficult, you just replace $P'_{ij} \geq P_{ij}$ by $P_{ij} \geq (1-P_{ii})P'_{ij}$ and do the same thing. $\endgroup$ – Ian Oct 10 '17 at 19:27
  • $\begingroup$ @lan Thank you! I think I understand the intuition here but I still get little confused, for transience, I need to show $\sum_{n=1}^{\infty} P_{i,i}^{(n)} = \infty \iff \sum_{n=1}^{\infty} P_{i,i}^{'(n)} = \infty$. But as you said, for any path $(i_0,i_1\ldots,i_0)$ with $i_n \not = i_{n+1}$, the probability for $P'$ is higher than $P$, but this is not enough to conclude that $P_{i,i}^{'(n)} \ge P_{i,i}^{(n)}$ right? Since for $P$ there may exists path containing consecutive identical entries $\endgroup$ – user370220 Oct 11 '17 at 3:04

Your Answer

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