(2511)

where b (s) = 0 e sx b(x) dx denotes the Laplace transform of the probability density b(x) of the service time To prove this, note that Dn , Sn and n are independent of each other This implies that, for any x > 0, E e s(Dn +Sn n ) | Dn + Sn = x =

for s = (using L Hospital s rule it can be seen that this relation also holds for s = ) Hence, using (2510), ( s)E e sDn+1 = E e s(Dn +Sn ) sE e (Dn +Sn ) Since P {(Dn + Sn n )+ = 0 | Dn + Sn = x} = e x , we also have P {Dn+1 = 0} = E e (Dn +Sn ) The latter two relations and E e s(Dn +Sn ) = E e sDn E e sSn lead to (2511) The steady-state waiting-time distribution function Wq (x) is de ned by Wq (x) = lim P {Dn x},

x 0

The existence of this limit can be proved from Theorem 224 Let the random variable D have Wq (x) as probability distribution function Then, by the bounded convergence theorem in Appendix A, E(e sD ) = limn E(e sDn ) Using (256), it follows from limn P {Dn+1 = 0} = 0 and q0 = 1 that limn P {Dn+1 = 0} = 1 Letting n in (2511), we nd that E e sD = (1 )s s + b (s) (2512)

Noting that P {D x} = Wq (x) and using relation (E7) in Appendix E, we get from (2512) the desired result:

s + b (s) s(s + b (s))

(2513)

E(S 2 ) , 2(1 )

in agreement with the Pollaczek Khintchine formula (251)

( ) Let the random variable Lq be distributed according to the limiting distribution of ( ) the number of customers in queue at an arbitrary point in time That is, P {Lq = ( ) j } = pj +1 for j 1 and P {Lq = 0} = p0 + p1 Then the generating function ( ) of Lq and the Laplace transform of the delay distribution are related to each other by ( ) E(zLq ) = E[e (1 z)D ], |z| 1 (2514)

A direct probabilistic proof of this important relation can be given Denote by Ln the number of customers left behind in queue when the nth customer enters service Since service is in order of arrival, Ln is given by the number of customers arriving during the delay Dn of the nth customer Since the generating function of a Poisson distributed variable with mean is exp ( (1 z)), it follows that for any x 0 and n 1, E(zLn |Dn = x) = e x(1 z) Hence E(zLn ) = E[e (1 z)Dn ], n 1 (2515)

The limiting distribution of Ln as n is the same as the probability distribu( ) tion of Lq This follows from an up- and downcrossing argument: the long-run fraction of customers leaving j other customers behind in queue when entering service equals the long-run fraction of customers nding j other customers in queue upon arrival Noting that there is a single server and using the PASTA property, it follows that the latter fraction equals pj +1 for j 1 and p0 + p1 for j = 0 This ( ) proves that the limiting distribution of Ln equals the distribution of Lq Note that, by Theorem 224, Ln has a limiting distribution as n Letting n in (2515), the result (2514) follows Letting wq (x) denote the derivative of the waiting-time distribution function Wq (x) for x > 0, note that for the M/G/1 queue the relation (2514) can be restated as pj +1 =