Page 87 - A First Course In Stochastic Models

78 RENEWAL-REWARD PROCESSES

(Hint: use results from Section 2.6 to obtain the expected amount of time elapsed between
two arrivals finding the channel free.)

BIBLIOGRAPHIC NOTES

The very readable monograph of Cox (1962) contributed much to the populariza-
tion of renewal theory. A good account of renewal theory can also be found in the
texts Ross (1996) and Wolff (1989). A basic paper on renewal theory and regen-
erative processes is that of Smith (1958), a paper which recognized the usefulness
of renewal-reward processes in the analysis of applied probability problems. The
book of Ross (1970) was influential in promoting the application of renewal-reward
processes. The renewal-reward model has many applications in inventory, queue-
ing and reliability. The illustrative queueing example from Section 2.6 is taken
from the paper of Yadin and Naor (1963), which initiated the study of control
rules for queueing systems. Example 2.2.3 is adapted from the paper of Vered and
Yechiali (1979).
The first rigorous proof of L = λW was given by Little (1961) under rather
strong conditions; see also Jewell (1967). Under very weak conditions a sample-
path proof of L = λW was given by Stidham (1974). The important result that
Poisson arrivals see time averages was taken for granted by earlier practitioners.
A rigorous proof was given in the paper of Wolff (1982). The derivation of the
Laplace transform of the waiting-time distribution in the M/G/1 queue is adapted
from Cohen (1982) and the relation between this transform and the generating
function of the queue size comes from Haji and Newell (1971).

REFERENCES

Artalejo, J.R., Falin, G.I. and Lopez-Herrero, M.J. (2002) A second order analysis of the
waiting time in the M/G/1 retrial queue. Asia-Pacific J. Operat. Res., 19, 131–148.
Cohen, J.W. (1982) The Single Server Queue, 2nd edn. North-Holland, Amsterdam.
Cox, D.R. (1955) The statistical analysis of congestion. J. R. Statist. Soc. A., 118, 324–335.
Cox, D.R. (1962) Renewal Theory. Methuen, London.
Haji, R. and Newell, G.F. (1971) A relation between stationary queue and waiting-time
distribution. J. Appl. Prob., 8, 617–620.
Jewell, W.S. (1967) A simple proof of L = λW. Operat. Res., 15, 1109–1116.
Keilson, J. (1979) Markov Chain Models—Rarity and Exponentiality. Springer-Verlag,
Berlin.
Little, J.D.C. (1961) A proof for the queueing formula L = λW. Operat. Res., 9, 383–387.
Miller, D.R. (1972) Existence of limits in regenerative processes. Ann. Math. Statist., 43,
1275–1282.
Ross, S.M. (1970) Applied Probability Models with Optimization Applications. Holden-Day,
San Francisco.
Ross, S.M. (1996) Stochastic Processes, 2nd. edn. John Wiley & Sons, Inc., New York.
Smith, W.L. (1958) Renewal theory and its ramifications. J. R. Statist. Soc. B, 20, 243–302.
Solovyez, A.D. (1971) Asymptotic behaviour of the time of first occurrence of a rare event
in a regenerating process. Engineering Cybernetics, 9, 1038–1048.