Markov chains: recurrent iff expected number of visits is infinite

Dependencies:

  1. Markov chain
  2. Markov chains: recurrent states
  3. Linearity of expectation

Let $X = [X_0, X_1, \ldots]$ be a markov chain with transition function $P$. For state $i$, define $R_i$ and $N_i$ as \[ R_i = \bigvee_{t=1}^{\infty} (X_t = i), \] \[ N_i = \sum_{t=0}^{\infty} \begin{cases} 1 & \textrm{ if } X_t = i \\ 0 & \textrm{ otherwise} \end{cases}. \] Intuitively, $N_i$ is the number of times we visit $i$. Then \[ \frac{1}{1 - \Pr(R_i \mid X_0 = i)} = \E(N_i \mid X_0 = i) = \sum_{t=0}^{\infty} P^{(t)}(i, i). \] This means that $i$ is recurrent iff $\E(N_i \mid X_0 = i)$ is infinite. (The sum $\sum_{t=1}^{\infty} P^{(t)}(i, i)$ is a convenient way to compute $\E(N_i \mid X_0 = i)$.)

Proof

Let $T_i$ be the first time we revisit $i$, i.e., \[ T_i = \min_{t \ge 1} (X_t = i). \] Note that $\overline{R_i} \iff T_i = \infty$ (intuitively, $R_i$ is the event that we visit $i$ at time $t$ for some $t \ge 1$).

\begin{align} & \E(N_i \mid X_0 = i) \\ &= \E(N_i \mid X_0 = i, T_i = \infty)\Pr(T_i = \infty \mid X_0 = i) \\ &\quad+ \sum_{t=1}^{\infty} \E(N_i \mid X_0 = i, T_i = t)\Pr(T_i = t \mid X_0 = i) \\ &= \Pr(T_i = \infty \mid X_0 = i) \\ &\quad+ \sum_{t=1}^{\infty} (1 + \E(N_i \mid X_0 = i))\Pr(T_i = t \mid X_0 = i) \tag{$\begin{array}{ll}\textrm{by markov property} \\ \textrm{and time homogeneity}\end{array}$} \\ &= \Pr(T_i = \infty \mid X_0 = i) \\ &\quad+ (1 + \E(N_i \mid X_0 = i))\Pr(T_i \neq \infty \mid X_0 = i) \\ &= 1 + \E(N_i \mid X_0 = i)\Pr(T_i \neq \infty \mid X_0 = i) \\ &= 1 + \E(N_i \mid X_0 = i)\Pr(R_i \mid X_0 = i). \end{align} Hence, \[ \E(N_i \mid X_0 = i) = \frac{1}{1 - \Pr(R_i \mid X_0 = 1)}. \]

Let \[ A_{i,t} = \begin{cases} 1 & \textrm{ if } X_t = i \\ 0 & \textrm{ otherwise} \end{cases}. \] Then $N_i = \sum_{t=0}^{\infty} A_{i,t}$.

\begin{align} & \E(N_i \mid X_0 = i) \\ &= \sum_{t=0}^{\infty} \E(A_{i,t} \mid X_0 = i) \tag{linearity of expectation} \\ &= \sum_{t=0}^{\infty} \Pr(X_t = i \mid X_0 = i) \\ &= \sum_{t=0}^{\infty} P^{(t)}(i, i). \end{align}

Dependency for:

  1. Markov chains: recurrence is a class property
  2. Markov chains: finite sink is recurrent (incomplete)

Info:

Transitive dependencies:

  1. /analysis/topological-space
  2. /sets-and-relations/countable-set
  3. /sets-and-relations/de-morgan-laws
  4. /measure-theory/linearity-of-lebesgue-integral
  5. /measure-theory/lebesgue-integral
  6. σ-algebra
  7. Generated σ-algebra
  8. Borel algebra
  9. Measurable function
  10. Generators of the real Borel algebra (incomplete)
  11. Measure
  12. σ-algebra is closed under countable intersections
  13. Group
  14. Ring
  15. Field
  16. Vector Space
  17. Semiring
  18. Matrix
  19. Probability
  20. Conditional probability (incomplete)
  21. Random variable
  22. Markov chain
  23. Markov chains: recurrent states
  24. Expected value of a random variable
  25. Linearity of expectation