Page 200 - A First Course In Stochastic Models

THE ERLANG DELAY MODEL 193

Burke’s output theorem For any k ≥ 1,

lim P {T n+1 − T n ≤ x 1 , . . . , T n+k − T n+k−1 ≤ x k }
n→∞
= (1 − e −λx 1 ) · · · (1 − e −λx k ) for all x 1 , . . . , x k ≥ 0.

In other words, in statistical equilibrium the process describing the departures of
served customers is a Poisson process with rate λ.

We first give a heuristic argument for this result. If at a given time t there are
i customers present, then the probability that in (t, t + t) a service is completed
equals min(i, c)µ t + o( t) for t → 0. The equilibrium probability of being in
state i at an arbitrary point in time is given by p i . Assuming that the process is
in statistical equilibrium, it follows that the probability of a customer leaving in
(t, t + t) is given by

c−1 ∞ c−1 ∞

iµ tp i + cµ tp i + o( t) = ip i + c p i µ t + o( t)
i=0 i=c i=0 i=c
as t → 0. The expression between brackets gives the long-run average number
of busy servers and is thus equal to cρ by Little’s formula. Since ρ = λ/(cµ) it
follows that the probability of a customer leaving in (t, t + t) equals
cρµ t + o( t) = λ t + o( t)

as t → 0. This indicates that the departure process of customers is indeed a
Poisson process with rate λ when the M/M/c system has reached statistical equi-
librium. This result is of utmost importance for tandem queues when the first station
in the tandem queue is described by an M/M/c system.

Time reversibility

The practically useful result that the output process of an M/M/c queue is a Pois-
son process can be given a firm basis by the important concept of time reversibility.
Consider a continuous-time Markov chain {X(t)} that satisfies Assumption 4.2.1
and has the property that all states communicate with each other. The continuous-
time Markov chain {X(t)} is said to satisfy detailed balance if its unique equilib-
rium distribution {p j } has the property that

p k q kj = p j q jk for all j, k ∈ I with j = k. (5.1.15)
In other words, the long-run average number of transitions from state k to state j
per time unit is equal to the long-run average number of transitions from state j
to state k per time unit for all j = k. Detailed balance is intimately related to time
reversibility. A convenient way to characterize time reversibility is to consider the
stationary version of the Markov chain {X(t)}. In the stationary version the initial
state at time t = 0 is chosen according to the equilibrium distribution {p j }. For the