4
$\begingroup$

Theorem 4.1 of the book Introduction to Probability Models (10th edition) by Sheldon Ross states that an "irreducible ergodic" Markov chain has limiting probabilities that exist.

And ergodic further means that it must be positive recurrent and aperiodic.

Why did he exclude null recurrent chains? Null recurrence means that the distribution of the number of time steps between visiting the same state doesn't have a mean (a Cauchy like distribution). What's wrong with that kind of distribution? How does that make the chain not have valid steady states?


An example of a null recurrent Markov chain is the one dimensional random walk (symmetric). But that is also not aperiodic (so periodic?). Perhaps we can "fix" that by adding a self-loop at the state $0$ (or even all the states). Does such a chain not have a steady state distribution?

$\endgroup$
6
  • $\begingroup$ Can you come up with a null recurrent chain that doesn't have limiting state probabilities that sum to $1$? There's a fairly standard one... ¶ By the way, Ross's book has a number of different editions with different theorem numberings, so it might be useful to indicate which edition you're using. $\endgroup$
    – Brian Tung
    Dec 11, 2023 at 7:07
  • 2
    $\begingroup$ Haha, good point. What about a triangular lattice? ETA: $+1$ for the cookie jar metaphor. $\endgroup$
    – Brian Tung
    Dec 11, 2023 at 7:12
  • 1
    $\begingroup$ Not familiar with the triangular lattice. Searching for it serves up a bunch of papers, but I'm not sure they align with what you have in mind. Can you please share a reference? $\endgroup$ Dec 11, 2023 at 7:15
  • 1
    $\begingroup$ I'm speaking imprecisely; I just mean the lattice of equilateral triangles stretching to infinity (like this), with any state transitioning to any of its six nearest neighbors with probability $1/6$ each. Does that satisfy your pedagogical needs? $\endgroup$
    – Brian Tung
    Dec 11, 2023 at 7:17
  • 1
    $\begingroup$ I see. Yes, that one will not be aperiodic while still being null recurrent, I think. Need to think about it more. $\endgroup$ Dec 11, 2023 at 7:26

1 Answer 1

1
$\begingroup$

$\def\ed{\stackrel{\text{def}}{=}}$ Ross's theorem $4.1$ says a little more than that an irreducible ergodic chain "has limiting probabilities that exist". Here's the theorem as stated by Ross:

For an irreducible ergodic Markov chain $\ \lim_\limits{n\rightarrow\infty}P_{ij}^n\ $ exists $\color{red}{\text{and is independent of }\ i}\ .$ Furthermore, letting $$\pi_j=\lim_\limits{n\rightarrow\infty}P_{ij}^n, j\ge0,$$ then $\ \pi_j\ $ is the unique nonnegative solution of \begin{align} \pi_j&=\sum_{i=0}^\infty\pi_iP_{ij}, j\ge0,\\ \sum_{j=0}^\infty \pi_j&=1\tag{4.7}\label{eq}\end{align}

The conclusions of the theorem don't hold for any chain with null recurrent states. From equation (\ref{eq}) it follows that there's at least one state $\ s\ $ for which $\ \pi_s>0\ $. But if $\ i\ $ is a null recurrent state, then $$ \lim_\limits{n\rightarrow\infty}P_{is}^n=0\ne\pi_s\ , $$ which would contradict the limit's independence of $\ i\ $.

If you drop the conclusion that the limit is independent of $\ i\ $ then you can weaken the hypotheses of the theorem by replacing "irreducible ergodic Markov chain" with "aperiodic Markov chain with exactly one positive recurrent class of states". If you also drop the conclusion that a nonnegative solution of the equations $\ \pi_j=\sum_\limits{i=0}^\infty\pi_iP_{ij}\ ,$$\ \sum_\limits{j=0}^\infty \pi_j=1\ $ be unique then you can further weaken the hypotheses by replacing the words "exactly one" with "at least one".

$\endgroup$
3
  • $\begingroup$ Thanks. Why is it that if $i$ is recurrent then $\lim_{n \to \infty} P_{is}^n = 0$? What is $s$ here, any state? $\endgroup$ Dec 14, 2023 at 5:23
  • $\begingroup$ I chose $\ s\ $ here to be a positive recurrent state so as to obtain a contradiction to the limit's independence of $\ i\ $. In this case, since any state accessible from a null-recurrent must be null-recurrent, it follows that $\ P_{is}=0\ $ for all $\ n\ $, and hence $\ \lim_\limits{n\rightarrow\infty}P_{is}^n\ .$ It's nevertheless true that $\ \lim_\limits{n\rightarrow\infty}P_{is}^n\ $ for *all* states $\ s\ .$ $\endgroup$ Dec 15, 2023 at 3:47
  • $\begingroup$ I couldn't find an explicit statement of this result anywhere in Ross's book, but it's one of the conclusions of Theorem $1$ on p. 35 of Kai Lai Chung's Markov chains with stationary transition probabilities. $\endgroup$ Dec 15, 2023 at 3:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .