Namespaces
Variants
Actions

Difference between revisions of "Renewal theory"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
A branch of [[Probability theory|probability theory]] describing a large range of problems connected with the rejection and renewal of the elements of some system. The principal concepts in renewal theory are those of a renewal process and renewal equation. A renewal process may be described using the classical scheme of sums of independent random variables in the following manner. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r0812501.png" /> be a sequence of independent, non-negative, identically-distributed random variables having distribution function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r0812502.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r0812503.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r0812504.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r0812505.png" />. The renewal process <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r0812506.png" /> is defined as
+
<!--
 +
r0812501.png
 +
$#A+1 = 34 n = 0
 +
$#C+1 = 34 : ~/encyclopedia/old_files/data/R081/R.0801250 Renewal theory
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<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/r/r081/r081250/r0812507.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
If the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r0812508.png" /> are interpreted as the lifetimes of some successively replaceable element, the random variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r0812509.png" /> equals the number of replacements (or renewals) of these elements during time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125010.png" />. The renewal function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125011.png" /> plays an important part in studying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125012.png" />. This function satisfies the renewal equation
+
A branch of [[Probability theory|probability theory]] describing a large range of problems connected with the rejection and renewal of the elements of some system. The principal concepts in renewal theory are those of a renewal process and renewal equation. A renewal process may be described using the classical scheme of sums of independent random variables in the following manner. Let  $  \xi _ {1} , \xi _ {2} , . . . $
 +
be a sequence of independent, non-negative, identically-distributed random variables having distribution function $  F( x) $.
 +
Let  $  \zeta _ {0} = 0 $,
 +
$  \zeta _ {n} = \xi _ {1} + \dots + \xi _ {n} $,
 +
$  n \geq  1 $.  
 +
The renewal process  $  N _ {t} $
 +
is defined as
  
<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/r/r081/r081250/r08125013.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{1 }
 +
N _ {t}  = \max \{ {n } : {\zeta _ {n} \leq  t } \}
 +
.
 +
$$
  
For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125015.png" />, there arises an important special case of the renewal process — the [[Poisson process|Poisson process]], in which
+
If the  $  \xi _ {i} $
 +
are interpreted as the lifetimes of some successively replaceable element, the random variable  $  N _ {i} $
 +
equals the number of replacements (or renewals) of these elements during time  $  t $.  
 +
The renewal function  $  H( t) = {\mathsf E} N _ {t} $
 +
plays an important part in studying  $  N _ {t} $.
 +
This function satisfies the renewal 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/r/r081/r081250/r08125016.png" /></td> </tr></table>
+
$$ \tag{2 }
 +
H ( t)  = \
 +
F ( t) + \int\limits _ { 0 } ^ { t }  H ( t - u)  dF ( u).
 +
$$
  
and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125017.png" />.
+
For  $  F( t) = 1 - e ^ {- \rho t } $,
 +
$  t \geq  0 $,
 +
there arises an important special case of the renewal process — the [[Poisson process|Poisson process]], in which
  
The renewal process <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125018.png" /> and the renewal equation (2) are very important in the study of various theoretical and applied problems in [[Queueing theory|queueing theory]], reliability theory, storage theory, the theory of branching processes (cf. [[Branching process|Branching process]]), etc. A large number of results in renewal theory is connected with the study of the asymptotic properties of the renewal function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125019.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125020.png" />. An elementary renewal theorem states that
+
$$
 +
{\mathsf P} \{ N ( t) = k \}  =
 +
\frac{( \rho t) ^ {k} }{k! }
 +
e ^ {- \rho t } ,\ \
 +
k = 0, 1 \dots
 +
$$
  
<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/r/r081/r081250/r08125021.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
and  $  H( t) = \rho t $.
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125022.png" />. It was shown by D. Blackwell in 1948 (cf. [[#References|[1]]]), that if the distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125023.png" /> is not concentrated on some arithmetical lattice of the type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125024.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125025.png" />, then for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125026.png" />,
+
The renewal process  $  N _ {t} $
 +
and the renewal equation (2) are very important in the study of various theoretical and applied problems in [[Queueing theory|queueing theory]], reliability theory, storage theory, the theory of branching processes (cf. [[Branching process|Branching process]]), etc. A large number of results in renewal theory is connected with the study of the asymptotic properties of the renewal function  $  H( t) $
 +
as  $  t \rightarrow \infty $.  
 +
An elementary renewal theorem states 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/r/r081/r081250/r08125027.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>
+
$$ \tag{3 }
 +
\lim\limits _ {t \rightarrow \infty } \
  
Numerous results are available which generalize and precisize equations (3) and (4) in several respects. Results of the kind presented in (3) and (4) are used to study the asymptotic behaviour of the solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125028.png" /> of the renewal-type equation
+
\frac{H ( t) }{t }
 +
  = {
 +
\frac{1}{m}
 +
} ,
 +
$$
  
<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/r/r081/r081250/r08125029.png" /></td> </tr></table>
+
where  $  m = {\mathsf E} \xi _ {i} $.
 +
It was shown by D. Blackwell in 1948 (cf. [[#References|[1]]]), that if the distribution  $  \xi _ {i} $
 +
is not concentrated on some arithmetical lattice of the type  $  \{ 0, d, 2d , . . . \} $,
 +
$  d > 0 $,
 +
then for any  $  h > 0 $,
  
in which the free term <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125030.png" /> is some function other than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125031.png" /> which meets certain conditions.
+
$$ \tag{4 }
 +
\lim\limits _ {t \rightarrow \infty } \
 +
[ H ( t + h) - H ( t)]  =  {
 +
\frac{h}{m}
 +
} .
 +
$$
 +
 
 +
Numerous results are available which generalize and precisize equations (3) and (4) in several respects. Results of the kind presented in (3) and (4) are used to study the asymptotic behaviour of the solution  $  X( t) $
 +
of the renewal-type equation
 +
 
 +
$$
 +
X ( t)  = \
 +
K ( t) + \int\limits _ { 0 } ^ { t }  X ( t - u)  dF ( u),
 +
$$
 +
 
 +
in which the free term $  K( t) $
 +
is some function other than $  F( t) $
 +
which meets certain conditions.
  
 
The relation
 
The relation
  
<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/r/r081/r081250/r08125032.png" /></td> <td valign="top" style="width:5%;text-align:right;">(5)</td></tr></table>
+
$$ \tag{5 }
 +
{\mathsf P} \{ N _ {t} \geq  n \}  = {\mathsf P} \{ \zeta _ {n} \leq  t \}
 +
$$
  
follows from definition (1). Since limit theorems for sums <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125033.png" /> of independent terms have been thoroughly studied, relation (5) makes it possible to obtain limit theorems for the number of renewals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081250/r08125034.png" />.
+
follows from definition (1). Since limit theorems for sums $  \zeta _ {n} $
 +
of independent terms have been thoroughly studied, relation (5) makes it possible to obtain limit theorems for the number of renewals $  N _ {t} $.
  
 
There exists a large number of generalizations of the scheme just described. One such generalization, connected with semi-Markov processes (cf. [[Semi-Markov process|Semi-Markov process]]), yields the so-called Markov renewal process, in which the system has some number of states, and the lifetimes of the individual elements are random elements which depend on the states of the system before and after the moment of renewal.
 
There exists a large number of generalizations of the scheme just described. One such generalization, connected with semi-Markov processes (cf. [[Semi-Markov process|Semi-Markov process]]), yields the so-called Markov renewal process, in which the system has some number of states, and the lifetimes of the individual elements are random elements which depend on the states of the system before and after the moment of renewal.

Latest revision as of 08:10, 6 June 2020


A branch of probability theory describing a large range of problems connected with the rejection and renewal of the elements of some system. The principal concepts in renewal theory are those of a renewal process and renewal equation. A renewal process may be described using the classical scheme of sums of independent random variables in the following manner. Let $ \xi _ {1} , \xi _ {2} , . . . $ be a sequence of independent, non-negative, identically-distributed random variables having distribution function $ F( x) $. Let $ \zeta _ {0} = 0 $, $ \zeta _ {n} = \xi _ {1} + \dots + \xi _ {n} $, $ n \geq 1 $. The renewal process $ N _ {t} $ is defined as

$$ \tag{1 } N _ {t} = \max \{ {n } : {\zeta _ {n} \leq t } \} . $$

If the $ \xi _ {i} $ are interpreted as the lifetimes of some successively replaceable element, the random variable $ N _ {i} $ equals the number of replacements (or renewals) of these elements during time $ t $. The renewal function $ H( t) = {\mathsf E} N _ {t} $ plays an important part in studying $ N _ {t} $. This function satisfies the renewal equation

$$ \tag{2 } H ( t) = \ F ( t) + \int\limits _ { 0 } ^ { t } H ( t - u) dF ( u). $$

For $ F( t) = 1 - e ^ {- \rho t } $, $ t \geq 0 $, there arises an important special case of the renewal process — the Poisson process, in which

$$ {\mathsf P} \{ N ( t) = k \} = \frac{( \rho t) ^ {k} }{k! } e ^ {- \rho t } ,\ \ k = 0, 1 \dots $$

and $ H( t) = \rho t $.

The renewal process $ N _ {t} $ and the renewal equation (2) are very important in the study of various theoretical and applied problems in queueing theory, reliability theory, storage theory, the theory of branching processes (cf. Branching process), etc. A large number of results in renewal theory is connected with the study of the asymptotic properties of the renewal function $ H( t) $ as $ t \rightarrow \infty $. An elementary renewal theorem states that

$$ \tag{3 } \lim\limits _ {t \rightarrow \infty } \ \frac{H ( t) }{t } = { \frac{1}{m} } , $$

where $ m = {\mathsf E} \xi _ {i} $. It was shown by D. Blackwell in 1948 (cf. [1]), that if the distribution $ \xi _ {i} $ is not concentrated on some arithmetical lattice of the type $ \{ 0, d, 2d , . . . \} $, $ d > 0 $, then for any $ h > 0 $,

$$ \tag{4 } \lim\limits _ {t \rightarrow \infty } \ [ H ( t + h) - H ( t)] = { \frac{h}{m} } . $$

Numerous results are available which generalize and precisize equations (3) and (4) in several respects. Results of the kind presented in (3) and (4) are used to study the asymptotic behaviour of the solution $ X( t) $ of the renewal-type equation

$$ X ( t) = \ K ( t) + \int\limits _ { 0 } ^ { t } X ( t - u) dF ( u), $$

in which the free term $ K( t) $ is some function other than $ F( t) $ which meets certain conditions.

The relation

$$ \tag{5 } {\mathsf P} \{ N _ {t} \geq n \} = {\mathsf P} \{ \zeta _ {n} \leq t \} $$

follows from definition (1). Since limit theorems for sums $ \zeta _ {n} $ of independent terms have been thoroughly studied, relation (5) makes it possible to obtain limit theorems for the number of renewals $ N _ {t} $.

There exists a large number of generalizations of the scheme just described. One such generalization, connected with semi-Markov processes (cf. Semi-Markov process), yields the so-called Markov renewal process, in which the system has some number of states, and the lifetimes of the individual elements are random elements which depend on the states of the system before and after the moment of renewal.

References

[1] D.R. Cox, "Renewal theory" , Methuen (1962)
How to Cite This Entry:
Renewal theory. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Renewal_theory&oldid=48509
This article was adapted from an original article by B.A. Sevast'yanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article