Page 50 - A First Course In Stochastic Models

RENEWAL-REWARD PROCESSES 41

Note that the cycle length C n assumes values from the index set T . In the following
it is assumed that

0 < E(C 1 ) < ∞.
In many practical situations a reward structure is imposed on the regenerative
process {X(t), t ∈ T }. The reward structure usually consists of reward rates that
are earned continuously over time and lump rewards that are only earned at certain
state transitions. Let

R n = the total reward earned in the nth renewal cycle, n = 1, 2, . . . .
It is assumed that R 1 , R 2 , . . . are independent and identically distributed random
variables. In applications R n typically depends on C n . In case R n can take on both
positive and negative values, it is assumed that E(|R 1 |) < ∞. Let

R(t) = the cumulative reward earned up to time t.

The process {R(t), t ≥ 0} is called a renewal-reward process. We are now ready
to prove a theorem of utmost importance.

Theorem 2.2.1 (renewal-reward theorem)
R(t) E(R 1 )
lim = with probability 1.
t→∞ t E(C 1 )
In other words, for almost any realization of the process, the long-run average
reward per time unit is equal to the expected reward earned during one cycle divided
by the expected length of one cycle.

To prove this theorem we first establish the following lemma.
Lemma 2.2.2 For any t ≥ 0, let N(t) be the number of cycles completed up to
time t. Then
N(t) 1
lim = with probability 1.
t→∞ t E(C 1 )
Proof By the definition of N(t), we have

C 1 + · · · + C N(t) ≤ t < C 1 + · · · + C N(t)+1 .
Since P {C 1 + · · · + C n < ∞} = 1 for all n ≥ 1, it is not difficult to verify that

lim N(t) = ∞ with probability 1.
t→∞
The above inequality gives

C 1 + · · · + C N(t) t C 1 + · · · + C N(t)+1 N(t) + 1
≤ < .
N(t) N(t) N(t) + 1 N(t)