Exercise 3 (Pollaczek-Khinchine formula). Consider a G/G/1 queue, where arrivals are given by a renewal process of rate and service times are iid, copies of a RV S with finite mean and variance. We use the following notations: Tk-kth arrival time Wk Time that the kth customer spen S Time that the kth customer spends in the server in the queue (20) (21) Note that limW(Tk -h) equals the waiting time W of the kth customer in the queue. We will W(1)-Remaining time until exit of the last customer in the queue at time 1 assume that the following limit exists almost surely: lim (22) The goal of this exercise is to show the following Pollaczek-Khinchine formula for the mean waiting time: Almost surely, lv:- limW (23) f-oo t MATH 171 HOMEWORK 8 (i) Let S() denote the sum of service times of all customers in the queue at time t. Show that (24) (ii) Let N(t) and Nd(t) denote the number of arrivals and departures up to time t. Use Fubini's theorem to show that (25) (26) Also, deduce that N(T) (27) (iii) From (ii) and Exercise 3.4 in Lecture note 4, show that (28) (iv) Let R(t) denote the remaining service time of the current customer in the server. Then W()- R(t) +S(). Using (i and Exercise (2), conclude the PK formula (23) Exercise 3 (Pollaczek-Khinchine formula). Consider a G/G/1 queue, where arrivals are given by a renewal process of rate and service times are iid, copies of a RV S with finite mean and variance. We use the following notations: Tk-kth arrival time Wk Time that the kth customer spen S Time that the kth customer spends in the server in the queue (20) (21) Note that limW(Tk -h) equals the waiting time W of the kth customer in the queue. We will W(1)-Remaining time until exit of the last customer in the queue at time 1 assume that the following limit exists almost surely: lim (22) The goal of this exercise is to show the following Pollaczek-Khinchine formula for the mean waiting time: Almost surely, lv:- limW (23) f-oo t MATH 171 HOMEWORK 8 (i) Let S() denote the sum of service times of all customers in the queue at time t. Show that (24) (ii) Let N(t) and Nd(t) denote the number of arrivals and departures up to time t. Use Fubini's theorem to show that (25) (26) Also, deduce that N(T) (27) (iii) From (ii) and Exercise 3.4 in Lecture note 4, show that (28) (iv) Let R(t) denote the remaining service time of the current customer in the server. Then W()- R(t) +S(). Using (i and Exercise (2), conclude the PK formula (23)