Continuous-Time Countable Processes

See Continuous-Time Discrete-State Processes and Countable Markov Chains for more background context

Birth and Death

We assign birth rates ${\lambda }_{n\ge 0}$ and death rates ${\mu }_{n>0}$

$P_n^{\prime }(t)=-({\mu }_n+{\lambda }_n)P_n(t)+{\mu }_{n+1}{P}_{n+1}(t)+{\lambda }_{n-1}{P}_{n-1}(t)$
$p_t(m,n)=\mathbb{P}\{X_t=n\mid X_0=m\}$ is determined by solving the system with $P_m(0)=1$, $P_{n\ne m}(0)=0$

Example:
Queueing models are represented easily

• One server: ${\lambda }_n=\lambda$, ${\mu }_n=\mu$
• $k$ servers: ${\lambda }_n=\lambda$, ${\mu }_n=\min (n,k)\mu$
• Infinite servers: ${\lambda }_n=\lambda$, ${\mu }_n=n\mu$

Population model (with immigration): ${\lambda }_n=n\lambda +\nu$, ${\mu }_n=n\mu$

This chain is clearly irreducible. We check if it is recurrent by examining the corresponding discrete-time chain

$p(n,n-1)=\frac{{\mu }_n}{{\mu }_n+{\lambda }_n}$, $p(n,n+1)=\frac{{\lambda }_n}{{\mu }_n+{\lambda }_n}$
As in Countable Markov Chains, define $a(n)$ as the probability a chain starting at $n$ reaches $0$

$a(0)=1$
$a(n)({\mu }_n+{\lambda }_n)=a(n-1){\mu }_n+a(n+1){\lambda }_n$, $n>0$
$a(n)-a(n+1)=\frac{{\mu }_n}{{\lambda }_n}[a(n-1)-a(n)]$, $n\ge 1$
$a(n)-a(n+1)=\frac{{\mu }_1\dots {\mu }_n}{{\lambda }_1\dots {\lambda }_n}[a(0)-a(1)]$

$a(n+1)=[a(n+1)-a(0)]+a(0)$
$={\sum }_{j=0}^n[a(j+1)-a(j)]+1$
$=[a(1)-1]{\sum }_{j=0}^n\frac{{\mu }_1\dots {\mu }_j}{{\lambda }_1\dots {\lambda }_j}+1$ (we say the $j=0$ term is $1$)

This means the birth and death chain is transient $⟺$ ${\sum }_{n=1}^{\infty }\frac{{\mu }_1\dots {\mu }_n}{{\lambda }_1\dots {\lambda }_n}<\infty$

Like before, not all recurrent chains have limiting probabilities

An irreducible chain is positive recurrent if there is some distribution ${\lim }_{t\to \infty }\mathbb{P}\{X_t=n\mid X_0=m\}=\pi (n)$ for all $m$, other a chain is null recurrent

If the system is in the limiting probability, $P_n(t)=\pi (n)$ and $P_n^{\prime }(t)=0$
$0={\lambda }_{n-1}\pi (n-1)+{\mu }_{n+1}\pi (n+1)-({\lambda }_n+{\mu }_n)\pi (n)$

We solve for $\pi (n)=\frac{{\lambda }_0\dots {\lambda }_{n-1}}{{\mu }_1\dots {\mu }_n}\pi (0)$

This can only be a probability measure if $q={\sum }_{n=0}^{\infty }\frac{{\lambda }_0\dots {\lambda }_{n-1}}{{\mu }_1\dots {\mu }_n}<\infty$, such that $\pi (0)=q^{-1}$

Example:
For a one server queue, ${\sum }_{n=0}^{\infty }\frac{{\lambda }_0\dots {\lambda }_{n-1}}{{\mu }_1\dots {\mu }_n}={\sum }_{n=0}^{\infty }{\left(\frac{\lambda }{\mu }\right)}^n={\left(1-\frac{\lambda }{\mu }\right)}^{-1}$
This is positive recurrent for $\lambda <\mu$, in which case the equilibrium distribution is $\left(1-\frac{\lambda }{\mu }\right){\left(\frac{\lambda }{\mu }\right)}^n$

The expected length of the queue is ${\sum }_{n=0}^{\infty }n\pi (n)={\sum }_{n=0}^{\infty }n\left(1-\frac{\lambda }{\mu }\right){\left(\frac{\lambda }{\mu }\right)}^n=\frac{\lambda }{\mu }{\left(1-\frac{\lambda }{\mu }\right)}^{-1}=\frac{\lambda }{\mu -\lambda }$

We find that a $k$ server queue is positive recurrent if $\lambda <k\mu$

For the infinite server queue, we get ${\sum }_{n=0}^{\infty }\frac{{\lambda }_0\dots {\lambda }_{n-1}}{{\mu }_1\dots {\mu }_n}={\sum }_{n=0}^{\infty }\frac{1}{n!}{\left(\frac{\lambda }{\mu }\right)}^n=e^{\lambda /\mu }$ which is positive recurrent for all $\lambda ,\mu$ with $\pi (n)=e^{-\lambda /\mu }\frac{(\lambda /\mu {)}^n}{n!}$, the Poisson distribution with $\lambda /\mu$

Example:
The Yule process is a pure birth process with ${\lambda }_n=n\lambda$

$P_1(0)=1$, $P_{n>1}(0)=0$
$P_n^{\prime }(t)=(n-1)\lambda P_{n-1}(t)-n\lambda P_n(t)$

We can derive $P_n(t)=e^{-\lambda t}[1-e^{-\lambda t}{]}^{n-1}$ for $n\ge 1$
This looks like a geometric distribution with parameter $e^{-\lambda t}$, so we know that $\mathbb{E}(X_t)={\sum }_{n=1}^{\infty }n{P}_n(t)=e^{\lambda t}$

Another way to see this: Consider the time $Y_n$ when the population first reaches $n$. $Y_n=T_1+\cdots +T_{n-1}$, where $T_i$ is an exponential variable with parameter $i\lambda$

It follows $\mathbb{E}(Y_n)={\sum }_{i=1}^{n-1}\frac{1}{i\lambda }\sim \frac{\ln n}{\lambda }$ and $\text{Var}(Y_n)\le {\sum }_{i=1}^{\infty }(i\lambda {)}^{-2}<\infty$, so $Y_n$ equals $\ln n/\lambda$ up to a small random, bounded error. If it takes $\ln n/\lambda$ time to reach $n$ individuals, then in time $t$ we expect $e^{\lambda t}$ individuals

Example:
Consider ${\lambda }_n=n^2\lambda$
$Y_{\infty }=T_1+T_2+T_3+\dots$

$\mathbb{E}(Y_{\infty })={\sum }_{i=1}^{\infty }\mathbb{E}(T_i)={\sum }_{i=1}^{\infty }\frac{1}{i^2\lambda }<\infty$
Amazingly, this means the population grows to an infinite size in finite time! This is often called explosion

General Continuous, Countable Chains

Suppose we have a countable state space $S$ and rates $\alpha (x,y)$

If $\alpha (x)={\sum }_{y\ne x}^{}\alpha (x,y)<\infty$ we have $\mathbb{P}\{X_{t+\Delta t}=y\mid X_t=x\}=\alpha (x,y)\Delta t+o_x(\Delta t)$

First assume that explosion does not occur. We derive differential equations with Chapman-Kolmogorov,
Forward equations: $p_t^{\prime }(x,y)=-p_t(x,y)\alpha (y)+{\sum }_{z\ne y}^{}{p}_t(x,z)\alpha (z,y)$
Backward equations: $p_t^{\prime }(x,y)=-\alpha (x)p_t(x,y)+{\sum }_{z\ne x}^{}\alpha (x,z)p_t(z,y)$

The forward equations usually are justified, but sometimes the backwards equations are necessary

As we’ve seen, the case of finite state can be solved as ${\mathbf{P}}_t=e^{t\mathbf{A}}$