Renewal theory is a branch of probability theory with an interesting and varied range of applications. Applications include calculating the expected time for a monkey who is randomly tapping at a keyboard to type the word Macbeth and comparing the longterm benefits of different insurance policies. This article is quite technical and is likely only to be accessible to a reader with a modest knowledge of undergraduate-level probability theory. Knowledge of continuous-time Markov processes is essential and knowledge of the Poisson process is highly recommended.

Renewal processes - an 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\; ,\; \backslash ldots$ be a sequence of independent identically distributed random variables such that

We refer to the random variable $S\_i$ as the "$i$th" holding time.

Define for each n > 0 :

$J\_n\; =\; \backslash sum\_\{i=1\}^n\; S\_i,$

each $J\_n$ referred to as the "$n$th" jump time and the intervals

$*$

being called renewal intervals.

Then the random variable $(X\_t)\_\{t\backslash geq0\}$ given by

$X\_t\; =\; \backslash max\; \backslash left\backslash \{\backslash ,\; n:\; J\_n\; \backslash leq\; t\backslash ,\; \backslash right\backslash \}$

is called a renewal process.

Interpretation

One may choose to think of the holding times $\backslash \{\; S\_i\; :\; i\; \backslash geq\; 1\; \backslash \}$ 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 $\backslash \{\; J\_n\; :\; n\; \backslash geq\; 1\; \backslash \}$ 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,\; \backslash ldots$ be a sequence of IID random variables (rewards) satisfying

.

Then the random variable

$Y\_t\; =\; \backslash sum\_\{i=1\}^\{X\_t\}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,\backslash 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(t)\; =\; \backslash mathbb\{E\}*$.

The elementary renewal theorem

The renewal function satisfies

$\backslash lim\_\{t\; \backslash to\; \backslash infty\}\; \backslash frac\{1\}\{t\}m(t)\; =\; 1/\backslash mathbb\{E\}*$

The proof of this statement is non-trivial and therefore omitted.

The renewal equation

The renewal function satisfies

$m(t)\; =\; F\_S(t)\; +\; \backslash int\_0^t\; m(t-s)\; f\_S(s)\backslash ,\; 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(t)\; =\; \backslash mathbb\{E\}=\; \backslash mathbb\{E\}[\backslash mathbb\{E\}(X\_t\; \backslash mid\; S\_1)$.

But by the Markov property

$\backslash mathbb\{E\}(X\_t\; \backslash mid\; S\_1=s)\; =\; \backslash mathbb\{I\}\_\{\backslash \{t\; \backslash geq\; s\backslash \}\}\; \backslash left(\; 1\; +\; \backslash mathbb\{E\}*)\; \backslash right).$

So

$m(t)\; =\; \backslash mathbb\{E\}*$

$=\; \backslash mathbb\{E\}\backslash mid\; S\_1)$

$=\; \backslash int\_0^\backslash infty\; \backslash mathbb\{E\}(X\_t\; \backslash mid\; S\_1=s)\; f\_S(s)\backslash ,\; ds$

$=\; \backslash int\_0^\backslash infty\; \backslash mathbb\{I\}\_\{\backslash \{t\; \backslash geq\; s\backslash \}\}\; \backslash left(\; 1\; +\; \backslash mathbb\{E\}*\backslash right)\; f\_S(s)\backslash ,\; ds$

$=\; \backslash int\_0^t\; \backslash left(\; 1\; +\; m(t-s)\; \backslash right)\; f\_S(s)\backslash ,\; ds$

$=\; F\_S(t)\; +\; \backslash int\_0^t\; m(t-s)\; f\_S(s)\backslash ,\; ds,$

as required.

Asymptotic properties

$(X\_t)\_\{t\backslash geq0\}$ and $(Y\_t)\_\{t\backslash geq0\}$ satisfy

$\backslash lim\_\{t\; \backslash to\; \backslash infty\}\; \backslash frac\{1\}\{t\}\; X\_t\; =\; \backslash frac\{1\}\{\backslash mathbb\{E\}S\_1\}$ (strong law of large numbers for renewal processes)

$\backslash lim\_\{t\; \backslash to\; \backslash infty\}\; \backslash frac\{1\}\{t\}\; Y\_t\; =\; \backslash frac\{1\}\{\backslash mathbb\{E\}S\_1\}\; \backslash mathbb\{E\}W\_1$ (strong law of large numbers for renewal-reward processes)

almost surely.

Proof

First consider $(X\_t)\_\{t\backslash geq0\}$. By definition we have:

$J\_\{X\_t\}\; \backslash leq\; t\; \backslash leq\; J\_\{X\_t+1\}$

for all $t\; \backslash 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 we have:

$X\_t\; \backslash to\; \backslash infty$

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

$\backslash frac\{J\_\{X\_t\}\}\{X\_t\}\; =\; \backslash frac\{J\_n\}\{n\}\; =\; \backslash frac\{1\}\{n\}\backslash sum\_\{i=1\}^n\; S\_i\; \backslash to\; \backslash mathbb\{E\}S\_1$

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

$\backslash frac\{J\_\{X\_t+1\}\}\{X\_t\}\; =\; \backslash frac\{J\_\{X\_t+1\}\}\{X\_t+1\}\backslash frac\{X\_t+1\}\{X\_t\}\; =\; \backslash frac\{J\_\{n+1\}\}\{n+1\}\backslash frac\{n+1\}\{n\}\; \backslash to\; \backslash mathbb\{E\}S\_1\backslash cdot\; 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 $(Y\_t)\_\{t\backslash geq0\}$. We have

$\backslash frac\{1\}\{t\}Y\_t\; =\; \backslash frac\{X\_t\}\{t\}\; \backslash frac\{1\}\{X\_t\}\; Y\_t\; \backslash to\; \backslash frac\{1\}\{\backslash mathbb\{E\}S\_1\}\backslash cdot\backslash mathbb\{E\}W\_1$

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

The 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:

$\backslash mathbb\{P\}(S\_\{X\_t+1\}\; >\; x)\; \backslash geq\; \backslash mathbb\{P\}(S\_1>x)\; =\; 1-F\_S(x)$

where F_S is the cumulative distribution function of the IID holding times S_i.

Proof of the inspection paradox

Observe that the last jump-time before t is $J\_\{X\_t\}$; and that the renewal interval containing t is $S\_\{X\_t+1\}$. Then

$$

\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

$=\; \backslash int\_0^\backslash infty\; \backslash mathbb\{P\}(S\_\{X\_t+1\}>x\; |\; S\_\{X\_t+1\}>t-s)\; f\_S(s)\backslash ,\; ds$

$=\; \backslash int\_0^\backslash infty\; \backslash frac\{\backslash mathbb\{P\}(S\_\{X\_t+1\}>x\; \backslash ,\; ,\; \backslash ,\; S\_\{X\_t+1\}>t-s)\}\{\backslash mathbb\{P\}(S\_\{X\_t+1\}>t-s)\}\; f\_S(s)\; \backslash ,\; ds$

$=\; \backslash int\_0^\backslash infty\; \backslash frac\{\; 1-F(\backslash max\; \backslash \{\; x,t-s\; \backslash \})\; \}\{1-F(t-s)\}\; f\_S(s)\; \backslash ,\; ds$

$=\; \backslash int\_0^\backslash infty\; \backslash min\; \backslash left\backslash \{\backslash frac\{\; 1-F(x)\; \}\{1-F(t-s)\},\backslash frac\{\; 1-F(t-s)\; \}\{1-F(t-s)\}\backslash right\backslash \}\; f\_S(s)\; \backslash ,\; ds$

$=\; \backslash int\_0^\backslash infty\; \backslash min\; \backslash left\backslash \{\backslash frac\{\; 1-F(x)\; \}\{1-F(t-s)\},1\backslash right\backslash \}\; f\_S(s)\; \backslash ,\; ds$

$\backslash geq\; 1-F(x)$

$=\; \backslash mathbb\{P\}(S\_1>x)$

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 $(Y\_t)\_\{t\; \backslash geq\; 0\}$. 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 happends 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:

$$

\begin{matrix} \mathbb{E}S & = & \mathbb{E}\mid \mbox{machine fails before } t \cdot \mathbb{P}fails before } t \\ \\ & & \qquad + \quad \mathbb{E}\mid \mbox{machine does not fail before } t \cdot \mathbb{P}does not fail before } t \end{matrix}

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

and the expected cost W per machine is:

$$

\begin{matrix} \mathbb{E}W & = & \mathbb{E}(W \mid \mbox{machine fails before } t) \cdot \mathbb{P}(\mbox{machine fails before } t) \\ \\ & & + \quad \mathbb{E}[W \mid \mbox{machine does not fails before } t).\mathbb{P}(\mbox{machine does not fail before } t) \end{matrix}

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

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} 4\frac{ 4(1200t + 200) }{ t^2 + 4t - 2t^2 } = 4\frac{ (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 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.

See also

---

• Poisson process
• Continuous-time Markov process
• Semi-Markov process
• Queueing Theory
• Campbell's Theorem
• Little's Lemma

probability theory