Page 197 - A First Course In Stochastic Models

190 MARKOV CHAINS AND QUEUES

with D n denoting the delay in queue of the nth customer. The existence of the
limit will be shown below. It holds that

W q (x) = 1 − ρe −µ(1−ρ)x , x ≥ 0. (5.1.5)

A key step in the proof is the observation that the conditional delay in queue of
a customer finding j other customers present upon arrival has an Erlang (j, µ)
distribution for j ≥ 1. This follows by noting that the delay in queue of this
customer is the sum of j independent exponential random variables with the same
mean 1/µ (the remaining service time of the customer found in service also has
an exponential distribution with mean 1/µ). The probability distribution function
j−1 −µx k

of the Erlang (j, µ) distribution is given by 1− k=0 e (µx) /k!. Denoting by
(n)
π the probability that the nth arriving customer finds j other customers present
j
upon arrival, it follows that
j−1
∞ k
(n) −µx
(µx)
P {D n > x} = π e , x ≥ 0. (5.1.6)
j k!
j=1 k=0
The embedded Markov chain describing the number of customers present just
before the arrival epoch is irreducible and has the property that all states are ape-
(n)
riodic and positive recurrent. Thus lim n→∞ π exists and equals π j for all j; see
j
also relation (3.5.11). Using the bounded convergence theorem from Appendix A,
it now follows that lim n→∞ P {D n > x} exists and is given by
∞ j−1 k
−µx (µx)
lim P {D n > x} = π j e , x ≥ 0. (5.1.7)
n→∞ k!
j=1 k=0
To obtain (5.1.5) from (5.1.7), we use (5.1.2) and (5.1.3). This gives
∞ j−1 k ∞ ∞
−µx (µx) −µx (µx) k
1 − W q (x) = π j e = e π j
k! k!
j=1 k=0 k=0 j=k+1
∞ k ∞ k
−µx (µx) k+1 −µx (µρx) −µx µρx
= e ρ = ρe = ρe e ,
k! k!
k=0 k=0
which verifies (5.1.5). It is noted that the probability W q (x) can also be interpreted
as the long-run fraction of customers whose delay in queue is no more than x.

5.1.2 The M/M/c Queue
The analysis of the multi-server M/M/c queue is a rather straightforward extension
of the analysis of the M/M/1 queue. The transition rate diagram for the {X(t)}
process is given in Figure 5.1.2.