5
$\begingroup$

Can someone please explain to me the intuition behind Positive recurrence. What does it mean and why is it different to normal recurrence?

$\endgroup$
9
$\begingroup$

If the probability of return or recurrence is $1$ then the process or state is recurrent.

If the expected recurrence time is finite then this is called positive-recurrent; if the expected recurrence time is infinite then this is called null-recurrent.

See the Wikipedia article on Markov chains for more details.

Added as an example:

In a simple symmetric 1D random walk, the probability of first return after $2n$ steps is $\dfrac{\frac{1}{2n-1}{2n \choose n}}{2^{2n}}$. Since $\sum_{n=1}^\infty \dfrac{\frac{1}{2n-1}{2n \choose n}}{2^{2n}} =1$, the probability of first return in finite time is $1$, so this is recurrent. But since $\sum_{n=1}^\infty 2n \dfrac{\frac{1}{2n-1}{2n \choose n}}{2^{2n}}$ is infinite, the expected time of the first return is infinite, so this is null-recurrent.

$\endgroup$
  • $\begingroup$ Thanks, but I dont understand how the probability of return can be 1 but the expected recurrence time be infinity, surely then it will never return! $\endgroup$ – Rosie Jun 2 '12 at 20:35
  • 1
    $\begingroup$ Rosie: the simple symmetric random walk on the integer line returns to its starting point after a random time which is finite with full probability and has infinite expectation. A random variable can very much be almost surely finite and not integrable. $\endgroup$ – Did Jun 3 '12 at 6:58
  • $\begingroup$ @did are you saying that you can have a recurrent class so you will always return in a finite time but where the expected time taken to return can be infinite? I think I understand. So just to check, a state being recurrent means the probability of return in a finite time is 1, in addition to this now, every recurrent state is either positive recurrent or null recurrent. I have also got in my notes that if a state is null recurrent, then as n tends to infinity, the probability that we return to i in nd steps (where d is the period) is 0. Why is this? I cant understand. $\endgroup$ – Rosie Jun 3 '12 at 19:20
  • $\begingroup$ @Rosie: The probability of (any, not necessarily first) return after $nd$ steps need not be $0$ for a null-recurrent state (it is not in the simple random walk) but it does need to tend towards $0$ as $n$ increases. $\endgroup$ – Henry Jun 3 '12 at 20:39
  • $\begingroup$ @Henry, yes sorry that is actually what I meant, but I cant think why, intuitively, it must tend to 0, what happens to make it that way? $\endgroup$ – Rosie Jun 4 '12 at 7:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.