Page 362 - A First Course In Stochastic Models

THE M/G/1 QUEUE 357

We give only a sketch of the proof. Let the random variable D (∞) have W q (x) as
probability distribution function. By relation (E.8) in Appendix E,
−sD (∞)
∞ 1 − E(e )
−sx
e {1 − W q (x)} dx = .
0 s
To find E(e −sD (∞) ), let the random variable U n be 0 if the server is idle upon the
nth arrival and let U n be the remaining service time of the service in progress upon
the epoch of the nth arrival otherwise. Under the LCFS discipline, the delay D n of
the nth arrival depends only on U n . The random variable D n has a positive mass
at x = 0. Thus
E(e −sD n ) = P {U n = 0} + E(e −sD n | U n > 0)P {U n > 0}.

Next the following observation is made. Under the condition that U n = u and that
k new customers arrive during the remaining service time u, the delay in queue of
k
the nth arrival is distributed as u + B i , where B 1 , . . . , B k are independent
i=1
random variables each distributed as the length of a busy period. Hence
∞ k
∗
−λu (λu) −su k −[s+λ(1−β (s))]u
E(e −sD n | U n = u) = e e [β (s)] = e .
∗
k!
k=0
Define now the random variable R t as the remaining service time of the service
in progress at time t given that the server is busy at time t. Using the PASTA
property, it follows that
lim P {U n = 0} = 1 − ρ and lim P {U n ≤ u | U n > 0} = lim P {R t ≤ u}.
n→∞ n→∞ t→∞
Using the result
1 u
lim P {R t ≤ u} = {1 − B(y)} dy, u ≥ 0, (9.2.32)
t→∞ E(S) 0
it is a matter of some algebra to verify that

∗
E(e −sD (∞) ) = lim E(e −sD n ) = 1 − ρ + λ(1 − β (s)) .
∗
n→∞ s + λ − λβ (s)
This result gives (9.2.31). A remark is made about the important result (9.2.32).
It is tempting to conclude this result by considering only those times when the
server is busy and next using the equilibrium excess distribution from renewal
theory; see Theorem 8.2.5. However, more subtle renewal-theoretic arguments are
needed to prove (9.2.32). A probabilistic proof is as follows. Fix u ≥ 0. Let the
random variable I (t) = 1 if the server is busy at time t and the remaining service
time of the service in progress is larger than u and let I (t) = 0 otherwise. The
stochastic process {I (t)} is regenerative. The regeneration epochs are the service
completion epochs at which the server becomes idle. The length of a regeneration