Renewal theory


Renewal theory is the branch of probability theory that generalizes the Poisson process for arbitrary holding times. Instead of exponentially distributed holding times, a renewal process may have any independent and identically distributed holding times that have finite mean. A renewal-reward process additionally has a random sequence of rewards incurred at each holding time, which are IID but need not be independent of the holding times.
A renewal process has asymptotic properties analogous to the strong law of large numbers and central limit theorem. The renewal function and reward function are of key importance in renewal theory. The renewal function satisfies a recursive integral equation, the renewal equation. The key renewal equation gives the limiting value of the convolution of with a suitable non-negative function. The superposition of renewal processes can be studied as a special case of Markov renewal processes.
Applications include calculating the best strategy for replacing worn-out machinery in a factory and comparing the long-term benefits of different insurance policies. The inspection paradox relates to the fact that observing a renewal interval at time t gives an interval with average value larger than that of an average renewal interval.

Renewal processes

Introduction

The renewal process is a generalization of the Poisson process. In essence, the Poisson process is a continuous-time Markov process on the positive integers which has independent exponentially distributed holding times at each integer before advancing to the next integer,. In a renewal process, the holding times need not have an exponential distribution; rather, the holding times may have any distribution on the positive numbers, so long as the holding times are independent and identically distributed and have finite mean.

Formal definition

Let be a sequence of positive independent identically distributed random variables such that
We refer to the random variable as the "-th holding time".
is the expectation of.
Define for each n > 0 :
each is referred to as the "-th jump time" and the intervals are called "renewal intervals".
Then is given by random variable
where is the indicator function
represents the number of jumps that have occurred by time t, and is called a renewal process.

Interpretation

If one considers events occurring at random times, one may choose to think of the holding times as the random time elapsed between two consecutive events. For example, if the renewal process is modelling the numbers of breakdown of different machines, then the holding time represents the time between one machine breaking down before another one does.
The Poisson process is the unique renewal process with the Markov property, as the exponential distribution is the unique continuous random variable with the property of memorylessness.

Renewal-reward processes

Let be a sequence of IID random variables satisfying
Then the random variable
is called a renewal-reward process. Note that unlike the, each may take negative values as well as positive values.
The random variable depends on two sequences: the holding times and the rewards
These two sequences need not be independent. In particular, may be a function
of.

Interpretation

In the context of the above interpretation of the holding times as the time between successive malfunctions of a machine, the "rewards" may be viewed as the successive repair costs incurred as a result of the successive malfunctions.
An alternative analogy is that we have a magic goose which lays eggs at intervals distributed as. Sometimes it lays golden eggs of random weight, and sometimes it lays toxic eggs which require responsible disposal. The "rewards" are the successive financial losses/gains resulting from successive eggs and records the total financial "reward" at time t.

Renewal function

We define the renewal function as the expected value of the number of jumps observed up to some time :

Elementary renewal theorem

The renewal function satisfies
To prove the elementary renewal theorem, it is sufficient to show that is uniformly integrable.
To do this, consider some truncated renewal process where the holding times are defined by where is a point such that which exists for all non-deterministic renewal processes. This new renewal process is an upper bound on and its renewals can only occur on the lattice. Furthermore, the number of renewals at each time is geometric with parameter. So we have

Elementary renewal theorem for renewal reward processes

We define the reward function:
The reward function satisfies

Renewal equation

The renewal function satisfies
where is the cumulative distribution function of and is the corresponding probability density function.
But by the Markov property
So
as required.

Key renewal theorem

Let X be a renewal process with renewal function and interrenewal mean. Let be a function satisfying:
The key renewal theorem states that, as :

Renewal theorem

Considering for any gives as a special case the renewal theorem:
The result can be proved using integral equations or by a coupling argument. Though a special case of the key renewal theorem, it can be used to deduce the full theorem, by considering step functions and then increasing sequences of step functions.

Asymptotic properties

Renewal processes and renewal-reward processes have properties analogous to the strong law of large numbers, which can be derived from the same theorem. If is a renewal process and is a renewal-reward process then:
almost surely.
for all and so
for all t ≥ 0.
Now since we have:
as almost surely. Hence:
almost surely ; similarly:
almost surely.
Thus
almost surely.
Next consider. We have
almost surely.
Renewal processes additionally have a property analogous to the central limit theorem:

Inspection paradox

A curious feature of renewal processes is that if we wait some predetermined time t and then observe how large the renewal interval containing t is, we should expect it to be typically larger than a renewal interval of average size.
Mathematically the inspection paradox states: for any t > 0 the renewal interval containing t is stochastically larger than the first renewal interval. That is, for all x > 0 and for all t > 0:
where FS is the cumulative distribution function of the IID holding times Si.
The resolution of the paradox is that our sampled distribution at time t is size-biased, in that the likelihood an interval is chosen is proportional to its size. However, a renewal interval of average size is not size-biased.
since both and are greater than or equal to for all values of s.

Superposition

Unless the renewal process is a Poisson process, the superposition of two independent renewal processes is not a renewal process. However, such processes can be described within a larger class of processes called the Markov-renewal processes. However, the cumulative distribution function of the first inter-event time in the superposition process is given by
where Rk and αk > 0 are the CDF of the inter-event times and the arrival rate of process k.

Example application

Eric the entrepreneur has n machines, each having an operational lifetime uniformly distributed between zero and two years. Eric may let each machine run until it fails with replacement cost €2600; alternatively he may replace a machine at any time while it is still functional at a cost of €200.
What is his optimal replacement policy?
If Eric decides at the start of a machine's life to replace it at time 0 < t < 2 but the machine happens to fail before that time then the lifetime S of the machine is uniformly distributed on and thus has expectation 0.5t. So the overall expected lifetime of the machine is:
and the expected cost W per machine is:
So by the strong law of large numbers, his long-term average cost per unit time is:
then differentiating with respect to t:
this implies that the turning points satisfy:
and thus
We take the only solution t in : t = 2/3. This is indeed a minimum since the cost per unit time tends to infinity as t tends to zero, meaning that the cost is decreasing as t increases, until the point 2/3 where it starts to increase.