Countable Markov Chains

Definition: Unlike a finite Markov chain, a countable Markov chain can have a countably infinite state space $(X_n{)}_{n\ge 0}$, $X_n\in \mathbb{N},\mathbb{Z},\mathbb{Q}$

Conceptually, this is quite similar, however we now have situations where there are no boundaries

Consider an infinite random walk ${\mathbf{P}}_{i,i+1}=\frac{1}{2}$, ${\mathbf{P}}_{i,i}=\frac{1}{4}$, ${\mathbf{P}}_{i,i-1}=\frac{1}{4}$
This is irreducible, aperiodic yet $\mathbb{P}[X_n=10]=0$ as $n\to \infty$
This means the conditions for invariant measures are more complicated

Definition: Instead of a transition matrix, we now have a transition function $p(x,y)=\mathbb{P}[X_{n+1}=y\mid X_n=x]$ where $p(x,y)\ge 0$ and ${\sum }_y^{}p(x,y)=1$. We label the initial probabilities $p_0(x)=\mathbb{P}[X_0=x]$, the probabilities at time $n$, $p_n(x)=\mathbb{P}[X_n=x]$. We also denote $p_n(x,y)=\mathbb{P}[X_n=y\mid X_0=x]$

Theorem (Chapman-Kolmogorov): $p_{n+k}(x,y)={\sum }_z^{}{p}_n(x,z)p_k(z,y)$
When we considered a transition matrix, the same result occurred as a natural result of linear algebra, since ${\mathbf{P}}^{n+k}={\mathbf{P}}^n\cdot {\mathbf{P}}^k$ means ${\mathbf{P}}_{ij}^{n+k}={\sum }_l^{}{\mathbf{P}}_{il}^m\cdot {\mathbf{P}}_{lj}^k$

$p_{n+1}(x)={\sum }_y^{}{p}_n(y)p(y,x)$

Definition: Now an invariant measure is a probability distribution $\pi (x)={\sum }_{}^{}\pi (y)p(y,x)$

If $\exists \pi$ where $\pi (x)p(x,y)=\pi (y)p(y,x)$ then $\pi$ is the invariant measure and $X_n$ is reversible, by the same notion of reversibility we considered here.

We can also define communication classes and period the same way

Example: Find the invariant measure of the chain $p(k,k+1)=p$, $p(k,0)=1-p$.
$\pi (n)={\pi }_0\cdot p^n$
${\pi }_0=1-p$
${\pi }_n=(1-p)p^n$

Definition: $x$ is a recurrent state $⟺\mathbb{P}[X_n=x\text{ for infinitely many }n]=1$. $x$ is transient otherwise.

Theorem: $x$ is recurrent $⟺$ ${\sum }_{n=0}^{\infty }{p}_n(x,x)=\infty$ $⟺$ $\mathbb{P}[T(x)=+\infty ]=0$

Example:
$p(x,x+1)=p(x,x-1)=\frac{1}{2}$
$p_{2n+1}(0,0)=0$
$p_{2n}(0,0)=\left(\genfrac{}{}{0ex}{}{2n}{n}\right){\left(\frac{1}{2}\right)}^{2n}=\frac{(2n)!}{n!n!}{\left(\frac{1}{2}\right)}^{2n}$

We use Stirling’s formula $n!\sim \sqrt{2\pi n}{n}^n{e}^{-n}$ to see that $p_{2n}(0,0)\sim \frac{1}{\sqrt{\pi n}}$
This approaches $\infty$, so the chain is recurrent

Now what if we are in ${\mathbb{Z}}^d$?
$p(x,y)=1/2d$, $|x-y|=1$

By the law of large numbers, about $2n/d$ of our steps will be in each of the $d$ components. We need an even number of steps in each component to be able to return to $0$. This occurs with probability $(1/2{)}^{d-1}$, since each is independent, except for the last which will be even if the first $d-1$ are even.

Using Stirling’s formula again, we derive $p_{2n}(0,0)\sim {\left(\frac{1}{2}\right)}^{d-1}{\left(\frac{d}{n\pi }\right)}^{d/2}$
${\sum }_{}^{}{n}^{-a}<\infty ⟺a>1$, so our chain is recurrent if $d=1$ or $2$ but is transient otherwise

Here’s another method for differentiating recurrent and transient chains,

Consider a fixed state $z$ and define $\alpha (x)=\mathbb{P}\{X_n=z\text{ for some }n\ge 0\mid X_0=x\}$

If the chain is recurrent then $\alpha (x)=1$ for all $x$
If the chain is transient then $\alpha (z)=1$ but ${\min }_x\alpha (x)=0$ and we’ll be able to find a solution $\alpha (x)={\sum }_y^{}p(x,y)\alpha (y)$

Example:
$\alpha (x)=(1-p)\alpha (x-1)+p\alpha (x+1)$, $x>0$
We use our standard methods to get $\alpha (x)=c_1+c_2{\left(\frac{1-p}{p}\right)}^x$

Since $\alpha (0)=1$, $\alpha (x)=(1-c_2)+c_2{\left(\frac{1-p}{p}\right)}^x$, $p\ne 1/2$
$\alpha (x)=1+c_{2}x$, $p=1/2$

For $p=1/2$, the only solution is $\alpha (x)=1$
For $p<1/2$, the only solution is $c_2=0$, $\alpha (x)=1$
For $p>1/2$, $\alpha (x)={\left(\frac{1-p}{p}\right)}^x\to 0$

Positive and Null Recurrence

A recurrent chain does not necessarily have a limiting distribution ${\lim }_{n\to \infty }{p}_n(y,x)=\pi (x)$ for each $y\in S$

Certainly, if $X_n$ is transient, then ${\lim }_{n\to \infty }{p}_n(y,x)=0$. But this can also be the case if $X_n$ is recurrent. For example, take the random walk on $\mathbb{Z}$.

Definition: We call a chain null recurrent if it is recurrent but ${\lim }_{n\to \infty }{p}_n(x,y)=0$, otherwise a recurrent chain is positive recurrent

Positive recurrent chains behave similarly to finite Markov chains, where we have to ${\sum }_y^{}\pi (y)p(y,x)=\pi (x)$

We can also define $\mathbb{E}(T\mid X_n=x)=1/\pi (x)$
If $X_n$ is null recurrent then $T<\infty$ with probability $1$, however this equation no longer holds (but it does make sense when $X_n$ is transient)

We can find an invariant distribution $⟺$ $X_n$ is positive recurrent

Branching Process

Let’s look at a more in-depth example, considering a population of individuals at times $n$

Individuals reproduce independently and the probability an individual produces $k$ offspring is $p_k$

$p(k,j)=\mathbb{P}\{X_{n+1}=j\mid X_n=k\}=\mathbb{P}\{Y_1+\cdots +Y_k=j\}$

The mean offspring produced by an individual is $\mu ={\sum }_{i=0}^{\infty }i{p}_i$
$\mathbb{E}(X_{n+1}\mid X_n=k)=k\mu$
$\mathbb{E}(X_n)={\sum }_{k=0}^{\infty }\mathbb{P}\{X_{n-1}=k\}\mathbb{E}(X_n\mid X_{n-1}=k)=\mu \mathbb{E}(X_{n-1})$
$\mathbb{E}(X_n)={\mu }^n\mathbb{E}(X_0)$

So if $\mu <1$ then the mean number of offspring goes to $0$

How do we find the probability that the population dies out? This might occur even if $\mu >1$, and the fact that the expected value reaches $\infty$ does not really help us

We first assume $p_0>0$, $p_0+p_1<1$

$a_n(k)=\mathbb{P}\{X_n=0\mid X_0=k\}$
$a(k)={\lim }_{n\to \infty }{a}_n(k)$

$a(k)=a(1{)}^k$

$a=\mathbb{P}\{\text{population dies out}\mid X_0=1\}$
$={\sum }_{k=0}^{\infty }\mathbb{P}\{X_1=k\mid X_0=1\}\mathbb{P}\{\text{population dies out}\mid X_1=k\}={\sum }_{k=0}^{\infty }{p}_k{a}^k$

This is the generating function of a random variable! We label this $\varphi (a)$, yielding $a=\varphi (a)$

$a=1$ is a solution, but not the only one
We can derive ${\varphi }^n(a)=\varphi ({\varphi }^{n-1}(a))$, which will help us solve $a_n(1)={\varphi }^n(0)$

Inductively, we can see that $a_n\le \hat{a}$, where $\hat{a}$ is the smallest positive root of $a=\varphi (a)$ (because $\varphi$ is an increasing function)

Example: $\varphi (a)=\frac{1}{4}+\frac{1}{4}a+\frac{1}{2}{a}^2$ has solutions $a=1,1/2$, and the extinction probability is $1/2$

If $\mu <1$: trivially $a=1$

If $\mu =1$: ${\varphi }^{\prime }(1)=1$ and therefore ${\varphi }^{\prime }(0)<1$, so $1-\varphi (s)={\int }_s^1{\varphi }^{\prime }(s)ds<1-s$, and $\varphi (s)>s$ for any $s<1$

So the expected population size stays at $1$, while the extinction probability is $1$. This means that the conditional size increases over time

If $\mu >1$: ${\varphi }^{\prime }(1)>1$ and therefore there is some $s<1$ with $\varphi (s)<s$ (since $\varphi (1)=1$)

We also have $\varphi (0)>0$, so there must be some $\varphi (a)=a$ for $a\in (0,s)$. ${\varphi }^{\prime \prime }(s)>0$ for $s\in (0,1)$ so the curve is convex and there is only one solution $a$ as described.

So with positive probability, the population lives forever