# Recurrence definition for a Markov chain

We define a state i to be recurrent if $\sum\limits_{n=0}^\infty P(X_n=i,X_k \neq i$ for $1\leq k < n | X_0=i)$=1.

Why do we take infinite series over the probability? Why don't we define recurrent just as:

$P(X_n=i,X_k \neq i$ for $1\leq k < n | X_0=i)$=1

Doesn't this already mean, that if we start in s, we will with probability 1 (almost surely) return to s, after n steps?

Edit:

Also, i is said to be recurrent if:

$\sum\limits_{n=0}^\infty p_{ii}^{(n)}= \infty$.

How does this fit logically with the other definition? Why would the series of the transition probabilities be unbounded?

• Shouldn't it be $\sum_{n = 1}^\infty$ in the first line? – Lucas Jan 27 '13 at 12:08

$$P(X_n=i,X_k \neq i \text{ for } 1\leq k < n \mid X_0=i) = 1$$

This is the probability that the Markov chain will return to state $i$, for the first time, after exactly $n$ steps. What we need for recurrence, however, is the probability that the Markov chain will ever return to state $i$, no matter how long it takes.

$$\sum_{n = 1}^\infty P(X_n=i,X_k \neq i \text{ for } 1\leq k < n \mid X_0=i) = 1$$

This is the probability that the Markov chain will return after 1 step, 2 steps, 3 steps, or any number of steps.

$$p_{ii}^{(n)} = P(X_n = i \mid X_0 = i)$$

This is the probability that the Markov chain is in state $i$ after $n$ steps, but it might have returned to that state earlier. If a state is recurrent, we should expect it to be revisited infinitely often in an infinitely long Markov chain, right? Because if we have visited it once, we will most likely visit it again, and again, and again. The expected number of returns to state $i$ is given by

$$\sum_{n = 0}^\infty p_{ii}^{(n)}$$

and should therefore be infinite for a recurrent state.

• Thank you very much Lucas! One question: "Because if we have visited it once, we will most likely visit it again, and again, and again.". What ensures that we are going to revisit a state after we did once?. If our chain has infinitely many states, how can we be sure that we are going back to one states after we have been once there? – Chris Jan 27 '13 at 23:59
• We only revisit the state infinitely often if it is recurrent. Basically, that's what recurrence means. If we start in state $i$, we will come back to state $i$. And if we start from there again, we will return again. That's why recurrence implies an infinite expected number of returns to the state, ($\sum_{n = 0}^\infty p_{ii}^{(n)} = \infty$). If the state is not recurrent, we are not guaranteed to visit it infinitely often. – Lucas Jan 28 '13 at 16:24