Birth-death process

From Wikipedia, the free encyclopedia

The birth-death process is a special case of Continuous-time Markov process where the states represent the current size of a population and where the transitions are limited to births and deaths. Birth-death processes have many application in demography, queueing theory, or in biology, for example to study the evolution of bacteria.

When a birth occurs, the process goes from state n to n+1. When a death occurs, the process goes from state n to state n-1. The process is specified by birth rates $\{\lambda_{i}\}_{i=0..\infty}$ and death rates $\{\mu_{i}\}_{i=1..\infty}$ .

1 Examples of birth-death processes
2 Use in queueing theory
3 Equilibrium
4 Limit behaviour
5 See also
6 References

[edit] Examples of birth-death processes

A pure birth process is a birth-death process where $μ i = 0$ for all $i \ge 0$ .

A pure death process is a birth-death process where $λ i = 0$ for all $i \ge 0$ .

A (homogeneous) Poisson process is a pure birth process where $λ i = λ$ for all $i \ge 0$

A M/M/1 queue is a birth-death process used to describe customers in an infinite queue.

[edit] 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/ $\infty$ /FIF0 (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 time with K places in the queue. Despite the assumption of an infinite population this model is good model for various telecommunciation systems.

[edit] The 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 $λ$ and the average mean service time as $1 / μ$ . The birth and death process is a M/M/1 queue when,

λ i = λ

and

μ i = μ

for all

i

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

$p_0^\prime(t)=\mu_1 p_1(t)-\lambda_0 p_0(t)$

$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)$

[edit] The M/M/C queue

The M/M/C is multi-server queue with C servers and an infinite buffer. This differs from the M/M/1 queue only in the service time which now becomes,

μ i = i μ

for $i\leq C$ and

μ i = C μ

for $i\geq C$ with

λ i = λ

for all

i

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

$p_0^\prime(t)=\mu_1 p_1(t)-\lambda_0 p_0(t)$

$p_k^\prime(t)=\lambda_{k-1} p_{k-1}(t)+(k+1)\mu_{k+1} p_{k+1}(t)-(\lambda_k +\mu_k) p_k(t)$ for $k \leq C-1$

$p_k^\prime(t)=\lambda_{k-1} p_{k-1}(t)+C\mu_{k+1} p_{k+1}(t)-(\lambda_k +\mu_k) p_k(t)$ for $k \geq C$

[edit] The 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,

λ i = λ

for $0 \leq i < K$

λ i = 0

for $i\geq K$

μ i = μ

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,

λ 0 = 0

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

μ K = 0

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

$p_0^\prime(t)=\mu_1 p_1(t)-\lambda_0 p_0(t)$

$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)$ for $k \leq K$

$p_k^\prime(t)=0$ for

k > K

[edit] Equilibrium

A queue is said to be in equilibrium if the limit $\lim_{t \to \infty}p_k(t)$ exists. For this to be the case, $p_k^\prime(t)$ must be zero.

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

λ 0 p 0 (t) = μ 1 p 1 (t)

(λ k + μ k) p k (t) = λ k - 1 p k - 1 (t) + μ k + 1 p k + 1 (t)

If $λ k = λ$ and $μ k = μ$ for all $k$ (the homogenous case), this can be reduced to

λ p k (t) = μ p k + 1 (t)

for $k\geq 0$

[edit] Limit behaviour

In a small time $Δ t$ , only three types of transitions are possible: one death, or one birth, or no birth nor death. If the rate of occurrences (per unit time) of births is $λ$ and that for deaths is $μ$ , then the probabilities of the above transitions are $λΔ t$ , $μΔ t$ , and $1 - (λ + μ)Δ t$ respectively. For a population process, "birth" is the transition towards increasing the population by 1 while "death" is the transition towards decreasing the population size by 1.

[edit] See also

[edit] References

G. Latouche, V. Ramaswami. Introduction to Matrix Analytic Methods in Stochastic Modelling, 1st edition. Chapter 1: Quasi-Birth-and-Death Processes; ASA SIAM, 1999.
M. A. Nowak. Evolutionary Dynamics: Exploring the Equations of Life, Harvard University Press, 2006.

Categories: Stochastic processes | Queueing theory

Birth-death process

From Wikipedia, the free encyclopedia

Contents

[edit] Examples of birth-death processes

[edit] Use in queueing theory

[edit] The M/M/1 queue

[edit] The M/M/C queue

[edit] The M/M/1/K queue

[edit] Equilibrium

[edit] Limit behaviour

[edit] See also

[edit] References

Views

Navigation

Interaction

Search

Languages