Editing Queueing theory (section)

=== Birth-death process ===
{{See also|Survival analysis}}
The behaviour of a single queue (also called a ''queueing node'') can be described by a [[birth–death process]], which describes the arrivals and departures from the queue, along with the number of jobs currently in the system. If ''k'' denotes the number of jobs in the system (either being serviced or waiting if the queue has a buffer of waiting jobs), then an arrival increases ''k'' by 1 and a departure decreases ''k'' by 1.

The system transitions between values of ''k'' by "births" and "deaths", which occur at the arrival rates <math>\lambda_i</math> and the departure rates <math>\mu_i</math> for each job <math>i</math>. For a queue, these rates are generally considered not to vary with the number of jobs in the queue, so a single [[average]] rate of arrivals/departures per unit time is assumed. Under this assumption, this process has an arrival rate of <math>\lambda = \text{avg}(\lambda_1,\lambda_2,\dots,\lambda_k)</math> and a departure rate of <math>\mu = \text{avg}(\mu_1, \mu_2, \dots, \mu_k)</math>.

[[File:BD-proces.png|thumb|center|643x643px|A birth–death process. The values in the circles represent the state of the system, which evolves based on arrival rates ''λ<sub>i</sub>'' and departure rates ''μ<sub>i</sub>''.]]

[[File:Mm1_queue.svg|thumb|center|250px|A queue with 1 server, arrival rate ''λ'' and departure rate ''μ'']]

==== Balance equations ====

The [[steady state]] equations for the birth-and-death process, known as the [[balance equation]]s, are as follows. Here <math>P_n</math> denotes the steady state probability to be in state ''n''.

: <math>\mu_1 P_1 = \lambda_0 P_0</math>
: <math>\lambda_0 P_0 + \mu_2 P_2 = (\lambda_1 + \mu_1) P_1</math>
: <math>\lambda_{n-1} P_{n-1} + \mu_{n+1} P_{n+1} = (\lambda_n + \mu_n) P_n</math>

The first two equations imply
: <math>P_1 = \frac{\lambda_0}{\mu_1} P_0</math>
and
: <math>P_2 = \frac{\lambda_1}{\mu_2} P_1 + \frac{1}{\mu_2} (\mu_1 P_1 - \lambda_0 P_0) = \frac{\lambda_1}{\mu_2} P_1 = \frac{\lambda_1 \lambda_0}{\mu_2 \mu_1} P_0</math>.

By mathematical induction,
: <math>P_n = \frac{\lambda_{n-1} \lambda_{n-2} \cdots \lambda_0}{\mu_n \mu_{n-1} \cdots \mu_1} P_0 = P_0 \prod_{i = 0}^{n-1} \frac{\lambda_i}{\mu_{i+1}}</math>.

The condition <math>\sum_{n = 0}^{\infty} P_n = P_0 + P_0 \sum_{n=1}^\infty \prod_{i=0}^{n-1} \frac{\lambda_i}{\mu_{i+1}} = 1</math> leads to
: <math>P_0 = \frac{1}{1 + \sum_{n=1}^{\infty}\prod_{i=0}^{n-1} \frac{\lambda_i}{\mu_{i+1}} }</math>
which, together with the equation for <math>P_n</math> <math>(n\geq1)</math>, fully describes the required steady state probabilities.