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) 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)