Renewal theory

Short description: Branch of probability 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 (IID) holding times that have finite expectation. 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 m(t) (expected number of arrivals) and reward function g(t) (expected reward value) 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 m′(t) 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; comparing the long-term benefits of different insurance policies; and modelling the transmission of infectious disease, where "One of the most widely adopted means of inference of the reproduction number is via the renewal equation".[1] 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.

## Contents

* 1 Renewal processes
* 1.1 Introduction
* 1.2 Formal definition
* 1.3 Interpretation
* 2 Renewal-reward processes
* 2.1 Interpretation
* 3 Renewal function
* 3.1 Elementary renewal theorem
* 3.2 Elementary renewal theorem for renewal reward processes
* 3.3 Renewal equation
* 4 Key renewal theorem
* 4.1 Renewal theorem
* 5 Asymptotic properties
* 6 Inspection paradox
* 7 Superposition
* 8 Example application
* 9 See also
* 10 Notes
* 11 References

## 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 (usually starting at zero) which has independent exponentially distributed holding times at each integer i before advancing to the next integer, i+1. 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 (IID) and have finite mean.

### Formal definition

Sample evolution of a renewal process with holding times Si and jump times Jn.

Let (Si)i≥1 be a sequence of positive independent identically distributed random variables with finite expected value

0<E⁡[Si]<∞.

We refer to the random variable Si as the "i-th holding time".

Define for each n > 0 :

Jn=∑i=1nSi,

each Jn is referred to as the "n-th jump time" and the intervals [Jn,Jn+1] are called "renewal intervals".

Then (Xt)t≥0 is given by random variable

Xt=∑n=1∞𝕀{Jn≤t}=sup⁡{n:Jn≤t}

where 𝕀{Jn≤t} is the indicator function

𝕀{Jn≤t}={1,if Jn≤t0,otherwise

(Xt)t≥0 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 {Si:i≥1} 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,[2] as the exponential distribution is the unique continuous random variable with the property of memorylessness.

## Renewal-reward processes

Sample evolution of a renewal-reward process with holding times Si, jump times Jn and rewards Wi

Let W1,W2,… be a sequence of IID random variables (rewards) satisfying

E⁡|Wi|<∞.

Then the random variable

Yt=∑i=1XtWi

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

The random variable Yt depends on two sequences: the holding times S1,S2,… and the rewards W1,W2,… These two sequences need not be independent. In particular, Wi may be a function of Si.

### Interpretation

In the context of the above interpretation of the holding times as the time between successive malfunctions of a machine, the "rewards" W1,W2,… (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 Si. 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" Wi are the successive (random) financial losses/gains resulting from successive eggs (i = 1,2,3,...) and Yt 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 t:

m(t)=E⁡[Xt].

### Elementary renewal theorem

The renewal function satisfies

limt->∞1tm(t)=1E⁡[S1].

Proof

The strong law of large numbers for renewal processes implies

limt->∞Xtt=1E⁡[S1].

To prove the elementary renewal theorem, it is sufficient to show that {Xtt;t≥0} is uniformly integrable.

To do this, consider some truncated renewal process where the holding times are defined by Sn‾=a𝕀⁡{Sn>a} where a is a point such that 0<F(a)=p<1 which exists for all non-deterministic renewal processes. This new renewal process X‾t is an upper bound on Xt and its renewals can only occur on the lattice {na;n∈ℕ}. Furthermore, the number of renewals at each time is geometric with parameter p. So we have

Xt‾≤∑i=1[at]Geometric⁡(p)E⁡[Xt‾2]≤C1t+C2t2P(Xtt>x)≤E⁡[Xt2]t2x2≤E⁡[Xt‾2]t2x2≤Cx2.

### Elementary renewal theorem for renewal reward processes

We define the reward function:

g(t)=E⁡[Yt].

The reward function satisfies

limt->∞1tg(t)=E⁡[W1]E⁡[S1].

### Renewal equation

The renewal function satisfies

m(t)=FS(t)+∫0tm(t−s)fS(s)ds

where FS is the cumulative distribution function of S1 and fS is the corresponding probability density function.

Proof[3]

We may iterate the expectation about the first holding time:

m(t)=E⁡[Xt]=E⁡[E⁡(Xt∣S1)].

From the definition of the renewal process, we have

E⁡(Xt∣S1=s)=𝕀{t≥s}(1+E⁡[Xt−s]).

m(t)=E⁡[Xt]=E⁡[E⁡(Xt∣S1)]=∫0∞E⁡(Xt∣S1=s)fS(s)ds=∫0∞𝕀{t≥s}(1+E⁡[Xt−s])fS(s)ds=∫0t(1+m(t−s))fS(s)ds=FS(t)+∫0tm(t−s)fS(s)ds,

as required.

## Key renewal theorem

Let X be a renewal process with renewal function m(t) and interrenewal mean μ. Let g:[0,∞)->[0,∞) be a function satisfying:

* ∫0∞g(t)dt<∞
* g is monotone and non-increasing

The key renewal theorem states that, as t->∞:[4]

∫0tg(t−x)m′(x)dx->1μ∫0∞g(x)dx

### Renewal theorem

Considering g(x)=𝕀[0,h](x) for any h>0 gives as a special case the renewal theorem:[5]

m(t+h)−m(t)->hμ as t->∞

The result can be proved using integral equations or by a coupling argument.[6] 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.[4]

## 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 (Xt)t≥0 is a renewal process and (Yt)t≥0 is a renewal-reward process then:

limt->∞1tXt=1E⁡[S1][7]

limt->∞1tYt=1E⁡[S1]E⁡[W1]

almost surely.

Proof

First consider (Xt)t≥0. By definition we have:

JXt≤t≤JXt+1

for all t≥0 and so

JXtXt≤tXt≤JXt+1Xt

for all t ≥ 0\.

Now since 0<E⁡[Si]<∞ we have:

Xt->∞

as t->∞ almost surely (with probability 1). Hence:

JXtXt=Jnn=1n∑i=1nSi->E⁡[S1]

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

JXt+1Xt=JXt+1Xt+1Xt+1Xt=Jn+1n+1n+1n->E⁡[S1]⋅1

almost surely.

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

1tXt->1E⁡[S1]

almost surely.[4]

Next consider (Yt)t≥0. We have

1tYt=Xtt1XtYt->1E⁡[S1]⋅E⁡[W1]

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

Renewal processes additionally have a property analogous to the central limit theorem:[7]

Xt−t/μtσ2/μ3->𝒩(0,1)

## Inspection paradox

The renewal interval determined by the random point t (shown in red) is stochastically larger than the first renewal interval.

See also: List of paradoxes § Mathematics

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:

P⁡(SXt+1>x)≥P⁡(S1>x)=1−FS(x)

where FS is the cumulative distribution function of the IID holding times Si. A vivid example is the bus waiting time paradox: For a given random distribution of bus arrivals, the average rider at a bus stop observes more delays than the average operator of the buses.

The resolution of the paradox is that our sampled distribution at time t is size-biased (see sampling bias), in that the likelihood an interval is chosen is proportional to its size. However, a renewal interval of average size is not size-biased.

Proof

Observe that the last jump-time before t is JXt; and that the renewal interval containing t is SXt+1. Then

P⁡(SXt+1>x)=∫0∞P⁡(SXt+1>x∣JXt=s)fJXt(s)ds=∫0∞P⁡(SXt+1>x|SXt+1>t−s)fJXt(s)ds=∫0∞P⁡(SXt+1>x,SXt+1>t−s)P⁡(SXt+1>t−s)fJXt(s)ds=∫0∞1−F(max⁡{x,t−s})1−F(t−s)fJXt(s)ds=∫0∞min⁡{1−F(x)1−F(t−s),1−F(t−s)1−F(t−s)}fJXt(s)ds=∫0∞min⁡{1−F(x)1−F(t−s),1}fJXt(s)ds≥∫0∞(1−F(x))fJXt(s)ds=1−F(x)=P⁡(S1>x),

since both 1−F(x)1−F(t−s) and 1 are greater than or equal to 1−F(x) for all values of s.

## Superposition

Unless the renewal process is a Poisson process, the superposition (sum) of two independent renewal processes is not a renewal process.[8] However, such processes can be described within a larger class of processes called the Markov-renewal processes.[9] However, the cumulative distribution function of the first inter-event time in the superposition process is given by[10]

R(t)=1−∑k=1Kαk∑l=1Kαl(1−Rk(t))∏j=1,j≠kKαj∫t∞(1−Rj(u))du

where Rk(t) and αk > 0 are the CDF of the inter-event times and the arrival rate of process k.[11]

## 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?

Solution

The lifetime of the n machines can be modeled as n independent concurrent renewal-reward processes, so it is sufficient to consider the case n=1. Denote this process by (Yt)t≥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 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:

E⁡[S]=E⁡[S∣fails before t]⋅P⁡[fails before t]+E⁡[S∣does not fail before t]⋅P⁡[does not fail before t]=0.5t(t2)+t(2−t2)

and the expected cost W per machine is:

E⁡[W]=E⁡[W∣fails before t]⋅P⁡(fails before t)+E⁡[W∣does not fail before t]⋅P⁡(does not fail before t)=2600(t2)+200(2−t2)=1200t+200.

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

1tYt≃E⁡[W]E⁡[S]=4(1200t+200)t2+4t−2t2

then differentiating with respect to t:

∂∂t4(1200t+200)t2+4t−2t2=4(4t−t2)(1200)−(4−2t)(1200t+200)(t2+4t−2t2)2,

this implies that the turning points satisfy:

0=(4t−t2)(1200)−(4−2t)(1200t+200)=4800t−1200t2−4800t−800+2400t2+400t=−800+400t+1200t2,

and thus

0=3t2+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.

## See also

* Campbell's theorem (probability)
* Compound Poisson process
* Continuous-time Markov process
* Little's lemma
* Lotka's integral equation
* Palm–Khintchine theorem
* Poisson process
* Queueing theory
* Residual time
* Ruin theory
* Semi-Markov process
* Von Foerster equation

This article includes a list of general references, but it remains largely unverified because it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (July 2010) (Learn how and when to remove this template message)

|

## Notes

1. ↑ Green, William D.; Ferguson, Neil M.; Cori, Anne (2022). "Inferring the reproduction number using the renewal equation in heterogeneous epidemics". Journal of the Royal Society Interface 19 (188). doi:10.1098/rsif.2021.0429. PMID 35350879.
2. ↑ Grimmett & Stirzaker (1992), p. 393.
3. ↑ Grimmett & Stirzaker (1992), p. 390.
4. ↑ 4.0 4.1 4.2 Grimmett & Stirzaker (1992), p. 395.
5. ↑ Feller (1971), p. 347–351.
6. ↑ Grimmett & Stirzaker (1992), p. 394–5.
7. ↑ 7.0 7.1 Grimmett & Stirzaker (1992), p. 394.
8. ↑ Grimmett & Stirzaker (1992), p. 405.
9. ↑ Çinlar, Erhan (1969). "Markov Renewal Theory". Advances in Applied Probability (Applied Probability Trust) 1 (2): 123–187. doi:10.2307/1426216.
10. ↑ Lawrence, A. J. (1973). "Dependency of Intervals Between Events in Superposition Processes". Journal of the Royal Statistical Society. Series B (Methodological) 35 (2): 306–315. doi:10.1111/j.2517-6161.1973.tb00960.x. formula 4.1
11. ↑ Choungmo Fofack, Nicaise; Nain, Philippe; Neglia, Giovanni; Towsley, Don (6 March 2012). Analysis of TTL-based Cache Networks. Proceedings of 6th International Conference on Performance Evaluation Methodologies and Tools (report). Retrieved Nov 15, 2012.

## References

* Cox, David (1970). Renewal Theory. London: Methuen & Co.. p. 142. ISBN 0-412-20570-X.
* Doob, J. L. (1948). "Renewal Theory From the Point of View of the Theory of Probability". Transactions of the American Mathematical Society 63 (3): 422–438. doi:10.2307/1990567. https://www.ams.org/journals/tran/1948-063-03/S0002-9947-1948-0025098-8/S0002-9947-1948-0025098-8.pdf.
* Feller, William (1971). An introduction to probability theory and its applications. 2 (second ed.). Wiley.
* Grimmett, G. R.; Stirzaker, D. R. (1992). Probability and Random Processes (second ed.). Oxford University Press. ISBN 0-19-857222-0.
* Smith, Walter L. (1958). "Renewal Theory and Its Ramifications". Journal of the Royal Statistical Society, Series B 20 (2): 243–302. doi:10.1111/j.2517-6161.1958.tb00294.x.
* Wanli Wang, Johannes H. P. Schulz, Weihua Deng, and Eli Barkai (2018). "Renewal theory with fat-tailed distributed sojourn times: Typical versus rare". Phys. Rev. E 98 (4). doi:10.1103/PhysRevE.98.042139. Bibcode: 2018PhRvE..98d2139W.

* v
* t
* e

Stochastic processes

Discrete time|

* Bernoulli process
* Branching process
* Chinese restaurant process
* Galton–Watson process
* Independent and identically distributed random variables
* Markov chain
* Moran process
* Random walk
* Loop-erased
* Self-avoiding
* Biased
* Maximal entropy

Continuous time|

* Bessel process
* Birth–death process
* Brownian motion
* Bridge
* Excursion
* Fractional
* Geometric
* Meander
* Cauchy process
* Contact process
* Continuous-time random walk
* Cox process
* Diffusion process
* Empirical process
* Feller process
* Fleming–Viot process
* Gamma process
* Geometric process
* Hunt process
* Interacting particle systems
* Itô diffusion
* Itô process
* Jump diffusion
* Jump process
* Lévy process
* Local time
* Markov additive process
* McKean–Vlasov process
* Ornstein–Uhlenbeck process
* Poisson process
* Compound
* Non-homogeneous
* Point process
* Schramm–Loewner evolution
* Semimartingale
* Sigma-martingale
* Stable process
* Superprocess
* Telegraph process
* Variance gamma process
* Wiener process
* Wiener sausage

Both|

* Branching process
* Galves–Löcherbach model
* Gaussian process
* Hidden Markov model (HMM)
* Markov process
* Martingale
* Differences
* Local
* Sub-
* Super-
* Random dynamical system
* Regenerative process
* Renewal process
* Stochastic chains with memory of variable length
* White noise

Fields and other|

* Dirichlet process
* Gaussian random field
* Gibbs measure
* Hopfield model
* Ising model
* Potts model
* Boolean network
* Markov random field
* Percolation
* Pitman–Yor process
* Point process
* Cox
* Poisson
* Random field
* Random graph

Time series models|

* Autoregressive conditional heteroskedasticity (ARCH) model
* Autoregressive integrated moving average (ARIMA) model
* Autoregressive (AR) model
* Autoregressive–moving-average (ARMA) model
* Generalized autoregressive conditional heteroskedasticity (GARCH) model
* Moving-average (MA) model

Financial models|

* Black–Derman–Toy
* Black–Karasinski
* Black–Scholes
* Chen
* Constant elasticity of variance (CEV)
* Cox–Ingersoll–Ross (CIR)
* Garman–Kohlhagen
* Heath–Jarrow–Morton (HJM)
* Heston
* Ho–Lee
* Hull–White
* LIBOR market
* Rendleman–Bartter
* SABR volatility
* Vašíček
* Wilkie

Actuarial models|

* Bühlmann
* Cramér–Lundberg
* Risk process
* Sparre–Anderson

Queueing models|

* Bulk
* Fluid
* Generalized queueing network
* M/G/1
* M/M/1
* M/M/c

Properties|

* Càdlàg paths
* Continuous
* Continuous paths
* Ergodic
* Exchangeable
* Feller-continuous
* Gauss–Markov
* Markov
* Mixing
* Piecewise deterministic
* Predictable
* Progressively measurable
* Self-similar
* Stationary
* Time-reversible

Limit theorems|

* Central limit theorem
* Donsker's theorem
* Doob's martingale convergence theorems
* Ergodic theorem
* Fisher–Tippett–Gnedenko theorem
* Large deviation principle
* Law of large numbers (weak/strong)
* Law of the iterated logarithm
* Maximal ergodic theorem
* Sanov's theorem

Inequalities|

* Burkholder–Davis–Gundy
* Doob's martingale
* Kunita–Watanabe

Tools|

* Cameron–Martin formula
* Convergence of random variables
* Doléans-Dade exponential
* Doob decomposition theorem
* Doob–Meyer decomposition theorem
* Doob's optional stopping theorem
* Dynkin's formula
* Feynman–Kac formula
* Filtration
* Girsanov theorem
* Infinitesimal generator
* Itô integral
* Itô's lemma
* Karhunen–Loève_theorem
* Kolmogorov continuity theorem
* Kolmogorov extension theorem
* Lévy–Prokhorov metric
* Malliavin calculus
* Martingale representation theorem
* Optional stopping theorem
* Prokhorov's theorem
* Quadratic variation
* Reflection principle
* Skorokhod integral
* Skorokhod's representation theorem
* Skorokhod space
* Snell envelope
* Stochastic differential equation
* Tanaka
* Stopping time
* Stratonovich integral
* Uniform integrability
* Usual hypotheses
* Wiener space
* Classical
* Abstract

Disciplines|

* Actuarial mathematics
* Econometrics
* Ergodic theory
* Extreme value theory (EVT)
* Large deviations theory
* Mathematical finance
* Mathematical statistics
* Probability theory
* Queueing theory
* Renewal theory
* Ruin theory
* Statistics
* System on Chip design
* Stochastic analysis
* Time series analysis
* Machine learning

* List of topics
* Category

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Renewal theory. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Renewal_theory&oldid=4154517"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template