Namespaces
Variants
Actions

Difference between revisions of "Blackwell renewal theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(→‎References: Feller: internal link)
(details)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
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" />:
+
<!--This article has been texified automatically. Since there was no Nroff source code for this article,  
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
  
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;
+
Out of 105 formulas, 105 were replaced by TEX code.-->
  
ii) of the probability of renewal at time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120270/b1202704.png" />;
+
{{TEX|semi-auto}}{{TEX|done}}
 +
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) $t$:
  
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]]].
+
i) of the average number of units replaced in the interval $( t , t + h ]$, where $h$ is fixed;
 +
 
 +
ii) of the probability of renewal at time $t$;
 +
 
 +
iii) of the age, the remaining life and the total life of the (current) unit in operation at time $t$. 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.==
 
==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" />,
+
Let $X _ { 1 } , X _ { 2 } , \ldots$ be a sequence of independent and identically distributed random variables that are non-negative (cf. also [[Random variable|Random variable]]). The value of $X_i$ is to be thought of as the life-length of the $i$th unit. Let, for $n \geq 1$,
  
<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>
+
\begin{equation} \tag{a1} S _ { 0 } = 0, \end{equation}
  
<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>
+
\begin{equation*} S _ { n } = \sum _ { 1 } ^ { n } X _ { i }\; \text { for } \ n \geq 1 , \text { and for } \ t \geq 0 ,\; N ( t ) = k \;\text { if } S _ { k } \leq t < S _ { k + 1 } \;\text { for } k = 0,1, \dots , \end{equation*}
  
<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>
+
\begin{equation*} A ( t ) = t - S _ { N  ( t )} , R ( t ) = S _ { N ( t ) + 1 } - t, \end{equation*}
  
<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>
+
\begin{equation*} L ( t ) = R ( t ) + A ( t ). \end{equation*}
  
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
+
Thus, $S _ { n }$ is the time of the $n$th renewal, $N ( t )$ is the number of units used up to time $t$ excluding the one in operation, $A ( t )$ is the age of the unit in place at time $t$ with $R ( t )$ being its remaining life-time and $L ( t )$ 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>
+
\begin{equation} \tag{a2} U ( t ) \equiv \textsf{E} N ( t ), \end{equation}
  
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" />.
+
where $\mathsf{E} X$ denotes the expected value, or [[Mathematical expectation|mathematical expectation]], of the random variable $X$.
  
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]]].
+
Blackwell's renewal theorem says that for fixed $h > 0$, $U ( t + h ) - U ( t )$ converges as $t \rightarrow \infty$ to $h / \mathsf{E} X _ { 1 }$. 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
+
Let $F ( x ) = \mathsf{P} ( X _ { 1 } \leq x )$ be the distribution function of the random variable $X$ (cf. also [[Distribution function|Distribution function]]); it is assumed that $F ( 0 ) = 0$. The function $F$ is said to be arithmetic if there exist $h > 0$ and $a > 0$ 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>
+
\begin{equation*} \mathsf{P} ( X _ { 1 } = a+ n h \text { for some } n= 0,1 , \ldots ) = 1, \end{equation*}
  
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.
+
i.e. $( X _ { 1 } - a ) / h$ is a non-negative integer-valued random variable. The largest $h > 0$ for which this holds is called the span; see [[#References|[a5]]]. $F$ is said to be non-arithmetic if it is not arithmetic.
  
 
==Blackwell's renewal theorem.==
 
==Blackwell's renewal theorem.==
Line 36: Line 44:
  
 
===Arithmetic case.===
 
===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" />,
+
Let $F$ be arithmetic with $a = 0$ and span $h = 1$. Let, for $n \geq 0$,
  
<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>
+
\begin{equation} \tag{a3} u _ { n } \equiv \mathsf{P} ( S _ { k } = n \text{ for some } k \geq 0 ), \end{equation}
  
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
+
i.e. the probability that there is a renewal at time $n$. 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>
+
\begin{equation} \tag{a4} \operatorname { lim } _ { n } u _ { n } = \frac { 1 } { \mathsf{E} X _ { 1 } }. \end{equation}
  
 
===Non-arithmetic case.===
 
===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" />,
+
Let $F$ be non-arithmetic. Then for any $h > 0$,
  
<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>
+
\begin{equation} \tag{a5} \operatorname { lim } _ { t \rightarrow \infty } ( U ( t + h ) - U ( t ) ) = \frac { h } { \mathsf{E} X _ { 1 } }. \end{equation}
  
 
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]]]).
 
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.==
 
==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
+
There is an equivalent of this result, known as the key renewal theorem. It is as follows. Since $N ( t ) = \sum _ { 1 } ^ { \infty } I ( S _ { k } \leq t )$, its expected value $U ( t ) = \sum _ { 1 } ^ { \infty } \textsf{P} ( S _ { k } \leq t ) = \sum _ { 1 } ^ { \infty } F ^ { ( k ) } ( t )$, where $F ^ { ( k ) }$ is the $k$ fold convolution of $F$, 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>
 
 
 
<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/b12027055.png" /></td> </tr></table>
 
  
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
+
\begin{equation*} F ^ { ( 0 ) } ( u ) = I _ { [ 0 , \infty ) } ^ { ( u ) } \end{equation*}
 +
\[
 +
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 $\{ p _j  \} _ { 0 } ^ { \infty }$ and forcing sequence $\{ b _ { n } \}$ is an equation for a sequence $\{ a _ { n } \}$ 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>
+
\begin{equation} \tag{a6} a _ { n } = b _ { n } + \sum _ { 0 } ^ { n } a _ { n  - j} p _ { j } ,\; n = 0,1, \dots , \end{equation}
  
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" />.
+
where it is assumed that $p _ { 0 } = 0$, $p _ { j } \geq 0$ and $\sum _ { 1 } ^ { \infty } p _ { j } = 1$.
  
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
+
A renewal equation with distribution $F$ and forcing function $b ( . )$ is an equation for a function $a ( . )$ where both $a ( . )$ and $b ( . )$ are functions $\mathbf{R} ^ { + } \equiv [ 0 , \infty ) \rightarrow \mathbf{R}$ 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>
+
\begin{equation} \tag{a7} a ( t ) = b ( t ) + \int _ { ( 0 , t ] } a ( t - u ) d F ( u ) \text { for } t \geq 0. \end{equation}
  
 
It can be shown that (a6) and (a7) have unique solutions given by, respectively,
 
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>
+
\begin{equation} \tag{a8} a _ { n } = \sum _ { 0 } ^ { n } b _ { n  - j} u _ { j } ,\; n \geq 0, \end{equation}
  
 
and
 
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>
+
\begin{equation} \tag{a9} a ( t ) = \int _ { ( 0 , t ] } b ( t - s ) U ( d s ), \end{equation}
  
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).
+
where $\{ u _ { j } \}$ is as in (a3) and $U ( . )$ 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" />,
+
A function $b : [ 0 , \infty ) \rightarrow \mathbf R$ is called directly Riemann integrable if for every $h > 0$,
  
<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>
+
\begin{equation*} \sum _ { n = 0 } ^ { \infty } ( | \overline { m } _ { n } ( h ) | + | m \underline { \square } _ { n } ( h ) | ) < \infty, \end{equation*}
  
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.
+
and as $h \downarrow 0$ and $\sum _ { i } \overline { m } _ { n } ( h ) h$ and $\sum m \underline { \square } _ { n } ( h ) h$ approach the same limit, where $\overline { m } _ { n} ( h )$ and $m \underline { \square } _ { n } ( h )$ are, respectively, the supremum and infimum of $\{ b ( t ) : n h \leq t < ( n + 1 ) h \}$. This common limit is usually denoted by $\int _ { 0 } ^ { \infty } b ( u ) d u$; see [[#References|[a5]]]. A very useful equivalent of the Blackwell renewal theorem is the key renewal theorem.
  
 
===Arithmetic case.===
 
===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
+
Let $\{ b _ { n } \}$ satisfy $\sum | b _ { n } | < \infty$ and $\operatorname { gcd } \{ j : p_j > 0 \} = 1$. Then the unique solution $\{ a _ { n } \}$ 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>
+
\begin{equation*} \operatorname { lim } _ { n } a _ { n } = \frac { \sum _ { 0 } ^ { \infty } b _ { j } } { \sum _ { 0 } ^ { \infty } j p _ { j } }. \end{equation*}
  
 
===Non-arithmetic case.===
 
===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
+
Let $F$ be non-arithmetic and let $b ( . )$ be directly Riemann integrable. Then the unique solution $a ( . )$ 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>
+
\begin{equation*} \operatorname { lim } _ { t \rightarrow \infty } a ( t ) = \frac { \int _ { 0 } ^ { \infty } b ( u ) d u } { \int _ { 0 } ^ { \infty } u d F ( u ) }. \end{equation*}
  
 
==Application.==
 
==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
+
A random or [[Stochastic process|stochastic process]] $\{ Z ( t ) : t \geq 0 \}$ in discrete or continuous time is called regenerative if there exist a sequence of random times $0 \leq T _ { 0 } < T _ { 1 } < \ldots$ such that $\eta _ { i + 1 } \equiv \{ Z ( u ) : T _ { i } \leq u < T _ { i + 1 } , T _ { i + 1 } - T _ { i } \}$, $i \geq 0$, are stochastically independent, identically distributed and independent of $\eta _ { 0 } = \{ Z ( u ) : 0 \leq u < T _ { 0 } \}$. Let $h$ be a [[Measurable function|measurable function]] on the state space of $Z$ and $a ( t ) \equiv \mathsf{E} h ( Z ( t ) )$. Then $a ( t )$ satisfies the renewal equation (a7) with $b ( t ) = \mathsf{ E}h  ( \{ Z ( t ) : T _ { 1 } > t \} )$ and $F ( x ) = \mathsf{P} ( T _ { 1 } - T _ { 0 } \leq x )$. So, if the distribution of $T _ { 1 }$ 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>
+
\begin{equation*} \operatorname { lim } _ { t \rightarrow \infty } \mathsf{E}\operatorname { h } ( Z ( t ) ) = \frac { \int _ { 0 } ^ { \infty } b ( u ) d u } { \int _ { 0 } ^ { \infty } \mathsf{P} ( T _ { 1 } > u ) d u } = \end{equation*}
  
<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>
+
\begin{equation*} = \frac { \mathsf{E} \int _ { 0 } ^ { T _ { 1 } } h ( Z ( u ) ) d u } {  \mathsf{E} ( T _ { 1 } ) }. \end{equation*}
  
 
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]]].
 
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====
 
====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>
+
<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>

Latest revision as of 19:03, 23 January 2024

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) and objects of interest are the behaviour for large (time) $t$:

i) of the average number of units replaced in the interval $( t , t + h ]$, where $h$ is fixed;

ii) of the probability of renewal at time $t$;

iii) of the age, the remaining life and the total life of the (current) unit in operation at time $t$. The mathematical theory of such processes is called renewal theory and Blackwell's renewal theorem plays a central role in it. See [a2], [a4], [a5].

Mathematical framework.

Let $X _ { 1 } , X _ { 2 } , \ldots$ be a sequence of independent and identically distributed random variables that are non-negative (cf. also Random variable). The value of $X_i$ is to be thought of as the life-length of the $i$th unit. Let, for $n \geq 1$,

\begin{equation} \tag{a1} S _ { 0 } = 0, \end{equation}

\begin{equation*} S _ { n } = \sum _ { 1 } ^ { n } X _ { i }\; \text { for } \ n \geq 1 , \text { and for } \ t \geq 0 ,\; N ( t ) = k \;\text { if } S _ { k } \leq t < S _ { k + 1 } \;\text { for } k = 0,1, \dots , \end{equation*}

\begin{equation*} A ( t ) = t - S _ { N ( t )} , R ( t ) = S _ { N ( t ) + 1 } - t, \end{equation*}

\begin{equation*} L ( t ) = R ( t ) + A ( t ). \end{equation*}

Thus, $S _ { n }$ is the time of the $n$th renewal, $N ( t )$ is the number of units used up to time $t$ excluding the one in operation, $A ( t )$ is the age of the unit in place at time $t$ with $R ( t )$ being its remaining life-time and $L ( t )$ its total life-time. Let

\begin{equation} \tag{a2} U ( t ) \equiv \textsf{E} N ( t ), \end{equation}

where $\mathsf{E} X$ denotes the expected value, or mathematical expectation, of the random variable $X$.

Blackwell's renewal theorem says that for fixed $h > 0$, $U ( t + h ) - U ( t )$ converges as $t \rightarrow \infty$ to $h / \mathsf{E} X _ { 1 }$. A precise statement is given below. This was proved by D. Blackwell; see [a2]. This result has several variants and consequences and applications in applied probability theory; see [a1].

Let $F ( x ) = \mathsf{P} ( X _ { 1 } \leq x )$ be the distribution function of the random variable $X$ (cf. also Distribution function); it is assumed that $F ( 0 ) = 0$. The function $F$ is said to be arithmetic if there exist $h > 0$ and $a > 0$ such that

\begin{equation*} \mathsf{P} ( X _ { 1 } = a+ n h \text { for some } n= 0,1 , \ldots ) = 1, \end{equation*}

i.e. $( X _ { 1 } - a ) / h$ is a non-negative integer-valued random variable. The largest $h > 0$ for which this holds is called the span; see [a5]. $F$ is said to be non-arithmetic if it is not arithmetic.

Blackwell's renewal theorem.

Arithmetic case.

Let $F$ be arithmetic with $a = 0$ and span $h = 1$. Let, for $n \geq 0$,

\begin{equation} \tag{a3} u _ { n } \equiv \mathsf{P} ( S _ { k } = n \text{ for some } k \geq 0 ), \end{equation}

i.e. the probability that there is a renewal at time $n$. Then

\begin{equation} \tag{a4} \operatorname { lim } _ { n } u _ { n } = \frac { 1 } { \mathsf{E} X _ { 1 } }. \end{equation}

Non-arithmetic case.

Let $F$ be non-arithmetic. Then for any $h > 0$,

\begin{equation} \tag{a5} \operatorname { lim } _ { t \rightarrow \infty } ( U ( t + h ) - U ( t ) ) = \frac { h } { \mathsf{E} X _ { 1 } }. \end{equation}

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

Key renewal theorem.

There is an equivalent of this result, known as the key renewal theorem. It is as follows. Since $N ( t ) = \sum _ { 1 } ^ { \infty } I ( S _ { k } \leq t )$, its expected value $U ( t ) = \sum _ { 1 } ^ { \infty } \textsf{P} ( S _ { k } \leq t ) = \sum _ { 1 } ^ { \infty } F ^ { ( k ) } ( t )$, where $F ^ { ( k ) }$ is the $k$ fold convolution of $F$, defined by

\begin{equation*} F ^ { ( 0 ) } ( u ) = I _ { [ 0 , \infty ) } ^ { ( u ) } \end{equation*} \[ 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 $\{ p _j \} _ { 0 } ^ { \infty }$ and forcing sequence $\{ b _ { n } \}$ is an equation for a sequence $\{ a _ { n } \}$ that satisfies

\begin{equation} \tag{a6} a _ { n } = b _ { n } + \sum _ { 0 } ^ { n } a _ { n - j} p _ { j } ,\; n = 0,1, \dots , \end{equation}

where it is assumed that $p _ { 0 } = 0$, $p _ { j } \geq 0$ and $\sum _ { 1 } ^ { \infty } p _ { j } = 1$.

A renewal equation with distribution $F$ and forcing function $b ( . )$ is an equation for a function $a ( . )$ where both $a ( . )$ and $b ( . )$ are functions $\mathbf{R} ^ { + } \equiv [ 0 , \infty ) \rightarrow \mathbf{R}$ that are Borel measurable and bounded on finite intervals and satisfy

\begin{equation} \tag{a7} a ( t ) = b ( t ) + \int _ { ( 0 , t ] } a ( t - u ) d F ( u ) \text { for } t \geq 0. \end{equation}

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

\begin{equation} \tag{a8} a _ { n } = \sum _ { 0 } ^ { n } b _ { n - j} u _ { j } ,\; n \geq 0, \end{equation}

and

\begin{equation} \tag{a9} a ( t ) = \int _ { ( 0 , t ] } b ( t - s ) U ( d s ), \end{equation}

where $\{ u _ { j } \}$ is as in (a3) and $U ( . )$ is as in (a2).

A function $b : [ 0 , \infty ) \rightarrow \mathbf R$ is called directly Riemann integrable if for every $h > 0$,

\begin{equation*} \sum _ { n = 0 } ^ { \infty } ( | \overline { m } _ { n } ( h ) | + | m \underline { \square } _ { n } ( h ) | ) < \infty, \end{equation*}

and as $h \downarrow 0$ and $\sum _ { i } \overline { m } _ { n } ( h ) h$ and $\sum m \underline { \square } _ { n } ( h ) h$ approach the same limit, where $\overline { m } _ { n} ( h )$ and $m \underline { \square } _ { n } ( h )$ are, respectively, the supremum and infimum of $\{ b ( t ) : n h \leq t < ( n + 1 ) h \}$. This common limit is usually denoted by $\int _ { 0 } ^ { \infty } b ( u ) d u$; see [a5]. A very useful equivalent of the Blackwell renewal theorem is the key renewal theorem.

Arithmetic case.

Let $\{ b _ { n } \}$ satisfy $\sum | b _ { n } | < \infty$ and $\operatorname { gcd } \{ j : p_j > 0 \} = 1$. Then the unique solution $\{ a _ { n } \}$ to (a6) is given by (a8) and

\begin{equation*} \operatorname { lim } _ { n } a _ { n } = \frac { \sum _ { 0 } ^ { \infty } b _ { j } } { \sum _ { 0 } ^ { \infty } j p _ { j } }. \end{equation*}

Non-arithmetic case.

Let $F$ be non-arithmetic and let $b ( . )$ be directly Riemann integrable. Then the unique solution $a ( . )$ to (a7) is given by (a9) and

\begin{equation*} \operatorname { lim } _ { t \rightarrow \infty } a ( t ) = \frac { \int _ { 0 } ^ { \infty } b ( u ) d u } { \int _ { 0 } ^ { \infty } u d F ( u ) }. \end{equation*}

Application.

A random or stochastic process $\{ Z ( t ) : t \geq 0 \}$ in discrete or continuous time is called regenerative if there exist a sequence of random times $0 \leq T _ { 0 } < T _ { 1 } < \ldots$ such that $\eta _ { i + 1 } \equiv \{ Z ( u ) : T _ { i } \leq u < T _ { i + 1 } , T _ { i + 1 } - T _ { i } \}$, $i \geq 0$, are stochastically independent, identically distributed and independent of $\eta _ { 0 } = \{ Z ( u ) : 0 \leq u < T _ { 0 } \}$. Let $h$ be a measurable function on the state space of $Z$ and $a ( t ) \equiv \mathsf{E} h ( Z ( t ) )$. Then $a ( t )$ satisfies the renewal equation (a7) with $b ( t ) = \mathsf{ E}h ( \{ Z ( t ) : T _ { 1 } > t \} )$ and $F ( x ) = \mathsf{P} ( T _ { 1 } - T _ { 0 } \leq x )$. So, if the distribution of $T _ { 1 }$ is non-arithmetic, then from the key renewal theorem one can conclude that

\begin{equation*} \operatorname { lim } _ { t \rightarrow \infty } \mathsf{E}\operatorname { h } ( Z ( t ) ) = \frac { \int _ { 0 } ^ { \infty } b ( u ) d u } { \int _ { 0 } ^ { \infty } \mathsf{P} ( T _ { 1 } > u ) d u } = \end{equation*}

\begin{equation*} = \frac { \mathsf{E} \int _ { 0 } ^ { T _ { 1 } } h ( Z ( u ) ) d u } { \mathsf{E} ( T _ { 1 } ) }. \end{equation*}

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 [a1].

References

[a1] S. Asmussen, "Applied probability and queues", Wiley (1987)
[a2] D. Blackwell, "A renewal theorem" Duke Math. J., 15 (1948) pp. 145–150
[a3] T. Lindvall, "Lectures on the coupling method", II, Wiley (1992) (Edition: Second)
[a4] W. Feller, "An introduction to probability theory and its applications", 1, Wiley (1968) (Edition: Third)
[a5] W. Feller, "An introduction to probability theory and its applications", 2, Wiley (1970) (Edition: Second)
How to Cite This Entry:
Blackwell renewal theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Blackwell_renewal_theorem&oldid=25938
This article was adapted from an original article by K.B. Athreya (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article