Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

closed as unclear what you're asking by Did, Norbert, Davide Giraudo, egreg, 91500 May 23 '14 at 10:20

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

are you familiar with Gambler's ruin problem? – Alex Oct 10 '12 at 21:04
+1. Have you found the answer? – Tim Apr 14 '13 at 16:30
-1. Not a real question I am afraid. – Did May 23 '14 at 8:01

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.

share|cite|improve this answer
I am aware of this. My question is about the most general case of a Markov chain with countable state-space. – robinson Oct 10 '12 at 21:41

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.

share|cite|improve this answer

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