2
$\begingroup$

Are there any necessary and sufficient conditions for a Markov chain to be null recurrent? What about sufficient conditions?

Naturally, I am not looking for tautological statements, e.g., a Markov chain is null recurrent if and only if it is recurrent and has no stationary distribution.

For example, one can consider various random walks on the integers or on infinite directed graphs; how might I figure out whether a particular such walk is null-recurrent or not, except by writing out the recurrence equations and trying to reason from there?

  • 0
    -1. Not a real question I am afraid.2019-05-22

2 Answers 2

4

A simple example: Gambler's ruin problem.

If $p>\frac{1}{2}$, then the Geometric series $\sum_{k=0}^{\infty}\big( \frac{p}{q} \big)^k$ diverges, hence this is a transient MC, if $p<\frac{1}{2}$, then the Geometric series $\sum_{k=0}^{\infty}\big( \frac{p}{q} \big)^k$ converges to $\frac{1}{1-\frac{p}{q}}$, hence this is a positive-recurrent MC. If $p=q=\frac{1}{2}$, this is a null-recurrent MC, i.e. the probability of ruin is 1, but mean time to it is $\infty$.

Hence just by looking at these probabilities you can tell what kind of MC you have and do not need to construct recurrent equations.

  • 0
    I agree with @robinson this is not addressing the problem in given general conditions2018-12-22
1

This is going to be taken almost straight from the wiki.

Let $X_n$ be the state of the Markov chain at time $n$. Let $T_i$ be the first return time to a state $i$, also called the hitting time:

\begin{align} T_i = \inf \{ n \ge 1 : X_n = i \mid X_0 = i \}. \end{align}

State $i$ is transient if $\mathbb{P}(T_i < \infty) < 1$ and state $i$ is recurrent if it is not transient.

The mean recurrence time $M_i$ at state $i$ is the expected return time:

\begin{align} M_i = \mathbb{E}[T_i] = \sum_{n = 1}^\infty n \mathbb{P}(T_i = n). \end{align}

State $i$ is positive recurrent if $M_i$ is finite; otherwise, state $i$ is null recurrent.