Page 359 - A First Course In Stochastic Models

354 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

of the busy period density is determined by the functional equation
∗
∗
∗
β (s) = b (s + λ − λβ (s)), (9.2.25)

∞ −sx
∗
where b (s) = 0 e b(x) dx is the Laplace transform of the probability density
b(x) of the service time of a customer. By relation (E.8) in Appendix E, the Laplace
transform of P {B > x} is given by
∞ 1 − β (s)
∗

−sx
e P {B > x} dx = . (9.2.26)
0 s
The key to the proof of (9.2.25) is the assertion that the amount of time needed to
empty the system when the system starts with n customers present is distributed as
the sum of the lengths of n independent busy periods B 1 , . . . , B n . To see this, note
first that the order of service has no effect on the amount of time needed to empty
the system. Following Tak´ acs (1962), imagine now the following service discipline.
The initial n customers C 1 , . . . , C n are separated. Customer C 1 is served first, after
which all customers (if any) are served who have arrived during the service time
of customer C 1 , and this way of service is continued until the system is free of all
customers but C 2 , . . . , C n . Next this procedure is repeated with customer C 2 , etc.
This verifies the above assertion. The remainder of the proof is now simple. Let
the random variables S 1 and ν 1 denote the length of the service initiating the busy
period and the number of customers arriving during that first service time. Then,
by conditioning on S 1 and ν 1 , we find

∞
∞ (λt) n
E(e −sB ) = e −λt E(e −sB | S 1 = t, ν 1 = n) b(t) dt
0 n!
n=0

∞ (λt) n
−λt −s(t+B 0 +···+B n )
∞
= e E(e ) b(t) dt,
0 n!
n=0
where B 0 = 0 and B 1 , . . . , B n are independent random variables each having the
same distribution as the busy period B. Thus we find

∞
∞ (λt) n
∗ −λt −st ∗ n
β (s) = e e [β (s)] b(t) dt
0 n!
n=0
∞ ∗

e
∗
∗
= e −st −λ[1−β (s)]t b(t) dt = b (s + λ − λβ (s)),
0
as was to be proved. In the same way as (9.2.25) was derived, we can derive the
generating function of the random variable N which is defined as the number of
∞
k
customers served in one busy period. Letting F(z) = k=0 P {N = k}z , it is left
to the reader to verify that
F(z) = zb (λ − λF(z)), |z| ≤ 1. (9.2.27)
∗