Definitions

Renewal theory

Renewal theory is the branch of probability theory that generalizes Poisson processes for arbitrary holding times. Applications include calculating the expected time for a monkey who is randomly tapping at a keyboard to type the word Macbeth and comparing the long-term benefits of different insurance policies.

Renewal processes

Introduction

A renewal process is a generalisation of the Poisson process. In essence, the Poisson process is a continuous-time Markov process on the positive integers (usually starting at zero) which has independent identically distributed holding times at each integer $i$ (exponentially distributed) before advancing (with probability 1) to the next integer:$i+1$. In the same informal spirit, we may define a renewal process to be the same thing, except that the holding times take on a more general distribution. (Note however that the IID property of the holding times is retained).

Formal definition

Let $S_1 , S_2 , S_3 , S_4 , S_5, ldots$ be a sequence of independent identically distributed random variables such that

$0 < mathbb\left\{E\right\}\left[S_i\right] < infty.$

We refer to the random variable $S_i$ as the "$i$th" holding time.

Define for each n > 0 :

$J_n = sum_\left\{i=1\right\}^n S_i,$

each $J_n$ referred to as the "$n$th" jump time and the intervals

$\left[J_n,J_\left\{n+1\right\}\right]$

being called renewal intervals.

Then the random variable $\left(X_t\right)_\left\{tgeq0\right\}$ given by

$X_t = sum^\left\{infty\right\}_\left\{n=1\right\} mathbb\left\{I\right\}_\left\{\left\{J_n leq t\right\}\right\}=sup left\left\{, n: J_n leq t, right\right\}$

is called a renewal process.

Interpretation

One may choose to think of the holding times $\left\{ S_i : i geq 1 \right\}$ as the time elapsed before a machine breaks for the "$i$th" time since the last time it broke. (Note this assumes that the machine is immediately fixed and we restart the clock immediately.) Under this interpretation, the jump times $\left\{ J_n : n geq 1 \right\}$ record the successive times at which the machine breaks and the renewal process $X_t$ records the number of times the machine has so far had to be repaired at any given time $t$.

However it is more helpful to understand the renewal process in its abstract form, since it may be used to model a great number of practical situations of interest which do not relate very closely to the operation of machines.

Renewal-reward processes

Let $W_1, W_2, ldots$ be a sequence of IID random variables (rewards) satisfying

$mathbb\left\{E\right\}|W_i| < infty.,$

Then the random variable

$Y_t = sum_\left\{i=1\right\}^\left\{X_t\right\}W_i$

is called a renewal-reward process. Note that unlike the $S_i$, each $W_i$ may take negative values as well as positive values.

Interpretation

In the context of the above interpretation of the holding times as the time between successive malfunctions of a machine, the "rewards" $W_1,W_2,ldots$ (which in this case happen to be negative) 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 (holding times) distributed as $S_i$. Sometimes it lays golden eggs of random weight, and sometimes it lays toxic eggs (also of random weight) which require responsible (and costly) disposal. The "rewards" $W_i$ are the successive (random) financial losses/gains resulting from successive eggs (i = 1,2,3,...) and $Y_t$ records the total financial "reward" at time t.

Properties of renewal processes and renewal-reward processes

We define the renewal function:

$m\left(t\right) = mathbb\left\{E\right\}\left[X_t\right].,$

The elementary renewal theorem

The renewal function satisfies

$lim_\left\{t to infty\right\} frac\left\{1\right\}\left\{t\right\}m\left(t\right) = 1/mathbb\left\{E\right\}\left[S_1\right].$

Proof

Below, you find that the strong law of large numbers for renewal processes tell us that

$lim_\left\{t to infty\right\} frac \left\{X_t\right\}\left\{t\right\} = frac\left\{1\right\}\left\{mathbb\left\{E\right\}\left[S_1\right]\right\}.$

To prove the elementary renewal theorem, it is sufficient to show that $left\left\{frac\left\{X_t\right\}\left\{t\right\}; t geq 0right\right\}$ is uniformly integrable.

To do this, consider some truncated renewal process where the holding times are defined by $overline\left\{S_n\right\} = a mathbb\left\{I\right\}\left\{S_n > a\right\}$ where $a$ is a point such that $0 < F\left(a\right) = p < 1$ which exists for all non-deterministic renewal processes. This new renewal process $overline\left\{X_t\right\}$ is an upper bound on $X_t$ and its renewals can only occur on the lattice $\left\{na; n in mathbb\left\{N\right\} \right\}$. Furthermore, the number of renewals at each time is geometric with parameter $p$. So we have


begin{align} overline{X_t} &leq sum_{i=1}^{[at]} mathrm{Geometric}(p) mathbb{E}left[,overline{X_t},right]^2 &leq C_1 t + C_2 t^2 Pleft(frac{X_t}{t} > xright) &leq frac{Eleft[X_t^2right]}{t^2x^2} leq frac{Eleft[overline{X_t}^2right]}{t^2x^2} leq frac{C}{x^2}. end{align}

The elementary renewal theorem for reward renewal processes

We define the reward function:

$g\left(t\right) = mathbb\left\{E\right\}\left[Y_t\right].,$

The renewal function satisfies

$lim_\left\{t to infty\right\} frac\left\{1\right\}\left\{t\right\}g\left(t\right) = frac\left\{mathbb\left\{E\right\}\left[W_1\right]\right\}\left\{mathbb\left\{E\right\}\left[S_1\right]\right\}.$

The renewal equation

The renewal function satisfies

$m\left(t\right) = F_S\left(t\right) + int_0^t m\left(t-s\right) f_S\left(s\right), ds$

where $F_S$ is the cumulative distribution function of $S_1$ and $f_S$ is the corresponding probability density function.

Proof of the renewal equation

We may iterate the expectation about the first holding time:

$m\left(t\right) = mathbb\left\{E\right\}\left[X_t\right] = mathbb\left\{E\right\}\left[mathbb\left\{E\right\}\left(X_t mid S_1\right)\right].$

But by the Markov property

$mathbb\left\{E\right\}\left(X_t mid S_1=s\right) = mathbb\left\{I\right\}_\left\{\left\{t geq s\right\}\right\} left\left(1 + mathbb\left\{E\right\}\left[X_\left\{t-s\right\}\right] right\right).$

So


begin{align} m(t) & {} = mathbb{E}[X_t] & {} = mathbb{E}[mathbb{E}(X_t mid S_1)] & {} = int_0^infty mathbb{E}(X_t mid S_1=s) f_S(s), ds & {} = int_0^infty mathbb{I}_{{t geq s}} left(1 + mathbb{E}[X_{t-s}] right) f_S(s), ds & {} = int_0^t left(1 + m(t-s) right) f_S(s), ds & {} = F_S(t) + int_0^t m(t-s) f_S(s), ds, end{align}

as required.

Asymptotic properties

$\left(X_t\right)_\left\{tgeq0\right\}$ and $\left(Y_t\right)_\left\{tgeq0\right\}$ satisfy

$lim_\left\{t to infty\right\} frac\left\{1\right\}\left\{t\right\} X_t = frac\left\{1\right\}\left\{mathbb\left\{E\right\}S_1\right\}$ (strong law of large numbers for renewal processes)

$lim_\left\{t to infty\right\} frac\left\{1\right\}\left\{t\right\} Y_t = frac\left\{1\right\}\left\{mathbb\left\{E\right\}S_1\right\} mathbb\left\{E\right\}W_1$ (strong law of large numbers for renewal-reward processes)

almost surely.

Proof

First consider $\left(X_t\right)_\left\{tgeq0\right\}$. By definition we have:

$J_\left\{X_t\right\} leq t leq J_\left\{X_t+1\right\}$

for all $t geq 0$ and so


frac{J_{X_t}}{X_t} leq frac{t}{X_t} leq frac{J_{X_t+1}}{X_t}

for all t ≥ 0.

Now since $0< mathbb\left\{E\right\}S_i < infty$ we have:

$X_t to infty$

as $t to infty$ almost surely (with probability 1). Hence:

$frac\left\{J_\left\{X_t\right\}\right\}\left\{X_t\right\} = frac\left\{J_n\right\}\left\{n\right\} = frac\left\{1\right\}\left\{n\right\}sum_\left\{i=1\right\}^n S_i to mathbb\left\{E\right\}S_1$

almost surely (using the strong law of large numbers); similarly:

$frac\left\{J_\left\{X_t+1\right\}\right\}\left\{X_t\right\} = frac\left\{J_\left\{X_t+1\right\}\right\}\left\{X_t+1\right\}frac\left\{X_t+1\right\}\left\{X_t\right\} = frac\left\{J_\left\{n+1\right\}\right\}\left\{n+1\right\}frac\left\{n+1\right\}\left\{n\right\} to mathbb\left\{E\right\}S_1cdot 1$

almost surely.

Thus (since $t/X_t$ is sandwiched between the two terms)


frac{1}{t} X_t to frac{1}{mathbb{E}S_1}

almost surely.

Next consider $\left(Y_t\right)_\left\{tgeq0\right\}$. We have

$frac\left\{1\right\}\left\{t\right\}Y_t = frac\left\{X_t\right\}\left\{t\right\} frac\left\{1\right\}\left\{X_t\right\} Y_t to frac\left\{1\right\}\left\{mathbb\left\{E\right\}S_1\right\}cdotmathbb\left\{E\right\}W_1$

almost surely (using the first result and using the law of large numbers on $Y_t$).

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:

$mathbb\left\{P\right\}\left(S_\left\{X_t+1\right\} > x\right) geq mathbb\left\{P\right\}\left(S_1>x\right) = 1-F_S\left(x\right)$

where FS is the cumulative distribution function of the IID holding times Si.

Observe that the last jump-time before t is $J_\left\{X_t\right\}$; and that the renewal interval containing t is $S_\left\{X_t+1\right\}$. Then


begin{align} mathbb{P}(S_{X_t+1}>x) & {} = int_0^infty mathbb{P}(S_{X_t+1}>x mid J_{X_t} = s) f_S(s) , ds & {} = int_0^infty mathbb{P}(S_{X_t+1}>x | S_{X_t+1}>t-s) f_S(s), ds & {} = int_0^infty frac{mathbb{P}(S_{X_t+1}>x , , , S_{X_t+1}>t-s)}{mathbb{P}(S_{X_t+1}>t-s)} f_S(s) , ds & {} = int_0^infty frac{ 1-F(max { x,t-s }) }{1-F(t-s)} f_S(s) , ds & {} = int_0^infty min left{frac{ 1-F(x) }{1-F(t-s)},frac{ 1-F(t-s) }{1-F(t-s)}right} f_S(s) , ds & {} = int_0^infty min left{frac{ 1-F(x) }{1-F(t-s)},1right} f_S(s) , ds & {} geq 1-F(x) & {} = mathbb{P}(S_1>x) end{align}

as required.

Example applications

Example 1 - use of the strong law of large numbers

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?

Solution

We may model the lifetime of the n machines as n independent concurrent renewal-reward processes, so it is sufficient to consider the case n=1. Denote this process by $\left(Y_t\right)_\left\{t geq 0\right\}$. The successive lifetimes S of the replacement machines are independent and identically distributed, so the optimal policy is the same for all replacement machines in the process.

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 [0, t] and thus has expectation 0.5t. So the overall expected lifetime of the machine is:

$mathbb\left\{E\right\}S = mathbb\left\{E\right\}\left[S mid mbox\left\{fails before \right\} t\right] cdot mathbb\left\{P\right\}\left[mbox\left\{fails before \right\} t\right] + mathbb\left\{E\right\}\left[S mid mbox\left\{does not fail before \right\} t\right] cdot mathbb\left\{P\right\}\left[mbox\left\{does not fail before \right\} t\right]$

$= frac\left\{t\right\}\left\{2\right\}left\left(0.5tright\right) + frac\left\{2-t\right\}\left\{2\right\}left\left(t right\right)$

and the expected cost W per machine is:

$mathbb\left\{E\right\}W = mathbb\left\{E\right\}\left(W mid mbox\left\{fails before \right\} t\right) cdot mathbb\left\{P\right\}\left(mbox\left\{fails before \right\} t\right) + mathbb\left\{E\right\}\left[W mid mbox\left\{does not fail before \right\} t\right).mathbb\left\{P\right\}\left(mbox\left\{does not fail before \right\} t\right)$

$= frac\left\{t\right\}\left\{2\right\}\left(2600 \right) + frac\left\{2-t\right\}\left\{2\right\} \left(200 \right) = 1200t + 200.,$

So by the strong law of large numbers, his longterm average cost per unit time is:


lim_{t to infty} frac{1}{t} Y_t = frac{mathbb{E}W}{mathbb{E}S} = frac{ 4(1200t + 200) }{ t^2 + 4t - 2t^2 }

then differentiating with respect to t:


frac{partial}{partial t} frac{ 4(1200t + 200) }{ t^2 + 4t - 2t^2 } = 4frac{ (4t - t^2)(1200) - (4 - 2t)(1200t + 200) }{ (t^2 + 4t - 2t^2)^2 },

this implies that the turning points satisfy:


0 = (4t - t^2)(1200) - (4 - 2t)(1200t + 200)
`= 4800t - 1200t^2 -4800t - 800 + 2400t^2 + 400t `


= -800 + 400t + 1200t^2,

and thus


0 = 3t^2 + t - 2 = (3t -2)(t+1).

We take the only solution t in [0, 2]: t = 2/3. This is indeed a minimum (and not a maximum) 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.