13
$\begingroup$

I cannot understand how there can be positive recurrent and null recurrent Markov Chains. Markov Chains can be split up into transient and recurrent states, where recurrent means that it will be able to go back to that state sooner or later, as compared to a transient state whereby it may escape without ever being able to come back to the state.

Since by definition, a recurrent state means that the Markov chain will be able to return to the state in finite time, why is there a need to define another subset of recurrent Markov chain (null recurrent), whose definition (I feel, even though I know it's not true) violates the whole point of a recurrent Markov Chain in the first place?

Could someone please help with the intuition behind this?

$\endgroup$

2 Answers 2

9
$\begingroup$

Mars Plastic puts it rather nicely. Here are additional elements.

In order to better understand this concept of positive recurrent and null recurrent Markov chains, first it is good to set ourselves in a context where it becomes important.

One of the fundamental questions for Markov chains is whether there exists a stationary distribution. If you restrict yourself to finite state chains, then there is always one (Brouwer's fixed point theorem), and the notion of a null-recurrent state simply does not exist.

In the infinite case, you can start asking new questions. Even fully connected chains can fail to have a stationary distribution. It can be proven that if the chain is positive recurrent then it must exist, and $\pi(i) = 1/E[\tau_i]$.

If it's null recurrent, that means $\pi$ does not exist, but you still have a guarantee of returning to every state.

In other words, even if the concept of a mixing time does not make sense, you still have finite hitting times.

$\endgroup$
2
  • 1
    $\begingroup$ Can't say I like the word guarantee. Having measure 1 just means that the likelihood of something happening is almost certain. $\endgroup$ Commented Oct 19, 2020 at 16:39
  • 2
    $\begingroup$ My thought process was that the return time of a null-recurrent state has a heavy-tailed distribution, which is why its expected value is infinite, even though the probability of its being <$\infty$ is 1. Is this true? $\endgroup$
    – 900edges
    Commented Apr 16, 2021 at 13:08
7
$\begingroup$

A state is recurrent, if the waiting time $\tau$ for the chain's return to that state is almost surely finite. If $\tau$ also has finite expectation, one speaks of positive recurrence, otherwise of null-recurrence. (Recall that a random variable with finite expectation is necessarily almost surely finite, while the converse is not true in general.)

Intuitively speaking, recurrence means that the chain will eventually return, and positive recurrence means that the chain will return relatively fast. This line of thinking is also encouraged by asymptotic results like the Ratio Limit Theorem or Orey's Ergodic Theorem.

$\endgroup$
2
  • $\begingroup$ If the chain is irreducible and recurrent, and for a particular state we know that its return time has finite expectation, does that mean that all states have finite expected return time and hence the whole markov chain is positive recurrent? Or is it possible for some states to have finite expected return time while others have infinite expected return time? $\endgroup$
    – Roy
    Commented Nov 2, 2023 at 20:28
  • $\begingroup$ @Roy No, that is impossible. Any irreducible Markov chain with at least one positive recurrent state is in fact positive recurrent. $\endgroup$ Commented Jun 10 at 19:25

You must log in to answer this question.

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