View source for Blackwell renewal theorem

Consider a piece of equipment that has a finite but random life-time. Suppose one starts with a new one and, after that fails, replaces it with a second new one and, after that one fails, replaces it with a third new one and so on indefinitely. Such a process is called a renewal process (cf. also [[Renewal theory|Renewal theory]]) and objects of interest are the behaviour for large (time) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b1202701.png" />:

i) of the average number of units replaced in the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b1202702.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b1202703.png" /> is fixed;

ii) of the probability of renewal at time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b1202704.png" />;

iii) of the age, the remaining life and the total life of the (current) unit in operation at time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b1202705.png" />. The mathematical theory of such processes is called [[Renewal theory|renewal theory]] and Blackwell's renewal theorem plays a central role in it. See [[#References|[a2]]], [[#References|[a4]]], [[#References|[a5]]].

==Mathematical framework.==
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b1202706.png" /> be a sequence of independent and identically distributed random variables that are non-negative (cf. also [[Random variable|Random variable]]). The value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b1202707.png" /> is to be thought of as the life-length of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b1202708.png" />th unit. Let, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b1202709.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027010.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027011.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027012.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027013.png" /></td> </tr></table>

Thus, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027014.png" /> is the time of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027015.png" />th renewal, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027016.png" /> is the number of units used up to time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027017.png" /> excluding the one in operation, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027018.png" /> is the age of the unit in place at time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027019.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027020.png" /> being its remaining life-time and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027021.png" /> its total life-time. Let

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027022.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a2)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027023.png" /> denotes the expected value, or [[Mathematical expectation|mathematical expectation]], of the random variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027024.png" />.

Blackwell's renewal theorem says that for fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027025.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027026.png" /> converges as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027027.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027028.png" />. A precise statement is given below. This was proved by D. Blackwell; see [[#References|[a2]]]. This result has several variants and consequences and applications in applied probability theory; see [[#References|[a1]]].

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027029.png" /> be the distribution function of the random variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027030.png" /> (cf. also [[Distribution function|Distribution function]]); it is assumed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027031.png" />. The function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027032.png" /> is said to be arithmetic if there exist <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027033.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027034.png" /> such that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027035.png" /></td> </tr></table>

i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027036.png" /> is a non-negative integer-valued random variable. The largest <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027037.png" /> for which this holds is called the span; see [[#References|[a5]]]. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027038.png" /> is said to be non-arithmetic if it is not arithmetic.

==Blackwell's renewal theorem.==


===Arithmetic case.===
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027039.png" /> be arithmetic with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027040.png" /> and span <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027041.png" />. Let, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027042.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027043.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a3)</td></tr></table>

i.e. the probability that there is a renewal at time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027044.png" />. Then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027045.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a4)</td></tr></table>

===Non-arithmetic case.===
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027046.png" /> be non-arithmetic. Then for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027047.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027048.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a5)</td></tr></table>

The arithmetic case was proved by P. Erdös, W. Feller and H. Pollard; see [[#References|[a4]]]. The non-arithmetic case was proved by Blackwell; see [[#References|[a5]]]. More recently, proofs of these using the coupling method have become available (see [[#References|[a3]]]).

==Key renewal theorem.==
There is an equivalent of this result, known as the key renewal theorem. It is as follows. Since <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027049.png" />, its expected value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027050.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027051.png" /> is the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027052.png" /> fold convolution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027053.png" />, defined by

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027054.png" /></td> </tr></table>
\[
F^k(t) \equiv \int_{(0,t]} F^{(k-1)}(t-u) \, \rd F(u) \, , \quad k \ge 1 \, .
\]
A discrete renewal equation, with probability distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027056.png" /> and forcing sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027057.png" /> is an equation for a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027058.png" /> that satisfies

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027059.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a6)</td></tr></table>

where it is assumed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027060.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027061.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027062.png" />.

A renewal equation with distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027063.png" /> and forcing function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027064.png" /> is an equation for a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027065.png" /> where both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027066.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027067.png" /> are functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027068.png" /> that are Borel measurable and bounded on finite intervals and satisfy

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027069.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a7)</td></tr></table>

It can be shown that (a6) and (a7) have unique solutions given by, respectively,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027070.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a8)</td></tr></table>

and

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027071.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a9)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027072.png" /> is as in (a3) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027073.png" /> is as in (a2).

A function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027074.png" /> is called directly Riemann integrable if for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027075.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027076.png" /></td> </tr></table>

and as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027077.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027078.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027079.png" /> approach the same limit, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027080.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027081.png" /> are, respectively, the supremum and infimum of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027082.png" />. This common limit is usually denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027083.png" />; see [[#References|[a5]]]. A very useful equivalent of the Blackwell renewal theorem is the key renewal theorem.

===Arithmetic case.===
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027084.png" /> satisfy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027085.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027086.png" />. Then the unique solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027087.png" /> to (a6) is given by (a8) and

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027088.png" /></td> </tr></table>

===Non-arithmetic case.===
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027089.png" /> be non-arithmetic and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027090.png" /> be directly Riemann integrable. Then the unique solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027091.png" /> to (a7) is given by (a9) and

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027092.png" /></td> </tr></table>

==Application.==
A random or [[Stochastic process|stochastic process]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027093.png" /> in discrete or continuous time is called regenerative if there exist a sequence of random times <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027094.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027095.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027096.png" />, are stochastically independent, identically distributed and independent of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027097.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027098.png" /> be a [[Measurable function|measurable function]] on the state space of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b12027099.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b120270100.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b120270101.png" /> satisfies the renewal equation (a7) with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b120270102.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b120270103.png" />. So, if the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b120270104.png" /> is non-arithmetic, then from the key renewal theorem one can conclude that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b120270105.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b120270106.png" /></td> </tr></table>

This, in turn, can be used to prove the convergence to an equilibrium distribution for many regenerative processes, including positive recurrent irreducible Markov chains; see [[#References|[a1]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> S. Asmussen, "Applied probability and queues", Wiley (1987)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> D. Blackwell, "A renewal theorem" ''Duke Math. J.'', '''15''' (1948) pp. 145–150</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> T. Lindvall, "Lectures on the coupling method", '''II''', Wiley (1992) (Edition: Second)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> W. Feller, [[Feller, "An introduction to probability theory and its applications"|"An introduction to probability theory and its applications"]], '''1''', Wiley (1968) (Edition: Third)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> W. Feller, [[Feller, "An introduction to probability theory and its  applications"|"An introduction to probability theory and its  applications"]], '''2''', Wiley (1970) (Edition: Second)</TD></TR></table>