%%% Title of object:	Renewal Processes
%%% Canonical Name:	RENEWALPROCESSES
%%% Type:	Definition
%%% Created on:	2010-08-27 07:24:58
%%% Modified on:	2010-09-04 01:49:54
%%% Creator:	KMitov
%%% Modifier:	jkimmel
%%% Author:	jkimmel
%%% Author:	KMitov
%%% 
%%% Classification:	msc:60K05
%%% Preamble:

\documentclass[10pt]{article}
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.

% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}

% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}

% there are many more packages, add them here as you need them

% define commands here
%%% Content:

\begin{document}

\begin{center}

{\Large \bf Renewal Processes}\\[4mm]


{\large \it Kosto V. Mitov}

Professor, Faculty of Aviation - National Military University, D. Mitropolia, Pleven, Bulgaria \\[2mm]

{\large \it Michael A. Zazanis}

Professor, Department of Statistics

Athens University of Economics and Business, Athens, Greece



\end{center}


Let $\{X_n;n\in \mathbb{N}\}$ be a sequence of independent, identically distributed random
variables with values in $\mathbb{R}^+$ and distribution function $F$. The process $\{S_n;n \in \mathbb{N}_0\}$
defined by means of $S_0:=0$, $S_n:=S_{n-1}+X_n$, $n=1,2,\ldots$ is called an {\em ordinary renewal process}.
The non--negative random variables $X_n$ are called increments or, in many applications, inter--event times.
In connection with the sequence of random points in time, $\{S_n\}$, one can define the {\em counting process}
$N_t = \sum_{n=0}^\infty 1(S_n \leq t)$, $t \in \mathbb{R}^+$, where $1(A)$ designates the {\em indicator function} of
the event $A$ (which is 1 if $A$ occurs and 0 otherwise).
The {\em renewal function} associated with a renewal process is the increasing, right--continuous function
$U(t) :=EN_t= \sum_{n=0}^\infty F^{*n}(t)$ where $F^{*n}(t)$ denotes the $n$--fold {\em convolution} of the distribution
function $F$ with itself (hence $F^{*n}(t) =P(S_n \leq t)$).

Renewal processes are intimately related to the theory of the so--called {\em renewal equation} which is a linear
integral equation of the form
\begin{equation} \label{renewal_equation}
Z(x) = z(x) + \int_0^x Z(x-y) F(dy)
\end{equation}
where $z: \mathbb{R}^+ \rightarrow \mathbb{R}$ is a Borel function, bounded on finite intervals,
and $F$ a probability distribution on $\mathbb{R}^+$. $F$ and $z$ are assumed to be given and the object
is to determine the (unique) solution $Z$ which is bounded on finite intervals, and study its asymptotic
behavior as $x\rightarrow \infty$. Its solution is given, in terms of the renewal function by the convolution
$Z(x) = \int_0^xz(x-y) U(dy)$.


Renewal processes are important as special cases of random point processes. In this respect the Poisson
process on the real line is the simplest and most important renewal process. They occur naturally
in the theory of replacement of industrial equipment, the theory of queues, in branching processes, and in many other
applications. In the framework of perpetual replacement of a single item, $X_n$ is the life of the $n$th such item which,
as soon as it fails, is replaced by a new one with independent duration distributed according to $F$. Then $N_t$
is the number of items used in the time interval $[0,t]$ and $S_{N_t}$ is the time of the last replacement before $t$.
We define three additional processes $\{A_t;t\geq 0\}$, $\{B_t;t \geq 0\}$, and $\{C_t;t\geq 0\}$ as follows:
$A_t := t - S_{N_t-1}$ is the {\em age}, $B_t:=S_{N_t}-t$ is the {\em remaining life}, and $C_t :=A_t+B_t =X_{N_t}$
is the total life duration of the item currently in use. (The age and remaining life are also known as the backward and
forward recurrence times.) The statistics of these processes can be described
by means of appropriate renewal equations. For instance, if $W_x(t):=P(A_t \leq x)$ then conditioning on $S_1$ (using
the so--called ``renewal argument'') we obtain
\begin{equation} \label{age}
W_x(t) = (1-F(t))1(t \leq x) + \int_0^t W_{x}(t-s)dF(s).
\end{equation}

If we allow the first increment to have a different distribution from all the others, i.e.\ if we set $S_0 = X_0$ and
$S_n =S_{n-1}+X_n$, $n=1,2,\ldots$ where $X_0$ is independent of the $\{X_n\}$ and, unlike them, has distribution
$F_0$, different from $F$, we obtain a {\em delayed renewal process}. This type of process is important because it provides
additional flexibility in accommodating different initial conditions. Of course, its limiting properties are not
affected by this modification. Of particular importance, assuming the mean $m$ to be finite, is the choice $F_0=F_I$, given by
\begin{equation} \label{integrated_tail}
F_I(x):= \frac{1}{m} \int_0^x (1-F(y))dy.
\end{equation}
With this choice, $\{S_n\}$ becomes a {\em stationary point process}. $F_I$ is called the {\em integrated tail distribution}
associated with the distribution $F$.

Of fundamental importance are the limit theorems related to renewal processes. If $\displaystyle m:=\int_0^\infty x dF(x)$ denotes
the mean of the increments, then the {\em Elementary Renewal Theorem} states that $\displaystyle \lim_{t \rightarrow \infty}
t^{-1} U(t) = m^{-1}$. (The result holds also in the case $m=\infty$ provided that we interpret $m^{-1}$ as 0.) A refinement
is possible if the increments have finite second moment, in which case
$\displaystyle \lim_{t \rightarrow \infty} \left( U(t) - t/m \right) = EX_1^2/(2m^2)$. An analogous bound, due to Lorden (1970),
also holds for all $t \geq 0$: $\displaystyle U(t) \leq t/m + EX_1^2/m^2$. When the second moment exists we also have a Central
Limit Theorem for the number of events up to time $t$: As $t \rightarrow \infty$,
$\displaystyle \frac{N_t - t/m}{\sigma \sqrt{t/m^3}} \stackrel{d}{\rightarrow} Z$
where $Z$ is a standard Normal random variable and $\sigma^2= Var(X_1)$.

Much deeper is {\em Blackwell's Theorem} which states that,
if $F$ in non--lattice and the mean $m$ is finite then
\begin{equation} \label{Blackwell}
\lim_{t \rightarrow \infty} \left( U(t+h) - U(t) \right) = h/m \hspace{0.3in} \mbox{ for all $h >0$}.
\end{equation}
(A distribution $F$ on $\mathbb{R}^+$ is {\em lattice} with lattice size $\delta$ if there exists $\delta>0$ such
that the support of $F$ is a subset of $\{n\delta; n=0,1,2,\ldots\}$ and $\delta$ is the largest such number.) If
$F$ is lattice ($\delta$) then (\ref{Blackwell}) still holds, provided that $h$ is an integer multiple of $\delta$.
Also, if $m=\infty$ the theorem still holds with $m^{-1}=0$.
Blackwell's original proof (1948) of (\ref{Blackwell}) depended on harmonic analysis techniques.
In the 1970's with the widespread use of coupling techniques simpler probabilistic proofs of the renewal theorem became
available. (See \cite{Lindvall} for a complete account.) An integral version of Blackwell's theorem, the
{\em Key Renewal Theorem}, states that, if $z$ is directly Riemann integrable then the
limit $\displaystyle \lim_{x \rightarrow \infty} \int_0^x z(x-y)dU(y)$ exists and equals $\displaystyle m^{-1} \int_0^\infty z(x)dx$. This then gives
the limiting behavior of any function which satisfies a renewal equation (\ref{renewal_equation}). (Direct Riemann integrability
is a direct extension of the Riemann integral from bounded intervals to unbounded ones: Fix $h>0$ and let
$\overline{\gamma}_n(h)=\sup_{nh\leq x< (n+1)h}z(x)$, $\underline{\gamma}_n(h)=\inf_{nh\leq x< (n+1)h}z(x)$. Set
$\overline{I}(h):=\sum_{n=0}^\infty h \overline{\gamma}_n(h)$ and $\underline{I}(h):=\sum_{n=0}^\infty h \underline{\gamma}_n(h)$.
Clearly, if $h_1>h_2>0$ then $\underline{I}(h_1) \leq \underline{I}(h_2) \leq \overline{I}(h_2) \leq \overline{I}(h_1)$,
though these quantities may not necessarily be finite. If $\lim_{h\rightarrow 0} \underline{I}(h)$ and
$\lim_{h\rightarrow 0}\overline{I}(h)$ exist and are equal then $z$ is directly Riemann integrable. It should be noted that
the direct Riemann integral is more restrictive than either the improper Riemann integral or the Lebesgue integral.)

The discrete version of the renewal theorem is simpler but not elementary. Suppose we are given a probability distribution
$\{f_n;n=1,2,\ldots\}$ which is {\em non--arithmetic}, i.e. $\text{g.c.d.}\{n:f_n>0\}=1$ and has mean $m= \sum_{n=1}^\infty n f_n$,
and define the renewal sequence $\{u_n;n=0,1,2,\ldots\}$ via $u_0=1$, $u_n =f_n+f_{n-1}u_1+\cdots+f_1 u_{n-1}$. Then
$\lim_{n\rightarrow \infty}u_n = m^{-1}$ (interpreted as 0 when $m=\infty$). This is the celebrated Erd\"os--Feller--Pollard (1948)
renewal theorem (see \cite{Feller}, vol.\ 1, ch.\ 13) which marks the beginning of modern renewal theory and played a
central r\^ole in the treatment of Markov chains with countable state space. Interesting behavior arises if the non--arithmetic
distribution function $\{f_n\}$ has infinite mean:
Suppose that $\sum_{k=n+1}^\infty f_k = L(n)n^{-\alpha}$ where $0<\alpha<1$ and $L(n)$ is a {\em slowly varying} function. (A real
function $L$ is said to be slowly varying if it is positive, measurable, and for every $\lambda>0$, $L(\lambda x)/L(x) \rightarrow 1$
as $x \rightarrow \infty$.) Then (Garsia and Lamperti, 1962) $\liminf_{n\rightarrow \infty} n^{1-\alpha}L(n) u_n = \pi^{-1}\sin \pi \alpha$.
If $1/2 < \alpha <1$, this can be sharpened to $\lim_{n\rightarrow \infty} n^{1-\alpha}L(n)u_n =\pi^{-1}\sin \pi \alpha$.
Analogous results in continuous time are also proved. Suppose that
$F(.)$ is continuous, $F(0+)=0,$ $F(\infty)=1,$ $m=\infty,$ and
\begin{eqnarray}
&&\label{regvar}\tag{5} \displaystyle 1-F(t) \sim
\frac{t^{-\alpha}L(t)}{\Gamma(1-\alpha)} \ \Leftrightarrow \ m(t):=\int_0^t (1-F(u))du \sim
\frac{t^{1-\alpha}L(t)}{\Gamma(2-\alpha)}, \ t \to
\infty,\end{eqnarray} where $\alpha \in [0,1)$ and $L(\cdot)$ is a
slowly varying function at infinity. Under these conditions the
growth rate of $U(t)$ is given by (see e.g.\ \cite{bgt}, Ch.\ 8),
\begin{eqnarray*}
U(t) \sim C_\alpha t/m(t), \ \mbox{ as } \ t \to \infty, \mbox{ where } C_\alpha=[\Gamma(\alpha+1)\Gamma(2-\alpha)]^{-1}.
\end{eqnarray*}
Erickson (1970) proved a version of Blackwell's theorem in the infinite mean cycle case. It
states that if in (\ref{regvar}), $\alpha \in (\frac{1}{2}, 1],$ then for any fixed $h>0$
\begin{eqnarray*}
&&
\lim_{t \to \infty}m(t)[U(t)-U(t-h)] = C_\alpha h.
\end{eqnarray*}
If $\alpha \in (0,\frac{1}{2}],$ then $\lim$ has to be replaced by $\liminf.$
Several versions of the Key Renewal Theorem in the infinite mean cycle case are also proved in Teugels (1968), Erickson (1970),
and Anderson and Athreya (1987).


Using the Key Renewal Theorem one can obtain the asymptotic behavior of the age and the current and residual life. If $Y$ is a
random variable with distribution $\displaystyle P(Y \leq y) = \frac{1}{m}\int_0^y x dF(x)$ and $V$ is uniform in $[0,1]$
and independent of $Y$, then
$$(A_t,B_t,C_t) \stackrel{d}{\rightarrow} (VY,(1-V)Y,Y) \mbox{ as } t \rightarrow \infty. $$
In particular the limiting marginal distribution of the age (which is the same as that of the residual life) is
$$\lim_{t\rightarrow \infty} P(A_t \leq x) = F_I(x),$$
the integrated tail distribution given in (\ref{integrated_tail}).
The limiting behavior of these processes gives rise to the so called ``renewal paradox''. For instance, the limiting distribution of the
item currently in use is
$$\lim_{t\rightarrow \infty} P(C_t \leq x) = \frac{1}{m} \int_0^x ydF(y)$$
with corresponding mean, provided that the second moment of $F$
exists, given by $m+ \sigma^2/m$. Hence if we inspect such a process a long time after it has started
operating (and is therefore in equilibrium) the part we are going to see will have longer life duration than average. Of course this is
simply an instance of {\em length--biased sampling} and its effects are more pronounced when the variability of the distribution $F$
around its mean is large.

In the infinite mean cycle case the life time processes $A_t$ and $B_t$ have a linear growth to infinity, i.e.\ the
normalized processes $A_t/t$ and $B_t/t$ have non-degenerate
limit laws, jointly or separately. This result is usually called the Dynkin-Lamperti theorem
(Dynkin, 1955, Lamperti, 1962). (See also \cite{bgt}, Ch.\ 8). The theorem
states that the condition (\ref{regvar}) with $\alpha \in (0,1)$ is necessary and
sufficient for the existence of non-degenerate limit laws for $A_t/t$, $B_t/t$,
\begin{eqnarray*}
&&
\displaystyle
\lim_{t \to \infty}P\left(A_t/t \le x\right) = \pi^{-1}\sin \pi \alpha \int_0^xu^{-\alpha}(1-u)^{\alpha-1},\ \ 0 <x< 1,\\
&&
\displaystyle
\lim_{t \to \infty}P\left(B_t/t \le x\right)=\pi^{-1} \sin \pi \alpha \int_0^x u^{-\alpha}(1+u)^{-1}du, \ \ \ x > 0.
\end{eqnarray*}
An important and immediate generalization of the renewal equation (\ref{renewal_equation}) is to allow $F$ to be a general positive
finite measure on $\mathbb{R}^+$. Setting $\Vert F \Vert:=F(\mathbb{R}^+)$ one distinguishes the {\em excessive} case where
$\Vert F\Vert > 1$, the {\em defective} case where $\Vert F \Vert < 1$, and the {\em proper} case we have already discussed,
where $\Vert F \Vert =1$. In the excessive case one can always find a (unique) $\beta >0$ such that
$\displaystyle \int_0^\infty e^{-\beta x}dF(x) =1$. One can define then a probability distribution function $F^{\#}$ via the relationship
$\displaystyle dF^{\#}(x) = e^{-\beta x} dF(x)$, $x \geq 0$. Multiplying both sides of (\ref{renewal_equation}) by $e^{-\beta x}$ and
setting $\displaystyle z^\#(x)= e^{-\beta x}z(x)$, $Z^\#(x)= e^{-\beta x}Z(x)$, the proper renewal equation
$\displaystyle Z^{\#}(x) = z^{\#}(x)+ \int_0^x z^{\#}(x-y) dF^\#(y)$ is obtained. The Key Renewal Theorem then yields
$$\lim_{x\rightarrow \infty}e^{-\beta x}Z(x) = \frac{1}{m^\#}\int_0^\infty z^\#(y)dy,$$
which establishes that, asymptotically, $Z$ grows exponentially with rate $\beta$. We should point out that
the defective case is not entirely similar. While
formally one again tries to identify $\beta >0$ so that $\displaystyle \int_0^\infty e^{\beta x} dF(x) =1$, this may or may not be possible
according to whether the distribution function $\displaystyle \frac{1}{\Vert F\Vert}F(x)$ is {\em light--tailed} or {\em heavy--tailed}. In
the former case one proceeds just as in the excessive case. (For more details see \cite{Feller}, vol.\ 2 ch.\ 11).
This type of analysis is characteristic of the applications of renewal theory to areas such as population dynamics, the
theory of collective insurance risk, and to the economic theory or replacement and depreciation (Jorgenson (1974),
Feldstein and Rothchild (1974)).


Alternating renewal processes arise in a natural way in many situations, like queueing systems and reliability of
industrial equipment, where working(busy) periods ($X$) interchange with idle periods ($T$).
Consider a sequence of random vectors with non-negative coordinates $(T_i,X_i), i=1,2,\ldots$.
It defines an {\it alternating renewal sequence} $(S_n, $ $S_{n+1}')$ as follows
$S_0=0, \ S_n'=S_{n-1}+T_n, \ \ S_{n}=S_n'+X_n=S_{n-1}+(T_n+X_n), \ \ n=1,2,\ldots.$
An interpretation in terms of the reliability theory is the following. There are two types of renewal events:
$S_n$ is the moment when the installation of a new element begins (The installation takes time $T_n$);
$S'_{n+1}$ is the moment when the installation ends and the new element starts working.
(The working period has length $X_n$). The renewal process $N(t)=\sup\{n: S_n \le t\}$ counts
the pairs of renewal events in the interval $[0,t].$ The processes $\sigma_t=\max\{0,t-S'_{N(t)+1}\}$ -- {\it spent working time}
and $\tau_t=\min\{S_{N(t)+1}-t,X_{N(t)+1}\}$ -- {\it residual working time} generalize the lifetime processes $A_t$ and $B_t$.
Their properties are derived in Mitov and Yanev (2001) in the infinite mean cycle case.


The central place that renewal theory holds in the analysis of stochastic systems is due to the concept of {\em regeneration}.
Let $\{X_t; t \in \mathbb{R}^+\}$ be a process with values in $\cal S$ (e.g.\ a Euclidean space $\mathbb{R}^d$) and sample paths
that are c\`adl\`ag (right--continuous with left--hand limits) a.s.. Such a process is called {\em regenerative} with respect to
a (possibly delayed) renewal process $\{S_n\}$, defined on the same probability space, if, for each $n \in \mathbb{N}$
the {\em post $S_n$ process} $(\{X_{S_n+t}\}_{t \geq 0}, \{S_{n+k}-S_n\}_{k\in \mathbb{N}})$ is independent of
$\{S_0, S_1, \ldots, S_n\}$ and its distribution does not depend on $n$, i.e.\
$(\{X_{S_n+t} \}_{t \geq 0},\{S_{n+k}-S_n\}_{k\in \mathbb{N}}) \stackrel{d}{=} (\{X_{S_0+t}\}_{t \geq 0}, \{S_k-S_0\}_{k\in \mathbb{N}})$
for all $n$. The existence of an embedded, non--lattice renewal process with respect to which the process $\{X_t\}$ is regenerative,
together with the finiteness of the mean $m:=E[S_1-S_0]$ is enough
to guarantee the existence of a ``stationary version'', say $\{\tilde{X}_t\}$, to which $\{X_t\}$ converges as $t$ goes to
infinity. The statistics of $\{\tilde{X}_t\}$ can be determined by analyzing the behavior of $\{X_t\}$ over any {\em regenerative
cycle}, i.e.\ a random time interval of the form $[S_n,S_{n+1})$. If $k \in \mathbb{N}$, $t_i \in \mathbb{R}^+$, $i=1,2,\ldots, k$, and
$f:{\cal S}^k \rightarrow \mathbb{R}$ is any bounded, continuous function then
\begin{equation*} \label{regenerative}\nonumber
Ef(\tilde{X}_{t_1},\ldots,\tilde{X}_{t_k}) = \frac{1}{m} E \int_{S_0}^{S_1} f(X_{t_1+t},\ldots,X_{t_k+t}) dt.
\end{equation*}


Nowadays, our view of whole areas of probability, including parts of the theory of Markov processes is influenced
by renewal theoretic tools and related concepts of regeneration. The analysis of many stochastic models is greatly
facilitated if one identifies certain embedded points in time that occur according to a renewal process and with
respect to which the process is regenerative. The fact that these regeneration cycles are independent, identically
distributed, also facilitates the statistical analysis of the simulation output of regenerative systems.

A detailed representation of the renewal theory and its applications could be found, for instance,
in the following books \cite{Asmussen}, \cite{bgt}, \cite{Feller}, and \cite{Resnick}.

Reprinted with permission from Lovric, Miodrag (2011), International
Encyclopedia of Statistical Science. Heidelberg: Springer Science
+Business Media, LLC.

\begin{thebibliography}{10} \vspace{-0.1in}
\bibitem{Asmussen} Asmussen, S. (2003). \emph{Applied Probability and Queues}. Second Edition. Springer Verlag. \vspace{-0.1in}
\bibitem{andersonathreya} Anderson, K. K.; Athreya, K. B. (1987). A renewal theorem in the infinite mean case, \emph{The Annals of Probability}, {\bf 15}, 388-393.\vspace{-0.1in}
\bibitem{bgt} Bingham, N. H.; Goldie, C. M.; Teugels, J. L. (1987). \emph{Regular Variation}, Cambridge University Press: Cambridge. \vspace{-0.1in}
\bibitem{dynkin} Dynkin, E. B. (1955). Limit theorems for sums of independent random quantities, \emph{Izves. Akad. Nauk U.S.S.R.}, {\bf 19}, 247-266.\vspace{-0.1in}
\bibitem{erickson} Erickson, K. B. (1970). Strong renewal theorems with infinite mean, \emph{Transactions of the American Mathematical Society}, {\bf 151}, 263-291.\vspace{-0.1in}
\bibitem{feldrotsh} Feldshtein, M.; Rotschild, M. (1974). Toward An Economic Theory of Replacement Investment, \emph{Econometrica}, {\bf 42(3)}, 393-423.\vspace{-0.1in}
\bibitem{Feller} Feller, W. (1968, 1971). \emph{An Introduction to Probability Theory and its Applications}, Vol I and II, John Wiley. \vspace{-0.1in}
\bibitem{gasialamperti} Garsia, A.; Lamperti, J. (1962) A discrete renewal theorem with infinite mean. \emph{Comment. Math. Helv.}, {\bf 37}, 221-234.\vspace{-0.1in}
\bibitem{Jorgenson} Jorgenson, D. W. (1974). Investment and Production: \emph{A Review. In Frontiers of Quantitative Economics, Vol 2, eds. M. Intriligator and D. Kendrick}, Amsterdam: North-Holland, 341-366.\vspace{-0.1in}
\bibitem{lamperti} Lamperti, J. (1962). An invariance principle in renewal theory, \emph{Annals of Mathematical Statistics}, {\bf 33}, 685-696.\vspace{-0.1in}
\bibitem{Lindvall} Lindvall, T. (1992). \emph{Lectures on the Coupling Method}, John Wiley. \vspace{-0.1in}
\bibitem{Lorden} Lorden, G. (1970). On the excess over the boundary, \emph{Ann. Math. Statist.},{ \bf41}, 520--527. \vspace{-0.1in}
\bibitem{mityan} Mitov, K. V.; Yanev, N. M. (2001). Limit theorems for alternating renewal processes in the infinite mean case, \emph{Advances in Applied Probability}, {\bf 33}, 896--911.\vspace{-0.1in}
\bibitem{Resnick} Resnick, S. (1992). \emph{Adventures in Stochastic Processes}. Birkh\"auser.

\end{thebibliography}
\end{document}
