GI=G=1 queue. Let 1; 2; : : : be independent with distribution F and Let 1; 2; : : : be independent with distribution G. Define a Markov chain by XnC1 D .Xn C n  nC1/

C where yC D maxfy; 0g. Here Xn is the workload in the queue at the time of arrival of the nth customer, not counting the service time of the nth customer, n. The amount of work in front of the .nC1/th customer is that in front of the nth customer plus his service time, minus the time between the arrival of customers n and nC1. If this is negative the server has caught up and the waiting time is 0. Suppose E

(a) Show that there is a K so that Ex.X1 x/   for x  K.

(c) Let Uk D minfn W Xn  Kg.

(b) Use the fact that XUk^n C.Uk ^ n/ is a supermartingale to conclude that ExUk  x=.