Page 49 - A First Course In Stochastic Models

40 RENEWAL-REWARD PROCESSES

Chapters 3 and 4, ergodic theorems for Markov chains will be proved by using
the renewal-reward theorem. The renewal-reward model is a simple and intuitively
appealing model that deals with a so-called regenerative process on which a cost
or reward structure is imposed. Many stochastic processes have the property of
regenerating themselves at certain points in time so that the behaviour of the process
after the regeneration epoch is a probabilistic replica of the behaviour starting at
time zero and is independent of the behaviour before the regeneration epoch.
A formal definition of a regenerative process is as follows.

Definition 2.2.1 A stochastic process {X(t), t ∈ T } with time-index set T is said
to be regenerative if there exists a (random) epoch S 1 such that:

(a) {X(t + S 1 ), t ∈ T } is independent of {X(t), 0 ≤ t < S 1 },
(b) {X(t + S 1 ), t ∈ T } has the same distribution as {X(t), t ∈ T }.
It is assumed that the index set T is either the interval T = [0, ∞) or the count-
able set T = {0, 1, . . . }. In the former case we have a continuous-time regenerative
process and in the other case a discrete-time regenerative process. The state space
of the process {X(t)} is assumed to be a subset of some Euclidean space.
The existence of the regeneration epoch S 1 implies the existence of further
regeneration epochs S 2 , S 3 , . . . having the same property as S 1 . Intuitively speak-
ing, a regenerative process can be split into independent and identically distributed
renewal cycles. A cycle is defined as the time interval between two consecutive
regeneration epochs. Examples of regenerative processes are:

(i) The continuous-time process {X(t), t ≥ 0} with X(t) denoting the number of
customers present at time t in a single-server queue in which the customers
arrive according to a renewal process and the service times are independent
and identically distributed random variables. It is assumed that at epoch 0 a
customer arrives at an empty system. The regeneration epochs S 1 , S 2 , . . . are
the epochs at which an arriving customer finds the system empty.
(ii) The discrete-time process {I n , n = 0, 1, . . . } with I n denoting the inventory
level at the beginning of the nth week in the (s, S) inventory model dealt with
in Example 2.1.3. Assume that the inventory level equals S at epoch 0. The
regeneration epochs are the beginnings of the weeks in which the inventory
level is ordered up to the level S.

Let us define the random variables C n = S n −S n−1 , n = 1, 2, . . . , where S 0 = 0
by convention. The random variables C 1 , C 2 , . . . are independent and identically
distributed. In fact the sequence {C 1 , C 2 , . . . } underlies a renewal process in which
the events are the occurrences of the regeneration epochs. Hence we can interpret
C n as

C n = the length of the nth renewal cycle, n = 1, 2, . . . .