# DTMC : Example of Irreducible Aperiodic Null Recurrent Chain

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.

-
The simple symmetric random walk on the integers is null recurrent. – Byron Schmuland Mar 3 '13 at 20:10

## 3 Answers

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.

-
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.

-
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.

-
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 not:en.wikipedia.org/wiki/Markov_chain#Periodicity – 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