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

Can someone give me an example of a Discrete Time Markov Chain (DTMC) which is

  • Irreducible

  • Aperiodic

  • Null Recurrent

I know that a Simple Symmetric Random Walk on Integers is Irreducible Periodic and Null Recurrent but I am having a tough time coming up with a Markov chain which has the aforementioned properties.

share|cite|improve this question
The simple symmetric random walk on the integers is null recurrent. – Byron Schmuland Mar 3 '13 at 20:10
up vote 1 down vote accepted

Take a random walk on the integers where the jump distribution satisfies $$\mathbb{P}(\xi=-1)=\mathbb{P}(\xi=0)=\mathbb{P}(\xi=1)=1/3.$$ Allowing the walk to sit still with positive probability "kills" the periodicity.

This chain is null for the same reason as the simple, symmetric random walk. If the new chain were positive, it would have a unique invariant probability measure $\pi$. The only non-negative solution to $\pi=\pi P$ is a constant sequence $\pi(k)\equiv c$, which cannot be a probability measure.

share|cite|improve this answer
is this for any state? – Alex Mar 3 '13 at 20:12
Yes, the transition kernel satisfies $p(k,k-1)=p(k,k)=p(k,k+1)=1/3$. That is what "random walk" usually means. – Byron Schmuland Mar 3 '13 at 20:13
@ByronSchmuland, I am sorry but I am sort of unconvinced that this is null recurrent. Can you give me a rough sketch of a proof why it is null recurrent? – Inquest Mar 3 '13 at 20:16

In your example take $p=q=\frac{1}{2}$

EDIT: if $p>q$, your MC is positive-recurrent; otherwise it is transient.

share|cite|improve this answer
This is periodic (with period 2) – Inquest Mar 3 '13 at 20:02
No it's not: if period was two, you return to the starting state w.p. 1 after two periods, which is not the case here. – Alex Mar 3 '13 at 20:03
If I am at zero. How many steps does it take to return to 0? Can I return in 1 or 3? – Inquest Mar 3 '13 at 20:04
@Inquest: "Symmetric" is $p=q=0.5$. Not the presence of 0 and 1 states only. – Bravo Mar 3 '13 at 20:09
Oops. I meant only symmetric (no simple). – Inquest Mar 3 '13 at 20:11

A symmetric random walk on integers (where you move left or right each with probability $p=0.5$) is null recurrent. When the probability $p\ne 0.5$, the walk becomes transient.

share|cite|improve this answer
I don't think so: take $q>\frac{1}{2}$ and MC becomes transient – Alex Mar 3 '13 at 20:02
The simple symmetric RV has period of 2 – Inquest Mar 3 '13 at 20:03
@Inquest: Period? This random walk spans all integers. For period 2, you need just 0 and 1. – Bravo Mar 3 '13 at 20:03
@Inquest: no it's – Alex Mar 3 '13 at 20:04
@Alex: My mistake: the random walk on all integers is either null recurrent or transient. It can become pos. rec. only if we restrict to $\{0,1,2\ldots\}$ and $p>q$. – Bravo Mar 3 '13 at 20:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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