Birth–death process

Short description: Special type of continuous-time Markov process

The birth–death process (or birth-and-death process) is a special case of continuous-time Markov process where the state transitions are of only two types: "births", which increase the state variable by one and "deaths", which decrease the state by one. It was introduced by William Feller.Cite error: Closing `</ref>` missing for `<ref>` tag

For integer [math]\displaystyle{ K\geq1, }[/math] let [math]\displaystyle{ \ln_{(K)}(x) }[/math] denote the [math]\displaystyle{ K }[/math]th iterate of natural logarithm, i.e. [math]\displaystyle{ \ln_{(1)}(x)=\ln (x) }[/math] and for any [math]\displaystyle{ 2\leq k\leq K }[/math], [math]\displaystyle{ \ln_{(k)}(x)=\ln_{(k-1)}(\ln (x)) }[/math].

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 [math]\displaystyle{ c \gt 1, }[/math] [math]\displaystyle{ K\geq1 }[/math] and [math]\displaystyle{ n_0 }[/math] such that for all [math]\displaystyle{ n \gt n_0 }[/math]

[math]\displaystyle{ \frac{\lambda_n}{\mu_n}\geq1+\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)}, }[/math]

where the empty sum for [math]\displaystyle{ K=1 }[/math] is assumed to be 0.

The birth-and-death process is recurrent if there exist [math]\displaystyle{ K\geq1 }[/math] and [math]\displaystyle{ n_0 }[/math] such that for all [math]\displaystyle{ n \gt n_0 }[/math]

[math]\displaystyle{ \frac{\lambda_n}{\mu_n}\leq1+\frac{1}{n}+\frac{1}{n}\sum_{k=1}^{K}\frac{1}{\prod_{j=1}^k\ln_{(j)}(n)}. }[/math]

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

## Contents

* 1 Application
* 2 Stationary solution
* 3 Examples of birth-death processes
* 4 Use in phylodynamics
* 5 Use in queueing theory
* 5.1 M/M/1 queue
* 5.2 Pure birth process associated with an M/M/1 queue
* 5.3 M/M/c queue
* 5.4 Pure death process associated with an M/M/C queue
* 5.5 M/M/1/K queue
* 6 Equilibrium
* 7 Bilateral birth-and-death process
* 8 See also
* 9 Notes
* 10 References

### Application

Consider one-dimensional random walk [math]\displaystyle{ S_t, \ t=0,1,\ldots, }[/math] that is defined as follows. Let [math]\displaystyle{ S_0=1 }[/math], and [math]\displaystyle{ S_t=S_{t-1}+e_t, \ t\geq1, }[/math] where [math]\displaystyle{ e_t }[/math] takes values [math]\displaystyle{ \pm1 }[/math], and the distribution of [math]\displaystyle{ S_t }[/math] is defined by the following conditions:

[math]\displaystyle{ \mathsf{P}\\{S_{t+1}=S_t+1|S_t\gt 0\\}=\frac{1}{2}+\frac{\alpha_{S_t}}{S_t}, \quad \mathsf{P}\\{S_{t+1}=S_t-1|S_t\gt 0\\}=\frac{1}{2}-\frac{\alpha_{S_t}}{S_t}, \quad \mathsf{P}\\{S_{t+1}=1|S_t=0\\}=1, }[/math]

where [math]\displaystyle{ \alpha_n }[/math] satisfy the condition [math]\displaystyle{ 0\lt \alpha_n\lt \min\\{C, n/2\\}, C\gt 0 }[/math].

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

[math]\displaystyle{ \lambda_n=\frac{1}{2}+\frac{\alpha_{n}}{n}, }[/math]

and the death rates

[math]\displaystyle{ \mu_n=\frac{1}{2}-\frac{\alpha_{n}}{n} }[/math].

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

The random walk is transient if there exist [math]\displaystyle{ c\gt 1 }[/math], [math]\displaystyle{ K\geq1 }[/math] and [math]\displaystyle{ n_0 }[/math] such that for all [math]\displaystyle{ n\gt n_0 }[/math]

[math]\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), }[/math]

where the empty sum for [math]\displaystyle{ K=1 }[/math] is assumed to be zero.

The random walk is recurrent if there exist [math]\displaystyle{ K\geq1 }[/math] and [math]\displaystyle{ n_0 }[/math] such that for all [math]\displaystyle{ n\gt n_0 }[/math]

[math]\displaystyle{ \alpha_n\leq\frac{1}{4}\left(1+\sum_{k=1}^{K}\prod_{j=1}^k\frac{1}{\ln_{(j)}(n)}\right). }[/math]

## Stationary solution

If a birth-and-death process is ergodic, then there exists steady-state probabilities [math]\displaystyle{ \pi_k=\lim_{t\to\infty}p_k(t), }[/math] where [math]\displaystyle{ p_k(t) }[/math] is the probability that the birth-and-death process is in state [math]\displaystyle{ k }[/math] at time [math]\displaystyle{ t. }[/math] The limit exists, independent of the initial values [math]\displaystyle{ p_k(0), }[/math] and is calculated by the relations:

[math]\displaystyle{ \pi_k=\pi_0\prod_{i=1}^k\frac{\lambda_{i-1}}{\mu_i},\quad k=1,2,\ldots, }[/math]
[math]\displaystyle{ \pi_0=\frac{1}{1+\sum_{k=1}^\infty\prod_{i=1}^k\frac{\lambda_{i-1}}{\mu_i}}. }[/math]

These limiting probabilities are obtained from the infinite system of differential equations for [math]\displaystyle{ p_k(t): }[/math]

[math]\displaystyle{ p_0^\prime(t)=\mu_1 p_1(t)-\lambda_0 p_0(t) \, }[/math]
[math]\displaystyle{ p_k^\prime(t)=\lambda_{k-1} p_{k-1}(t)+\mu_{k+1} p_{k+1}(t)-(\lambda_k +\mu_k) p_k(t), k=1,2,\ldots, \, }[/math]

and the initial condition [math]\displaystyle{ \sum_{k=0}^\infty p_k(t)=1. }[/math]

In turn, the last system of differential equations is derived from the system of difference equations that describes the dynamic of the system in a small time [math]\displaystyle{ \Delta t }[/math]. During this small time [math]\displaystyle{ \Delta t }[/math] only three types of transitions are considered as one death, or one birth, or no birth nor death. The probability of the first two of these transitions has the order of [math]\displaystyle{ \Delta t }[/math]. Other transitions during this small interval [math]\displaystyle{ \Delta t }[/math] such as more than one birth, or more than one death, or at least one birth and at least one death have the probabilities that are of smaller order than [math]\displaystyle{ \Delta t }[/math], and hence are negligible in derivations. If the system is in state k, then the probability of birth during an interval [math]\displaystyle{ \Delta t }[/math] is [math]\displaystyle{ \lambda_k\Delta t+o(\Delta t) }[/math], the probability of death is [math]\displaystyle{ \mu_k\Delta t+o(\Delta t) }[/math], and the probability of no birth and no death is [math]\displaystyle{ 1-\lambda_k\Delta t-\mu_k\Delta t+o(\Delta t) }[/math]. For a population process, "birth" is the transition towards increasing the population size by 1 while "death" is the transition towards decreasing the population size by 1.

## Examples of birth-death processes

A pure birth process is a birth–death process where [math]\displaystyle{ \mu_{i} = 0 }[/math] for all [math]\displaystyle{ i \ge 0 }[/math].

A pure death process is a birth–death process where [math]\displaystyle{ \lambda_{i} = 0 }[/math] for all [math]\displaystyle{ i \ge 0 }[/math].

M/M/1 model and M/M/c model, both used in queueing theory, are birth–death processes used to describe customers in an infinite queue.

## Use in phylodynamics

Birth–death processes are used in phylodynamics as a prior distribution for phylogenies, i.e. a binary tree in which birth events correspond to branches of the tree and death events correspond to leaf nodes.[3] Notably, they are used in viral phylodynamics[4] to understand the transmission process and how the number of people infected changes through time.[5]

The use of generalized birth-death processes in phylodynamics has stimulated investigations into the degree to which the rates of birth and death can be identified from data.[6] While the model is unidentifiable in general, the subset of models that are typically used are identifiable.[7]

## Use in queueing theory

In queueing theory the birth–death process is the most fundamental example of a queueing model, the M/M/C/K/[math]\displaystyle{ \infty }[/math]/FIFO (in complete Kendall's notation) queue. This is a queue with Poisson arrivals, drawn from an infinite population, and C servers with exponentially distributed service times with K places in the queue. Despite the assumption of an infinite population this model is a good model for various telecommunication systems.

### M/M/1 queue

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 [math]\displaystyle{ \lambda }[/math] and the average service time as [math]\displaystyle{ 1/\mu }[/math]. The birth and death process is an M/M/1 queue when,

[math]\displaystyle{ \lambda_{i}=\lambda\text{ and }\mu_{i}=\mu\text{ for all }i. \, }[/math]

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

[math]\displaystyle{ p_0^\prime(t)=\mu p_1(t)-\lambda p_0(t), \, }[/math]
[math]\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 \, }[/math]

### Pure birth process associated with an M/M/1 queue

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

[math]\displaystyle{ p_0^\prime(t)=-\lambda p_0(t), \, }[/math]
[math]\displaystyle{ p_k^\prime(t)=\lambda p_{k-1}(t)-\lambda p_k(t) \quad \text{for } k=1,2,\ldots \, }[/math]

Under the initial condition [math]\displaystyle{ p_0(0)=1 }[/math] and [math]\displaystyle{ p_k(0)=0, \ k=1,2,\ldots }[/math], the solution of the system is

[math]\displaystyle{ p_k(t)=\frac{(\lambda t)^k}{k!}\mathrm{e}^{-\lambda t}. }[/math]

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

### M/M/c queue

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:

[math]\displaystyle{ \mu_i = i\mu \quad \text{ for }i\leq C-1, \, }[/math]

and

[math]\displaystyle{ \mu_i = C\mu \quad \text{ for }i\geq C, \, }[/math]

with

[math]\displaystyle{ \lambda_i = \lambda \quad \text{ for all }i. \, }[/math]

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

[math]\displaystyle{ p_0^\prime(t)=\mu p_1(t)-\lambda p_0(t), \, }[/math]
[math]\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, \, }[/math]
[math]\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. \, }[/math]

### Pure death process associated with an M/M/C queue

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

[math]\displaystyle{ p_C^\prime(t)=-C\mu p_C(t), \, }[/math]
[math]\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. \, }[/math]

Under the initial condition [math]\displaystyle{ p_C(0)=1 }[/math] and [math]\displaystyle{ p_k(0)=0, \ k=0,1,\ldots, C-1, }[/math] we obtain the solution

[math]\displaystyle{ p_k(t)=\binom{C}{k}\mathrm{e}^{-k\mu t}\left(1-\mathrm{e}^{-\mu t}\right)^{C-k}, }[/math]

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

### M/M/1/K queue

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,

[math]\displaystyle{ \lambda_i = \lambda \quad \text{ for }0 \leq i \lt K, \, }[/math]

[math]\displaystyle{ \lambda_i=0 \quad \text{ for }i\geq K, \, }[/math]

[math]\displaystyle{ \mu_i=\mu \quad \text{ for }1 \leq i \leq K. \, }[/math]

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

[math]\displaystyle{ \lambda_0=0. \, }[/math]

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

[math]\displaystyle{ \mu_K = 0. \, }[/math]

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

[math]\displaystyle{ p_0^\prime(t)=\mu p_1(t)-\lambda p_0(t), }[/math]
[math]\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, \, }[/math]
[math]\displaystyle{ p_K^\prime(t)=\lambda p_{K-1}(t)-(\lambda +\mu) p_K(t), \, }[/math]
[math]\displaystyle{ p_k(t)=0 \quad \text{ for }k \gt K. \, }[/math]

## Equilibrium

A queue is said to be in equilibrium if the steady state probabilities [math]\displaystyle{ \pi_k=\lim_{t \to \infty}p_k(t), \ k=0,1,\ldots, }[/math] exist. The condition for the existence of these steady-state probabilities in the case of M/M/1 queue is [math]\displaystyle{ \rho=\lambda/\mu\lt 1 }[/math] and in the case of M/M/C queue is [math]\displaystyle{ \rho=\lambda/(C\mu)\lt 1 }[/math]. The parameter [math]\displaystyle{ \rho }[/math] is usually called load parameter or utilization parameter. Sometimes it is also called traffic intensity.

Using the M/M/1 queue as an example, the steady state equations are

[math]\displaystyle{ \lambda \pi_0=\mu \pi_1, \, }[/math]

[math]\displaystyle{ (\lambda +\mu) \pi_k=\lambda \pi_{k-1}+\mu \pi_{k+1}. \, }[/math]

This can be reduced to

[math]\displaystyle{ \lambda \pi_k=\mu \pi_{k+1}\text{ for }k\geq 0. \, }[/math]

So, taking into account that [math]\displaystyle{ \pi_0+\pi_1+\ldots=1 }[/math], we obtain

[math]\displaystyle{ \pi_k=(1-\rho)\rho^k. }[/math]

## Bilateral birth-and-death process

Bilateral birth-and-death process is defined similarly to that standard one with the only difference that the birth and death rates [math]\displaystyle{ \lambda_i }[/math] and [math]\displaystyle{ \mu_i }[/math] are defined for the values of index parameter [math]\displaystyle{ i=0,\pm1,\pm2,\ldots }[/math].[8] Following this, a bilateral birth-and-death process is recurrent if and only if

[math]\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}}{\mu_{-n}}=\infty. }[/math]

The notions of ergodicity and null-recurrence are defined similarly by extending the corresponding notions of the standard birth-and-death process.

## See also

* Erlang unit
* Queueing theory
* Queueing models
* Quasi-birth–death process
* Moran process

## Notes

1. ↑ Abramov, Vyacheslav M. (2022). "Necessary and sufficient conditions for the convergence of positive series". Journal of Classical Analysis 19 (2): 117–125. doi:10.7153/jca-2022-19-09. http://files.ele-math.com/articles/jca-19-09.pdf.
2. ↑ Cite error: Invalid `<ref>` tag; no text was provided for refs named `Abr2008`
3. ↑ "Sampling-through-time in birth-death trees". Journal of Theoretical Biology 267 (3): 396–404. December 2010. doi:10.1016/j.jtbi.2010.09.010. PMID 20851708. Bibcode: 2010JThBi.267..396S.
4. ↑ "Phylogenetic and epidemic modeling of rapidly evolving infectious diseases". Infection, Genetics and Evolution 11 (8): 1825–41. December 2011. doi:10.1016/j.meegid.2011.08.005. PMID 21906695.
5. ↑ "A computationally tractable birth-death model that combines phylogenetic and epidemiological data". PLOS Computational Biology 18 (2): e1009805. February 2022. doi:10.1371/journal.pcbi.1009805. PMID 35148311. Bibcode: 2022PLSCB..18E9805Z.
6. ↑ "Extant timetrees are consistent with a myriad of diversification histories". Nature 508 (7804): 502–505. April 2020. doi:10.1038/s41586-020-2176-1. PMID 32322065. Bibcode: 2020Natur.580..502L. https://www.biorxiv.org/content/biorxiv/early/2019/09/14/719435.full.pdf.
7. ↑ "A class of identifiable phylogenetic birth–death models". PNAS 119 (35): e2119513119. August 2022. doi:10.1073/pnas.2119513119. PMID 35994663. Bibcode: 2022PNAS..11919513L.
8. ↑ Pruitt, William E. (1963). "Bilateral birth and death processes". Transactions of the American Mathematical Society 107 (3): 508–525. doi:10.1090/S0002-9947-1963-0150858-0. https://www.ams.org/journals/tran/1963-107-03/S0002-9947-1963-0150858-0/S0002-9947-1963-0150858-0.pdf.

## References

* Latouche, G.; Ramaswami, V. (1999). "Quasi-Birth-and-Death Processes". Introduction to Matrix Analytic Methods in Stochastic Modelling (1st ed.). ASA SIAM. ISBN 0-89871-425-7.
* Nowak, M. A. (2006). Evolutionary Dynamics: Exploring the Equations of Life. Harvard University Press. ISBN 0-674-02338-2.
* Virtamo, J.. "Birth-death processes". 38.3143 Queueing Theory. https://www.netlab.tkk.fi/opetus/s383143/kalvot/E_bdpros.pdf.

* v
* t
* e

Stochastic processes

Discrete time|

* Bernoulli process
* Branching process
* Chinese restaurant process
* Galton–Watson process
* Independent and identically distributed random variables
* Markov chain
* Moran process
* Random walk
* Loop-erased
* Self-avoiding
* Biased
* Maximal entropy

Continuous time|

* Bessel process
* Birth–death process
* Brownian motion
* Bridge
* Excursion
* Fractional
* Geometric
* Meander
* Cauchy process
* Contact process
* Continuous-time random walk
* Cox process
* Diffusion process
* Empirical process
* Feller process
* Fleming–Viot process
* Gamma process
* Geometric process
* Hunt process
* Interacting particle systems
* Itô diffusion
* Itô process
* Jump diffusion
* Jump process
* Lévy process
* Local time
* Markov additive process
* McKean–Vlasov process
* Ornstein–Uhlenbeck process
* Poisson process
* Compound
* Non-homogeneous
* Point process
* Schramm–Loewner evolution
* Semimartingale
* Sigma-martingale
* Stable process
* Superprocess
* Telegraph process
* Variance gamma process
* Wiener process
* Wiener sausage

Both|

* Branching process
* Galves–Löcherbach model
* Gaussian process
* Hidden Markov model (HMM)
* Markov process
* Martingale
* Differences
* Local
* Sub-
* Super-
* Random dynamical system
* Regenerative process
* Renewal process
* Stochastic chains with memory of variable length
* White noise

Fields and other|

* Dirichlet process
* Gaussian random field
* Gibbs measure
* Hopfield model
* Ising model
* Potts model
* Boolean network
* Markov random field
* Percolation
* Pitman–Yor process
* Point process
* Cox
* Poisson
* Random field
* Random graph

Time series models|

* Autoregressive conditional heteroskedasticity (ARCH) model
* Autoregressive integrated moving average (ARIMA) model
* Autoregressive (AR) model
* Autoregressive–moving-average (ARMA) model
* Generalized autoregressive conditional heteroskedasticity (GARCH) model
* Moving-average (MA) model

Financial models|

* Black–Derman–Toy
* Black–Karasinski
* Black–Scholes
* Chen
* Constant elasticity of variance (CEV)
* Cox–Ingersoll–Ross (CIR)
* Garman–Kohlhagen
* Heath–Jarrow–Morton (HJM)
* Heston
* Ho–Lee
* Hull–White
* LIBOR market
* Rendleman–Bartter
* SABR volatility
* Vašíček
* Wilkie

Actuarial models|

* Bühlmann
* Cramér–Lundberg
* Risk process
* Sparre–Anderson

Queueing models|

* Bulk
* Fluid
* Generalized queueing network
* M/G/1
* M/M/1
* M/M/c

Properties|

* Càdlàg paths
* Continuous
* Continuous paths
* Ergodic
* Exchangeable
* Feller-continuous
* Gauss–Markov
* Markov
* Mixing
* Piecewise deterministic
* Predictable
* Progressively measurable
* Self-similar
* Stationary
* Time-reversible

Limit theorems|

* Central limit theorem
* Donsker's theorem
* Doob's martingale convergence theorems
* Ergodic theorem
* Fisher–Tippett–Gnedenko theorem
* Large deviation principle
* Law of large numbers (weak/strong)
* Law of the iterated logarithm
* Maximal ergodic theorem
* Sanov's theorem

Inequalities|

* Burkholder–Davis–Gundy
* Doob's martingale
* Kunita–Watanabe

Tools|

* Cameron–Martin formula
* Convergence of random variables
* Doléans-Dade exponential
* Doob decomposition theorem
* Doob–Meyer decomposition theorem
* Doob's optional stopping theorem
* Dynkin's formula
* Feynman–Kac formula
* Filtration
* Girsanov theorem
* Infinitesimal generator
* Itô integral
* Itô's lemma
* Karhunen–Loève_theorem
* Kolmogorov continuity theorem
* Kolmogorov extension theorem
* Lévy–Prokhorov metric
* Malliavin calculus
* Martingale representation theorem
* Optional stopping theorem
* Prokhorov's theorem
* Quadratic variation
* Reflection principle
* Skorokhod integral
* Skorokhod's representation theorem
* Skorokhod space
* Snell envelope
* Stochastic differential equation
* Tanaka
* Stopping time
* Stratonovich integral
* Uniform integrability
* Usual hypotheses
* Wiener space
* Classical
* Abstract

Disciplines|

* Actuarial mathematics
* Econometrics
* Ergodic theory
* Extreme value theory (EVT)
* Large deviations theory
* Mathematical finance
* Mathematical statistics
* Probability theory
* Queueing theory
* Renewal theory
* Ruin theory
* Statistics
* System on Chip design
* Stochastic analysis
* Time series analysis
* Machine learning

* List of topics
* Category

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Birth–death process. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Birth–death_process&oldid=3361955"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template