﻿

# 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=sup left\left\{, n: J_n leq t, ight\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 o 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 o 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 0 ight\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

:

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 o 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 left\left( 1 + mathbb\left\{E\right\} \left[X_\left\{t-s\right\}\right] ight\right).$

:So

::

:as required.

Asymptotic properties

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

:$lim_\left\{t o 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 o 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\left\{J_\left\{X_t\left\{X_t\right\} leq frac\left\{t\right\}\left\{X_t\right\} leq frac\left\{J_\left\{X_t+1\left\{X_t\right\}$

:for all "t" &ge; 0.

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

::$X_t o infty$

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

::$frac\left\{J_\left\{X_t\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 o mathbb\left\{E\right\}S_1$

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

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

:almost surely.

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

::$frac\left\{1\right\}\left\{t\right\} X_t o frac\left\{1\right\}\left\{mathbb\left\{E\right\}S_1\right\}$

: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 o 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 "F""S" 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

:

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?

olution

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.5"t". 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.5t ight\right) + frac\left\{2-t\right\}\left\{2\right\}left\left( t ight\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_\left\{t o infty\right\} frac\left\{1\right\}\left\{t\right\} Y_t = frac\left\{mathbb\left\{E\right\}W\right\}\left\{mathbb\left\{E\right\}S\right\}= frac\left\{ 4\left(1200t + 200\right) \right\}\left\{ t^2 + 4t - 2t^2 \right\}$

then differentiating with respect to "t":

:$frac\left\{partial\right\}\left\{partial t\right\} frac\left\{ 4\left(1200t + 200\right) \right\}\left\{ t^2 + 4t - 2t^2 \right\} = 4frac\left\{ \left(4t - t^2\right)\left(1200\right) - \left(4 - 2t\right)\left(1200t + 200\right) \right\}\left\{ \left(t^2 + 4t - 2t^2\right)^2 \right\},$

this implies that the turning points satisfy:

:$0 = \left(4t - t^2\right)\left(1200\right) - \left(4 - 2t\right)\left(1200t + 200\right) = 4800t - 1200t^2 -4800t - 800 + 2400t^2 + 400t$

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

and thus

:$0 = 3t^2 + t - 2 = \left(3t -2\right)\left(t+1\right).$

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.

ee also

*Poisson process
*Continuous-time Markov process
*Semi-Markov process
*Queueing theory
*Ruin theory
*Campbell's theorem
*Little's lemma

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Renewal — Renew or renewal may refer to: *Urban renewal, a function of urban planning *Renewal theory, a branch of probability theory *Renewal (journal), a journal of Labour politics (UK) *Renewal (law), the act of renewing an expiring law or act *Renewal… …   Wikipedia

• Queueing theory — is the mathematical study of waiting lines (or s ). The theory enables mathematical analysis of several related processes, including arriving at the (back of the) queue, waiting in the queue (essentially a storage process), and being served by… …   Wikipedia

• Ruin theory — Ruin theory, sometimes referred to as collective risk theory, is a branch of actuarial science that studies an insurer s vulnerability to insolvency based on mathematical modeling of the insurer s surplus.The theory permits the derivation and… …   Wikipedia

• Development of Darwin's theory — Following the inception of Charles Darwin s theory of natural selection in 1838, the development of Darwin s theory to explain the mystery of mysteries of how new species originated was his prime hobby in the background to his main occupation of… …   Wikipedia

• Jewish Renewal — Part of a series of articles on Jews and Judaism …   Wikipedia

• Art Renewal Center — The Art Renewal Center (ARC) is an organization led by Fred Ross dedicated to classical realism in art, as opposed to the Modernist developments of the 20th century. It exists primarily as an online art gallery.Edwards, Alun.… …   Wikipedia

• Chaos theory — This article is about chaos theory in Mathematics. For other uses of Chaos theory, see Chaos Theory (disambiguation). For other uses of Chaos, see Chaos (disambiguation). A plot of the Lorenz attractor for values r = 28, σ = 10, b = 8/3 …   Wikipedia

• Queer theory — is a field of Gender Studies that emerged in the early 1990s out of the fields of gay and lesbian studies and feminist studies. Heavily influenced by the work of Michel Foucault, queer theory builds both upon feminist challenges to the idea that… …   Wikipedia

• Two Stage Theory — The two stage theory (or stagism ) is the Marxist Leninist political theory which argues that underdeveloped countries, such as Tsarist Russia, must first pass through a stage of bourgeois democracy before moving to a socialist stage. [… …   Wikipedia

• DNA damage theory of aging — The DNA damage theory of aging proposes that aging is a consequence of unrepaired DNA damage accumulation. Damage in this context includes chemical reactions that mutate DNA and/or interfere with DNA replication. Although both mitochondrial and… …   Wikipedia