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.