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.

Reflected random walk on ${\mathbb{N}}$. The transition kernel is ${\mathbf{P}(x,x+1)=p}$ and ${\mathbf{P}(x,x-1)=1-p}$ for any ${x\in\{1,2,\ldots\}}$ and ${\mathbf{P}(0,1)=1}$. Here again ${p\in(0,1)}$. The kernel is irreducible. This time the reflection at zero kills the counting measure. All invariant measures are of geometric type, are reversible, and take the form

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

If ${p<1/2}$ then the chain is positive recurrent and there is a unique invariant probability measure which is the geometric distribution 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 measure which cannot be normalized into a probability measure.

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)\cdots=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.

Be First to Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Syntax · Style · Tracking & Privacy.