Back to basics - Irreducible Markov kernels

Let ${{(X_n)}_{n\geq0}}$ be a Markov chain on an at most countable state space ${E}$, with transition kernel ${\mathbf{P}}$. For any ${x,y\in E}$, the number of passages in ${y}$ before returning to ${x}$ is given by

$$\mu_x(y)=\mathbb{E}_x\left(\sum_{n=0}^{T_x-1}\mathbf{1}_{X_n=y}\right) \quad\mbox{where}\quad T_x=\inf\{n>0:X_n=x\}.$$

Note that ${\mu_x(x)=1}$ and ${\mu_x(E)=\mathbb{E}(T_x)}$.

I like very much the following classical theorem about irreducible kernels:

Irreducible kernels. Suppose that ${\mathbf{P}}$ is irreducible. Then every invariant measure ${\mu}$ has full support and satisfies ${\mu(y)\geq\mu(x)\mu_x(y)}$ for any ${x}$ and ${y}$ in ${E}$. Moreover there are three cases:

1. ${\mathbf{P}}$ is transient. Then ${\mu(E)=\infty}$ for every invariant measure ${\mu}$, ${E}$ is infinite, and there is no invariant probability measure;
2. ${\mathbf{P}}$ is recurrent. Then ${\mu_x}$ is invariant for every ${x\in E}$; the invariant measures are all proportional; and if ${\mu}$ is invariant then ${\mu(y)=\mu(x)\mu_x(y)}$ for any ${x,y\in E}$. In particular ${\mu_x(y)\mu_y(x)=1}$. There are two sub-cases:
   1. ${\mathbf{P}}$ is positive recurrent. Then there exists a unique invariant probability measure ${\mu}$ given by ${\mu(x)=1/\mathbb{E}_x(T_x)}$ for every ${x\in E}$;
   2. ${\mathbf{P}}$ is null recurrent. Then ${\mu(E)=\infty}$ for every invariant measure ${\mu}$, ${E}$ is infinite, and there is no invariant probability measure.

Here are my three favorite examples with infinite countable state space:

Random walk on ${\mathbb{Z}}$. The transition kernel is given by ${\mathbf{P}(x,x+1)=p}$ and ${\mathbf{P}(x,x-1)=1-p}$ for every ${x\in\mathbb{Z}}$, with ${p\in(0,1)}$. The kernel is irreducible. A measure ${\mu}$ on ${\mathbb{Z}}$ is invariant for ${\mathbf{P}}$ iff for every ${x\in\mathbb{Z}}$,

$$\mu(x)=\sum_{y\in\mathbb{Z}}\mu(y)\mathbf{P}(y,x)=p\mu(x-1)+(1-p)\mu(x+1).$$

This gives that all invariant measures take the form

$$\mu(x)=a+b\left(\frac{p}{1-p}\right)^x,\quad x\in\mathbb{Z},$$

where ${a,b\geq0}$ are parameters such that ${\mu(0)=a+b>0}$. We recover the counting measure if ${b=0}$ and a sort of geometric measure when ${a=0}$ which is reversible. If ${p=1/2}$ then both terms are the same and the counting measure is reversible.

The chain never admits an invariant probability measure. If ${p=1/2}$ then the chain is null recurrent, all invariant measures are proportional. If ${p\neq 1/2}$ then the chain is transient, there is a two parameters family of invariant measures.

Random walk on ${\mathbb{N}}$. The transition kernel is ${\mathbf{P}(x,x+1)=p}$ for ${x\in\{0,1,\ldots\}}$ and ${\mathbf{P}(x,x-1)=1-p}$ for ${x\in\{1,2,\ldots\}}$ and ${\mathbf{P}(0,0)=1-p}$. Here again ${p\in(0,1)}$. The kernel is irreducible. All invariant measures are geometric, reversible, and take the form

$$\mu(x)=\mu(0)\left(\frac{p}{1-p}\right)^x,\quad x\geq0.$$

If ${p<1/2}$ then the chain is positive recurrent and there is a unique invariant probability measure which is the geometric law on ${\{0,1,\ldots\}}$ with parameter ${p/(1-p)}$. If ${p=1/2}$ then the chain is null recurrent and the invariant measures are all proportional to the counting measure. If ${p>1/2}$ then the chain is transient and all invariant measures are proportional to a geometric blowing measure which cannot be normalized into a probability measure.

The continuous time analogue of this chain is known as the M/M/1 queue.

We could consider instead the reflected random walk on ${\mathbb{N}}$, by taking ${\mathbf{P}(0,1)=1}$. This deformation at the origin has a price: the invariant distribution in the case ${p<1/2}$ is no longer geometric, it is a mixture between a Dirac mass at ${0}$ and the geometric law on ${\{1,2,\ldots\}}$.

Growth and collapse walk on ${\mathbb{N}}$. The transition kernel is given by ${\mathbf{P}(x,x+1)=p_x}$ and ${\mathbf{P}(x,0)=1-p_x}$, for every ${x\in\mathbb{N}}$, where ${p_0=1}$, ${p_1,p_2,\ldots\in[0,1]}$. The kernel is irreducible iff

$$\{x\in\mathbb{N}:p_x>0\}=\mathbb{N} \quad\text{and}\quad \mbox{Card}\{x\in\mathbb{N}:p_x<1\}=\infty.$$

The very special growth-collapse nature of ${\mathbf{P}}$ gives

$$\mathbb{P}_0(T_0>n)=\prod_{x=0}^n\mathbf{P}(x,x+1)=p_0p_1\cdots p_n.$$

Also, if the kernel is irreducible, then it is recurrent iff

$$\lim_{x\rightarrow\infty}p_0p_1\cdots p_x=0.$$

If ${\mu}$ is invariant then for any ${x\in\mathbb{N}}$ with ${x>0}$,

$$\mu(x)=\sum_{y\in\mathbb{N}}\mu(y)\mathbf{P}(y,x)=\mu(x-1)p_{x-1}=\mu(0)p_0p_1\cdots p_{x-1}.$$

It follows that if the kernel is irreducible, then it is positive recurrent iff

$$\sum_{x=0}^\infty p_0p_1\cdots p_x<\infty,$$

and in this case there exists a unique invariant probability measure given by

$$\mu(x)=\frac{1}{\mathbb{E}_x(T_x)},\quad x\in\mathbb{N}.$$

Note that if ${p=\prod_{x\in\mathbb{N}}p_x\in(0,\infty)}$ and if ${\mu}$ is invariant then ${\mu(x)\geq p\mu(0)}$, and since ${\mu(0)=\sum_{x\in\mathbb{N}}(1-p_x)\mu(x)}$, we get ${\mu(0)\geq p\mu(0)\sum_{x\in\mathbb{N}}(1-p_x)}$, which forces either ${\mu(0)=0}$ or ${\mu(0)=\infty}$, and therefore there is no invariant measure in this case.

Further reading. Markov chains, by James Norris.