This lecture note is still being edited: the text may contain typos, inaccuracies, and locally unpolished passages. If you find something, please let the author know (contact information on the course page).
1 General facts
Let \(\xi_1,\xi_2, \ldots\) be i.i.d. random variables, moreover nonnegative (\(\xi_1 \geq 0\) a.s.), let \(S_n := \xi_1 + \ldots + \xi_{n}\), let \(N_t\), \(t \geq 0\), be the renewal process constructed from them:
If \(\xi_i \sim \operatorname {Exp}(\lambda )\), then the process \(N_t\) is called the (stationary) Poisson process of intensity \(\lambda\).
ProblemProblem 1
Is it true that a renewal process \(N_{t}\) always has independent increments?
ProblemProblem 2
Let \(N_{t}\) be a renewal process, where \(\xi_i\) is a.s. finite, i.e., \(\mathbb {P}\left(\xi_i < +\infty \right) = 1\). Prove that \(N_t\) a.s. goes to \(+\infty\): \[
\mathbb {P}\left(\lim \limits _{t \rightarrow +\infty } N_{t}=+\infty \right) = 1.
\]
Theorem 1 The following conditions are equivalent:
\(N_{t}\) is a.s. finite for every \(t\): \(\mathbb {P}\left(N_t < +\infty \right) = 1\) for every \(t \in \mathbb {R}_+\);
\(\mathbb {E}\left[\xi_i\right] > 0\);
\(\mathbb {P}\left(\xi_i = 0\right) < 1\).
ProblemProblem 3
Let \(N^{(1)}=\left(N_{t}^{(1)}, t \geq 0\right), \ldots , N^{(k)}=\left(N_{t}^{(k)}, t \geq 0\right)\) be independent Poisson processes of intensity \(\lambda_i\) respectively. Prove that the process \(N_{t}=\sum_{i=1}^{k} N_{t}^{(i)}\) is also Poisson, and find its intensity.
Independence of the processes means that the sigma-algebras \(\mathcal{F}^{(1)}, \ldots , \mathcal{F}^{(k)}\) they generate are jointly independent: \[
\mathcal{F}^{(i)} := \sigma \left(\left\{ N^{(i)}_t \; : \; t \geq 0\right\} \right).
\]
HintHint
Without loss of generality, you may prove this for \(k=2\).
2 (*) Computing the mean function
Denote the mean function by
\[
m(t) := \mathbb {E}\left[N_t\right]
\]
In the theory of renewal processes this function is called the renewal function.
ProblemProblem 4
Let \(\xi_i\) have density \[
p(x) = \begin{cases} \frac{e^{-x}}{2} + e^{-2x} , & x \geq 0 \\ 0, & x < 0 \end{cases}
\] Find the renewal function \(m(t)\).
HintHint
Pass to Laplace transforms.
3 Limit theorems
We will state some limit theorems directly for the renewal-reward process, since the ordinary renewal process is merely a special case of this more general construction. Let us recall the definition: let
be independent and identically distributed pairs of random variables, with \(\xi_1 > 0\) a.s. Then the process
\[
Z_t := \sum _{k=1}^{N_t} \eta _k
\]
is called a renewal-reward process. Note that \(\xi_i\) and \(\eta_i\) need not be independent. This can be useful in practical problems, see problem Problem 5 about the entrepreneur Vasily and his machine.
The ordinary renewal process is obtained by taking \(\eta_1 \equiv 1\) a.s.
For the process \(Z_{t}\) the following strong law of large numbers holds.
Theorem 2 (Strong law of large numbers for the renewal-reward process) Suppose that \(0 < \mathbb {E}\left[\xi_i\right] \leq +\infty\), \(\mathbb {E}\left[\left|\eta_i\right|\right] < +\infty\). Under the definitions above we have \[
\frac{Z_{t}}{t} \xrightarrow [t \to +\infty ]{\text{a.s.}} \frac{\theta }{\mu },
\] where \(\theta := \mathbb {E}\left[\eta_i\right]\), \(\mu := \mathbb {E}\left[\xi_i\right]\)
Theorem 3 Under the conditions above we have \[
\frac{Z_{t}}{t} \xrightarrow [t \to +\infty ]{L^1} \frac{\theta }{\mu }
\]
Corollary 1 (The elementary renewal theorem) We have \[
\frac{\mathbb {E}\left[Z_t\right]}{t} \xrightarrow [t \to +\infty ]{} \frac{\theta }{\mu }.
\] In particular, for the ordinary renewal process we have \[
\frac{\mathbb {E}\left[N_t\right]}{t} \xrightarrow [t \to +\infty ]{} \frac{1}{\mathbb {E}\left[\xi _1\right]}
\]
We will state the CLT simply for the renewal process.
Theorem 4 (CLT for the renewal process) Let \(\left(N_{t}, t \geqslant 0\right)\) be a renewal process constructed from random times \(\left\{ \xi_{n}, n \in \mathbb {N}\right\}\). Denote \(\mu = \mathbb {E}\left[\xi_{i}\right]\), \(\sigma^{2}= \operatorname {Var}\left[\xi_{i}\right]\), where it is known that \(0 < \mu , \sigma^{2} < +\infty\). Then \[
\sqrt{t}\left(\frac{N_t}{t} - \frac{1}{\mu }\right) \quad \xrightarrow [t \to +\infty ]{d} \quad \mathscr {N}\left(0, \; \frac{\sigma ^2}{\mu ^3}\right)
\]
In the language of mathematical statistics, one can say that if \(0 < \mu , \sigma^2 < +\infty\), then the time-averaged renewal process \(\frac{N_t}{t}\) is a strongly consistent and asymptotically normal estimator of \(\frac{1}{\mu }\) with asymptotic variance \(\frac{\sigma^2}{\mu^3}\).
The strong law of large numbers in action: six simulated trajectories of \(N_t/t\) for a renewal process with inter-arrival times \(\xi_i\). Choose the inter-arrival distribution from the dropdown β exponential \(\operatorname{Exp}(1)\), uniform \(U[0,2]\) (both with mean \(1\)), or the heavy-tailed Pareto distribution with parameter \(\alpha=1\), for which \(\mathbb{E}\left[\xi_i\right]=+\infty\) β and click βNew trajectoriesβ to regenerate a bundle of six independent realizations. The dashed line marks the limit \(1/\mu\): for the first two distributions this is \(1\), while for the Pareto case it is \(0\), since the mean is infinite and the renewal rate over an infinite horizon tends to zero.
ProblemProblem 5
The entrepreneur Vasily owns a machine whose lifetime is random and uniformly distributed between zero and two years. Vasily can either let the machine run until it breaks down, in which case the replacement cost is \(260\) thousand rubles; or, while the machine is still in working order, he can perform scheduled maintenance for \(20\) thousand rubles, which resets the machineβs lifetime (effectively making the machine new again).
Vasily has decided to act as follows: he chooses a fixed time \(0 < t_0 < 2\), and if the machine (since its last renewal) survives to time \(t_0\), he performs scheduled preventive maintenance. If the machine does not survive to \(t_0\), then, correspondingly, Vasily must perform the expensive replacement.
Let \(Z_t\) be Vasilyβs cost process. Express \(Z_t\) as a renewal-reward process1;
Find the limit \(\frac{Z_t}{t}\) of Vasilyβs average costs;
Help Vasily: find the optimal replacement time \(t_0\), i.e., the value of \(t_0\) that would minimize the average costs (at least in the long run, i.e., in the limit).
ProblemProblem 6
Prove the SLLN for the renewal process (Theorem Theorem 2).
HintHint
Outline of the proof:
Enum-item(1)
In the ordinary SLLN the parameter is discrete, whereas here it is continuous. Find a way to pass from considering \(\frac{Z_{t}}{t}\) to \(\frac{Z_{S_i}}{S_i}\);
Enum-item(2)
Using the SLLN, find the a.s. limit of \(\frac{Z_{S_i}}{S_i}\) as \(i \to \infty\).
4 Time since the previous / until the next renewal
Let \(N_t\) be a renewal process constructed from intervals \(\xi_1, \xi_2, \ldots\). As before, denote
\[
S_n = \xi _1 + \ldots + \xi _n,
\]
so that \(S_n\) is the time of the \(n\)-th renewal of the process.
It is convenient to use the following real-world interpretation. Imagine a plant with a machine installed on it. This machine periodically breaks down and is replaced by a new one. Then \(\xi_i\) is the lifetime of the \(i\)-th machine, and \(S_n\) is the time of the \(n\)-th machine replacement.
Definition 1
\(S_{N_t}\) is the time of the last renewal up to time \(t\). In the machine interpretation, this is the time of the last machine replacement. Correspondingly, \(S_{N_t + 1}\) is the time of the next (future) renewal, i.e., the next machine replacement.
The random process
\[
C_t = t - S_{N_t}
\]
is the time elapsed since the last renewal. It is called the current lifetime (or age).
The random process
\[
E_t = S_{N_t + 1} - t
\]
is the time remaining until the next renewal. It is called the excess lifetime (or residual life).
is the total lifetime of the machine that is operating at time \(t\).
A diagram illustrating the definitions of the current lifetime \(C_t\), the residual lifetime \(E_t\), and the total lifetime \(D_t\): a step trajectory of a renewal process together with a fixed time \(t\) lying between consecutive renewals \(S_{N_t}\) and \(S_{N_t+1}\). Drag the slider \(t\) β the braces \(C_t\), \(E_t\), and \(D_t\) redraw automatically β and click βNew renewal epochsβ to regenerate the inter-arrival times \(\xi_i \sim \operatorname{Exp}(1)\).
ProblemProblem 8
Let \(N_t\) be a renewal process constructed from \(\xi_1, \xi_2, \ldots\), i.i.d. random variables distributed as \(\operatorname {Exp}(\lambda )\). Correspondingly, \(N_t\) is a (stationary) Poisson process of intensity \(\lambda\).
Find the distribution of \(E_t\). Compute, for example, the survival function \(\mathbb {P}\left(E_t > v\right)\). Find the mean function (i.e., the expectation) of \(E_t\).
Find the distribution of \(C_t\) (the survival function \(\mathbb {P}\left(C_t > u\right)\), for example). Find the mean function of \(C_t\).
Compute the joint survival function \(\mathbb {P}\left(E_{t}>v, C_{t}>u\right)\).
Prove that \(E_{t}\) and \(C_{t}\) are independent (at a fixed point \(t\)) for the (stationary) Poisson process.
Let \(N_t\) be an (elementary) Poisson process of intensity \(\lambda\), as in the previous problem. Recall that \(D_t\) is the length of the waiting interval at time \(t\), and \(\xi_1\) is the length of the first interval.
Show that \(S_{D_t}(x) = \mathbb {P}\left(D_t > x\right) = \left(1 + \lambda \min (t,x)\right)\cdot e^{-\lambda x}\), \(x \geq 0\).
Which is larger: the survival function \(S_{D_t}\) for the interval at an arbitrary time \(t\), or the survival function \(S_{\xi_1}\) for the first interval?
Find \(\mathbb {E}\left[D_t\right]\), compare with \(\mathbb {E}\left[\xi_1\right]\).
HintHint
Use the previous problem: \(D_t = C_t + E_t\), the summands are independent, and the distributions are known.
The inspection paradox: the survival function of \(D_t\), the length of the interval covering the observation time \(t\), lies strictly above the survival function of a typical interval \(\xi_1 \sim \operatorname{Exp}(\lambda)\). Drag the sliders \(\lambda\) and \(t\) to see both curves redraw (defaults \(\lambda=1\), \(t=2\), matching the problem above), and click βSimulateβ to run \(N=20000\) independent trials: each trial builds a renewal process with \(\operatorname{Exp}(\lambda)\) inter-arrival times and records the length of the interval covering time \(t\). The histogram of these lengths matches the analytical density of \(D_t\) (obtained by differentiating \(S_{D_t}\)) rather than the density of a typical interval \(\operatorname{Exp}(\lambda)\) β this is exactly the paradox: the interval an observer βlands inβ is, on average, longer than a typical one.
ProblemProblem 10
Let \(N=\left(N_{t}, t \geqslant 0\right)\) be a Poisson process of intensity \(\lambda\). Find the expected number of its jumps on the interval \([0, T]\) such that
there are no other jumps in their right \(a\)-neighborhood (this neighborhood may extend beyond the interval),
there are no other jumps in their left \(a\)-neighborhood.