Birth–death process

Conditions for recurrence and transience were established by Samuel Karlin and James McGregor.[2]

A birth-and-death process is recurrent if and only if

${\displaystyle \sum _{i=1}^{\infty }\prod _{n=1}^{i}{\frac {\mu _{n}}{\lambda _{n}}}=\infty .}$

A birth-and-death process is ergodic if and only if

${\displaystyle \sum _{i=1}^{\infty }\prod _{n=1}^{i}{\frac {\mu _{n}}{\lambda _{n}}}=\infty \quad {\text{and}}\quad \sum _{i=1}^{\infty }\prod _{n=1}^{i}{\frac {\lambda _{n-1}}{\mu _{n}}}<\infty .}$

A birth-and-death process is null-recurrent if and only if

${\displaystyle \sum _{i=1}^{\infty }\prod _{n=1}^{i}{\frac {\mu _{n}}{\lambda _{n}}}=\infty \quad {\text{and}}\quad \sum _{i=1}^{\infty }\prod _{n=1}^{i}{\frac {\lambda _{n-1}}{\mu _{n}}}=\infty .}$

By using Extended Bertrand's test (see Section 4.1.4 from Ratio test) the conditions for recurrence, transience, ergodicity and null-recurrence can be derived in a more explicit form.[3]

For integer ${\displaystyle K\geq 1,}$ let ${\displaystyle \ln _{(K)}(x)}$ denote the ${\displaystyle K}$th iterate of natural logarithm, i.e. ${\displaystyle \ln _{(1)}(x)=\ln(x)}$ and for any ${\displaystyle 2\leq k\leq K}$, ${\displaystyle \ln _{(k)}(x)=\ln _{(k-1)}(\ln(x))}$.

Then, the conditions for recurrence and transience of a birth-and-death process are as follows.

The birth-and-death process is transient if there exist ${\displaystyle c>1,}$ ${\displaystyle K\geq 1}$ and ${\displaystyle n_{0}}$ such that for all ${\displaystyle n>n_{0}}$

${\displaystyle {\frac {\lambda _{n}}{\mu _{n}}}\geq 1+{\frac {1}{n}}+{\frac {1}{n}}\sum _{k=1}^{K-1}{\frac {1}{\prod _{j=1}^{k}\ln _{(j)}(n)}}+{\frac {c}{n\prod _{j=1}^{K}\ln _{(j)}(n)}},}$

where the empty sum for ${\displaystyle K=1}$ is assumed to be 0.

The birth-and-death process is recurrent if there exist ${\displaystyle K\geq 1}$ and ${\displaystyle n_{0}}$ such that for all ${\displaystyle n>n_{0}}$

${\displaystyle {\frac {\lambda _{n}}{\mu _{n}}}\leq 1+{\frac {1}{n}}+{\frac {1}{n}}\sum _{k=1}^{K}{\frac {1}{\prod _{j=1}^{k}\ln _{(j)}(n)}}.}$

Wider classes of birth-and-death processes, for which the conditions for recurrence and transience can be established, can be found in.[4]

Consider one-dimensional random walk ${\displaystyle S_{t},\ t=0,1,\ldots ,}$ that is defined as follows. Let ${\displaystyle S_{0}=1}$, and ${\displaystyle S_{t}=S_{t-1}+e_{t},\ t\geq 1,}$ where ${\displaystyle e_{t}}$ takes values ${\displaystyle \pm 1}$, and the distribution of ${\displaystyle S_{t}}$ is defined by the following conditions:

${\displaystyle {\mathsf {P}}\{S_{t+1}=S_{t}+1|S_{t}>0\}={\frac {1}{2}}+{\frac {\alpha _{S_{t}}}{S_{t}}},\quad {\mathsf {P}}\{S_{t+1}=S_{t}-1|S_{t}>0\}={\frac {1}{2}}-{\frac {\alpha _{S_{t}}}{S_{t}}},\quad {\mathsf {P}}\{S_{t+1}=1|S_{t}=0\}=1,}$

where ${\displaystyle \alpha _{n}}$ satisfy the condition ${\displaystyle 0<\alpha _{n}<\min\{C,n/2\},C>0}$.

The random walk described here is a discrete time analogue of the birth-and-death process (see Markov chain) with the birth rates

${\displaystyle \lambda _{n}={\frac {1}{2}}+{\frac {\alpha _{n}}{n}},}$

and the death rates

${\displaystyle \mu _{n}={\frac {1}{2}}-{\frac {\alpha _{n}}{n}}}$.

So, recurrence or transience of the random walk is associated with recurrence or transience of the birth-and-death process.[3]

The random walk is transient if there exist ${\displaystyle c>1}$, ${\displaystyle K\geq 1}$ and ${\displaystyle n_{0}}$ such that for all ${\displaystyle n>n_{0}}$

${\displaystyle \alpha _{n}\geq {\frac {1}{4}}\left(1+\sum _{k=1}^{K-1}\prod _{j=1}^{k}{\frac {1}{\ln _{(j)}(n)}}+c\prod _{j=1}^{K}{\frac {1}{\ln _{(j)}(n)}}\right),}$

where the empty sum for ${\displaystyle K=1}$ is assumed to be zero.

The random walk is recurrent if there exist ${\displaystyle K\geq 1}$ and ${\displaystyle n_{0}}$ such that for all ${\displaystyle n>n_{0}}$

${\displaystyle \alpha _{n}\leq {\frac {1}{4}}\left(1+\sum _{k=1}^{K}\prod _{j=1}^{k}{\frac {1}{\ln _{(j)}(n)}}\right).}$

The M/M/1 is a single server queue with an infinite buffer size. In a non-random environment the birth–death process in queueing models tend to be long-term averages, so the average rate of arrival is given as ${\displaystyle \lambda }$ and the average service time as ${\displaystyle 1/\mu }$. The birth and death process is an M/M/1 queue when,

${\displaystyle \lambda _{i}=\lambda {\text{ and }}\mu _{i}=\mu {\text{ for all }}i.\,}$

The differential equations for the probability that the system is in state k at time t are

${\displaystyle p_{0}^{\prime }(t)=\mu p_{1}(t)-\lambda p_{0}(t),\,}$

${\displaystyle p_{k}^{\prime }(t)=\lambda p_{k-1}(t)+\mu p_{k+1}(t)-(\lambda +\mu )p_{k}(t)\quad {\text{for }}k=1,2,\ldots \,}$

Pure birth process with ${\displaystyle \lambda _{k}\equiv \lambda }$ is a particular case of the M/M/1 queueing process. We have the following system of differential equations:

${\displaystyle p_{0}^{\prime }(t)=-\lambda p_{0}(t),\,}$

${\displaystyle p_{k}^{\prime }(t)=\lambda p_{k-1}(t)-\lambda p_{k}(t)\quad {\text{for }}k=1,2,\ldots \,}$

Under the initial condition ${\displaystyle p_{0}(0)=1}$ and ${\displaystyle p_{k}(0)=0,\ k=1,2,\ldots }$, the solution of the system is

${\displaystyle p_{k}(t)={\frac {(\lambda t)^{k}}{k!}}\mathrm {e} ^{-\lambda t}.}$

That is, a (homogeneous) Poisson process is a pure birth process.

The M/M/C is a multi-server queue with C servers and an infinite buffer. It characterizes by the following birth and death parameters:

${\displaystyle \mu _{i}=i\mu \quad {\text{ for }}i\leq C-1,\,}$

and

${\displaystyle \mu _{i}=C\mu \quad {\text{ for }}i\geq C,\,}$

with

${\displaystyle \lambda _{i}=\lambda \quad {\text{ for all }}i.\,}$

The system of differential equations in this case has the form:

${\displaystyle p_{0}^{\prime }(t)=\mu p_{1}(t)-\lambda p_{0}(t),\,}$

${\displaystyle p_{k}^{\prime }(t)=\lambda p_{k-1}(t)+(k+1)\mu p_{k+1}(t)-(\lambda +k\mu )p_{k}(t)\quad {\text{for }}k=1,2,\ldots ,C-1,\,}$

${\displaystyle p_{k}^{\prime }(t)=\lambda p_{k-1}(t)+C\mu p_{k+1}(t)-(\lambda +C\mu )p_{k}(t)\quad {\text{for }}k\geq C.\,}$

Pure death process with ${\displaystyle \mu _{k}=k\mu }$ is a particular case of the M/M/C queueing process. We have the following system of differential equations:

${\displaystyle p_{C}^{\prime }(t)=-C\mu p_{C}(t),\,}$

${\displaystyle p_{k}^{\prime }(t)=(k+1)\mu p_{k+1}(t)-k\mu p_{k}(t)\quad {\text{for }}k=0,1,\ldots ,C-1.\,}$

Under the initial condition ${\displaystyle p_{C}(0)=1}$ and ${\displaystyle p_{k}(0)=0,\ k=0,1,\ldots ,C-1,}$ we obtain the solution

${\displaystyle p_{k}(t)={\binom {C}{k}}\mathrm {e} ^{-k\mu t}\left(1-\mathrm {e} ^{-\mu t}\right)^{C-k},}$

that presents the version of binomial distribution depending on time parameter ${\displaystyle t}$ (see Binomial process).

The M/M/1/K queue is a single server queue with a buffer of size K. This queue has applications in telecommunications, as well as in biology when a population has a capacity limit. In telecommunication we again use the parameters from the M/M/1 queue with,

${\displaystyle \lambda _{i}=\lambda \quad {\text{ for }}0\leq i<K,\,}$

${\displaystyle \lambda _{i}=0\quad {\text{ for }}i\geq K,\,}$

${\displaystyle \mu _{i}=\mu \quad {\text{ for }}1\leq i\leq K.\,}$

In biology, particularly the growth of bacteria, when the population is zero there is no ability to grow so,

${\displaystyle \lambda _{0}=0.\,}$

Additionally if the capacity represents a limit where the individual dies from over population,

${\displaystyle \mu _{K}=0.\,}$

The differential equations for the probability that the system is in state k at time t are

${\displaystyle p_{0}^{\prime }(t)=\mu p_{1}(t)-\lambda p_{0}(t),}$

${\displaystyle p_{k}^{\prime }(t)=\lambda p_{k-1}(t)+\mu p_{k+1}(t)-(\lambda +\mu )p_{k}(t)\quad {\text{ for }}k\leq K-1,\,}$

${\displaystyle p_{K}^{\prime }(t)=\lambda p_{K-1}(t)-(\lambda +\mu )p_{K}(t),\,}$

${\displaystyle p_{k}(t)=0\quad {\text{ for }}k>K.\,}$