Consider a variation of an M/G/1 queueing system in which there is no facility to save waiting customers. Assume customers arrive according to a Poisson process of rate λ. If the server is busy, the customer departs and is lost forever; if the server is not busy, the customer enters service with a service time CDF denoted by FY (y). Successive service times (for those customers that are served) are IID and independent of arrival times. Assume that customer number 0 arrives and enters service at time t = 0.
(a) Show that the sequence of times S1, S2, ... at which successive successful customers enter service are the renewal times of a renewal process. Show that each inter-renewal interval Xi = Si - Si-1 (where S0 = 0) is the sum of two independent rv s, Yi + Ui where Yi is the ith service time; find the probability density of Ui.
(b) Assume that a reward (actually a cost in this case) of one unit is incurred for each customer turned away. Sketch the expected reward function as a function of time for the sample function of inter-renewal intervals and service intervals shown below; the expectation is to be taken over those (unshown) arrivals of customers that must be turned away.
(c) Let ( t R(τ )dτ denote the accumulated reward (i.e., cost) from 0 to t and find the limit as t → ∞ of (1/t) ( t R(τ )dτ . Explain (without any attempt to be rigorous or formal) why this limit exists with probability 1.
(d) In the limit of large t, find the expected reward from time t until the next renewal. Hint: Sketch this expected reward as a function of t for a given sample of inter-renewal intervals and service intervals; then find the time average.
(e) Now assume that the arrivals are deterministic, with the first arrival at time 0 and the nth arrival at time n - 1. Does the sequence of times S1, S2, ... at which subsequent customers start service still constitute the renewal times of a renewal process? Draw a sketch of arrivals, departures, and service time intervals. Again find t limt→∞((R(τ ) dτ )/t.
Text Book: Stochastic Processes: Theory for Applications By Robert G. Gallager.