Can someone please explain to me the intuition behind Positive recurrence. What does it mean and why is it different to normal recurrence?
1 Answer
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.
-
$\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$– RosieCommented Jun 2, 2012 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$– DidCommented Jun 3, 2012 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$– RosieCommented Jun 3, 2012 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$– HenryCommented Jun 3, 2012 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$– RosieCommented Jun 4, 2012 at 7:51