Page 42 - A First Course In Stochastic Models

CHAPTER 2

Renewal-Reward Processes

2.0 INTRODUCTION

The renewal-reward model is an extremely useful tool in the analysis of applied
probability models for inventory, queueing and reliability applications, among oth-
ers. Many stochastic processes are regenerative; that is, they regenerate themselves
from time to time so that the behaviour of the process after the regeneration epoch
is a probabilistic replica of the behaviour of the process starting at time zero. The
time interval between two regeneration epochs is called a cycle. The sequence of
regeneration cycles constitutes a so-called renewal process. The long-run behaviour
of a regenerative stochastic process on which a reward structure is imposed can
be studied in terms of the behaviour of the process during a single regeneration
cycle. The simple and intuitively appealing renewal-reward model has numerous
applications.
In Section 2.1 we first discuss some elementary results from renewal theory. A
more detailed treatment of renewal theory will be given in Chapter 8. Section 2.2
deals with the renewal-reward model. It shows how to calculate long-run aver-
ages such as the long-run average reward per time unit and the long-run fraction
of time the system spends in a given set of states. Illustrative examples will be
given. Section 2.3 discusses the formula of Little. This formula is a kind of law
of nature and relates among others the average queue size to the average wait-
ing time in queueing systems. Another fundamental result that is frequently used
in queueing and inventory applications is the property that Poisson arrivals see
time averages (PASTA). This result is discussed in some detail in Section 2.4. The
PASTA property is used in Section 2.5 to obtain the famous Pollaczek–Khintchine
formula from queueing theory. The renewal-reward model is used in Section 2.6 to
obtain a generalization of the Pollaczek–Khintchine formula in the framework of
a controlled queue. Section 2.7 shows how renewal theory and an up- and down-
crossing argument can be combined to derive a relation between time-average and
customer-average probabilities in queues.

A First Course in Stochastic Models H.C. Tijms
c 2003 John Wiley & Sons, Ltd. ISBNs: 0-471-49880-7 (HB); 0-471-49881-5 (PB)