6.4 Birth-death process

< Free Open Study >

The Poisson stochastic processes are related to a more general family of stochastic processes called birth-death processes. In birth-death stochastic processes we are concerned with a state space of random variables where the values range from 0, representing no members in the population, up to potentially an infinite number, representing a constantly growing population. More realistically we are interested in fixed-size populations that go through incremental additions to the population (births) and incremental deletions from the population (deaths).

For any specific level (possible range of values or specific number) in the population there is an associated birth rate and a death rate. This rate may be constant for each level but need not be. The birth-death stochastic process is described as a continuous parameter (index set) discrete state space stochastic process (Figure 6.8).

click to expand
Figure 6.8: Example birth-death process.

(6.15)

E(n), n = 0, 1, 2, ... describes the state and x(t) = n means x(t) is in state E(n) at time t.

For any stochastic process, x(t) t ≥ 0, to be a birth-death stochastic process, the process must be a discrete state space continuous parameter stochastic process, and it must have the following additional properties:

State changes are only in increments of ±1 and the value of E_n is never negative.
If the system is in state E_n at time t, the probability of a transition to E_n₊₁ during the interval (t, t+ h) is:

λ_nh + o(h)

and to E_n-₁ is:

μ_nh+ o(h).
The probability of more than one transition during an interval of length h is o(h).

If we examine a birth-death process from any particular state, E_n, we can see that we enter the state from only two other locations: either from state E_n+1 or E_n-₁ (Figure 6.9).

click to expand
Figure 6.9: Example stochastic process state transition diagram.

Using this knowledge we can compute a variety of important performance measures. All of these measures will be derived from the basis of computing the differential difference equations. These equations examine the birth-death stochastic process from the relationship with the initial state and the flow rates between states. We compute these focused on one node or state, as in Figure 6.9.

(6.16)

be the probability that the system is in state E_n at time t.

What is P_n(t + h) for small h?

(6.17)

Transposing the term P_n(t) and dividing by h:

(6.18)

Taking the limit as h → 0:

(6.19)

Equation 6.19 gives the relationship of the initial state to the first state and the initial birth and death rate. We will see the importance of this simple property of the birth-death stochastic process as we continue our development of this stochastic process and apply this to analyzing computer systems as simple queues and networks of queues.

One specialized example of the birth-death process looks at the condition when there are only births and no deaths, and, further, the birth rate is independent of the state and constant. More specifically, we make the following assumptions:

There is a birth rate with mean rate λ_n = λ > 0.
There are no deaths; therefore, the death rate is μ_n = 0.

Using this information and the basic birth-death analysis previously described, we can show that:

(6.20)

The probability of being in any state is:

(6.21)

which indicates that this is a Poisson process. The Poisson process can be modeled as a pure birth process with constant birth rate.

The general case birth-death process is a bit more complicated when finding time-dependent solutions. If, however, we look at the point where the system is nearing some limiting value, then the system can be assumed to be stationary and, therefore, equilibrium solutions exist for the system. In these equilibrium or steady-state solutions, we assume:

(6.22)

and

(6.23)

We can focus on the various states and compute the differential difference equations from a general node (any n ≥ 1) and for the initial state n = 0, as:

(6.24)
(6.25)

The solution for these differential difference equations, using a bit of algebra, is shown as:

(6.26)

and

The solutions described here focus on the use of balance equations to solve for the various state probabilities. Balance equations can be used, since we assume the system has reached equilibrium and, therefore, will migrate between stable states; no matter which state we happen to look at, this will hold. The balance equations examine each state, E_n, once equilibrium is reached; the rate of transition into state E_n and the rate of transition out of E_n are computed such that:

Rate of entering E_n = rate of leaving E_n

From the birth-death process we find that:

(6.27)
(6.28)

Also:

(6.29)

A graphical representation for the birth-death process is shown in Figure 6.10.

click to expand
Figure 6.10: Graphical representation for the birth-death process.

The rate transition diagram of an equilibrium analysis for a single server with no waiting line is shown in Figure 6.11. The example has Poisson arrivals with a rate of λ and exponential service with a rate of μ. The balance equations for this example are:

(6.30)

Figure 6.11: Transition rate diagram.

and

p₁ + p₀ = 1

Solving the balance equations yields:

(6.31)

Therefore:

(6.32)

The importance of this initial overview of the birth and death stochastic process, the representation of this process using transition rate diagrams, and the assumption of equilibrium and solution techniques using equilibrium will make more sense as we begin to look at general representations and mappings to computer systems.

< Free Open Study >