```{r setup, include=FALSE}
knitr::opts_chunk$set(echo = TRUE)
```
# More advanced renewal theorems
We will discuss some more advanced renewal theorems that will be useful for applications later. We call the function $m(t):= \mathbb{E} N(t)$ the **renewal function**.
**Theorem (Elementary renewal theorem):** The renewal function satisfies $m(t)/ t \to (\mu)^{-1}$, where $\mu$ is the mean inter-arrival time.
The elemenary renewal theorem can be thought of as a version of the law of large numbers. We already know that if $N$ is the renewal process, then $N(t)/t \to (\mu)^{-1}$; hence the proof of the theorem is the justification of the following interchange of limits:
$$ \lim_{t \to \infty} \frac{ \mathbb{E} N(t)}{t} = \mathbb{E} \Big( \lim_{t \to \infty} \frac{ N(t)}{t} \Big).$$
We say that the law of a real-valued random variable is of **lattice-type** if for some $a >0$ the random variables takes values in the set $$a\mathbb{Z} = \{az: z \in \mathbb{Z}\}$$ with probability one; the largest such possible $a$ is called the **span** of the lattice. Note that continuous random variables are of non-lattice type.
**Theorem (Blackwell's renewal theorem):** A renewal process with inter-arrival times that are of non-lattice type has a renewal function $m$ that satisfies
$$\frac{m(t+h) - m(t)}{h} \to \frac{1}{\mu},$$
as $t \to \infty$, for all $h >0$. Furthermore, in the case of a lattice-type inter-arrival time with span $a$, the limit holds if we choose $h$ to be integer multiples of $a$.
The lattice type cases were previously proved by [others](https://projecteuclid.org/download/pdf_1/euclid.pjm/1103051394), and [Blackwell](https://projecteuclid.org/download/imagefirstpage_1/euclid.dmj/1077474668) proved the more difficult non-lattice case. We will see in our coupling sketch proof that the non-lattice case is indeed more tricky.
A consequence of this theorem is the following version which is often used in applications. Recall that it is possible to define Stieltjes' extension of the Riemann integral where we have
$$ \int_a ^b f(x) d\phi(x) = \int_a^b f(x) \phi'(x) dx$$
if $\phi$ is continuously differentiable; the key is that we can make sense of the left-hand side even if $\phi$ is just monotone and right continuous. Going back to the definition of Riemann sums, we replace expressions of the sort:
$$ f(x_i^{*})(x_{i+1} - x_i)$$ with
$$ f(x_i^{*})(\phi(x_{i+1}) - \phi(x_i)).$$
Thus the length of an interval $(x_i, x_{i+1}]$ is weighted by the function $\phi$.
Much of the theory is similar, but it also allows us to have a more unified treatment of sums and integrals. We need to be a bit careful about endpoints in the integration as jumps are possible. We will take the convention that an integrals are taken over intervals of the form. $(a, b]$. Working from the definitions it is possible to show that if $\phi$ is step function with jumps at points $a < s_1< \cdots t$, since are no arrivals, and for $x \leq t$, we know that $N(t)$ is at least one, arriving at time $x$, so that the distribution of $N(t)$ is given by $1$ + the number of arrivals that have come by time $t-x$, which depends on $X_2, X_3, \ldots$ and thus as the same distribution as $N(t-x)$ so that
$$ \phi(x) = 1 + \mathbb{E}(N(t-x)).$$
Hence
$$
\begin{eqnarray*}
m(t) &=& \mathbb{E} (N(t)) \\
&=& \mathbb{E} \phi(X_1) \\
&=& \int_0 ^{\infty} \phi(x) dF(x) \\
&=& \int_0^t \big[ 1+ \mathbb{E}( N(t-x))\big]dF(x) \\
&=& F(t) + \int_0^t m(t-x)dF(x),
\end{eqnarray*}
$$
as desired.
It will be nice to adopt some notation, and express the renewal equation as
$$ m = F + m*F;$$
here we set (whenever they can be well-defined)
$$ (\phi * \psi)(t) = \int_0 ^t \phi(t-u) d \psi(u),$$
where $\phi(t) = \psi(t) = 0$ if $t <0$. A version of integration by parts (think of $d\psi(u) = \psi'(u)du$) gives that
$$ \phi* \psi = \psi * \phi.$$
The star-operation behaves like a convolution and is associative so that
$$ (\phi * \phi) * \zeta = \phi * (\phi * \zeta).$$
# Excessive life and stationary increments
Let $N$ be a renewal process, with i.i.d.\ inter-arrival times given by $X_1, X_2, \ldots$. Let $T_1, T_2, \ldots$ be the arrival times. We start with the question of when the distribution $N(t+s) - N(t)$ only depends on $s$, like in a Poisson process. In general this will not be true, just by virtue of how we defined renewal processes: the first arrival is special, $X_1$ is the time from the origin (where there is no arrival) to the first arrival, whereas $X_2$ is the time between the first arrival the second. Another way to put it, if we pick a time $t$, and wait until the next arrival after $t$, this quantity is known as the **excess lifetime** given by
$$E(t) = T_{N(t) +1} -t;$$
we have no reason to believe that it should be distributed as $X_1$. It turns out that if we are allowed to have a different distribution for $X_1$, while maintaining the same i.i.d.\ distribution for $X_2, X_3, \ldots$, we can define a **modified** or **delayed** renewal process $N^d$ that has stationary increments, and it is much easier to verify that this process satisfies Blackwell's renewal theorem; in particular, we will see that if $m^d(t) = \mathbb{E} N^d(t)$, then
$$ m^d(t+h) - m^d(t) = \frac{h}{\mu}.$$
It turns out that limiting distribution of $E(t)$ is what we should choose for $X_1$ if we want stationary increments, since as $t \to \infty$, we can imagine that the renewal process would have forgotten its non-stationary choice of $X_1$. It is possible to show (using the key renewal theorem and some more renewal equations) that
$$\lim_{t \to \infty} \mathbb{P}(E(t) \leq y) = \frac{1}{\mu} \int_0 ^y [1-F(x)]dx=: F^d(y),$$
where $F$ is the cdf of $X_1$ which is non-lattice type; see [Exercise 3](https://tsoo-math.github.io/ucl/QHW6.1.html). However, once we know the answer, we can simply use $F^d$ as the modifed distribution for $X_1$ and check that it does lead to stationary increments. There are some technical calculations involved.
Let us simulate $E(t)$ for large $t$ in the case where the inter-arrival times are uniformly distributed on $[0,1]$ and we see that it agrees with the stated theory.
```{r}
excess <- function(t){
arr = runif(1)
inter = arr
while(arr[length(arr)] 0$; it is easy to verify this fact for all positive rationals, and standard analysis arguments allow us to extend this result to all positive reals.
A similar renewal theorem holds for $m^d$, from which we know that $c = \mu^{-1}$. In addition, we subsitute $m^d$ into one of our renewal equations to obtain that
$$ cy = F^d(y) + c\int_0 ^y F(y-x)dx= F^d(y) + c\int_0^y F(x)dx$$
Thus
$$ F^d(y) = c\int_0 ^y [1- F(x)]dx.$$
Taking the limit at $y \to \infty$, we have
$$1= c \int_0 ^{\infty} [1-F(x)]dx = c\mu,$$
as desired.
# Sketch proof of Blackwell's renewal theorem
* Consider independent renewal processes $N$ and $N^d$, where $N^d$ is the stationary delayed version.
* Thus $N$ is constructed via $X_1, X_2, \ldots$ inter-arrival times, whereas, $N^d$ is constructed as $X_1', X_2', \ldots, X_3, \ldots$ inter-arrival times, and the sequences $X$ and $X'$ are independent.
* Let $\epsilon >0$.
* Various arguments can be used to deduce that with probability $1$, there exists some $i,j$ such that
$$|T_i - T^d_j| < \epsilon$$
* Redefine $N$ and $N'$ so that, from $i$ and $j$ onwards, we use the same (new) i.i.d.\ random variables $Z_1, Z_2, \ldots$ that have the same inter-arrival distribution as $X_1$. Specifically, $T_{i+1} = T_i + Z_1$ and $T^d_{j+1} = T^d_{j} + Z_1$.
* Now the redefined $N$ and $N^d$ will forever be $\epsilon$ close.
* Hence the limiting behaviour of $N$ is the same as $N^d$.
* The Blackwell renewal theorem is obvious for $N^d$, since $m^d(t)= \mu^{-1} t$.
* We remark that the analogous Blackwell renewal theorem also holds for *any* delayed renewal process.
# Some more remarks on renewal equations
Recall we started with $m^d = F^d + m* F^d$ and obtained $m^d = F^d + m^d * F$, the key being that $m^d * F= m * F^d$.
Similar considerations give the following. See [Exercise 2](https://tsoo-math.github.io/ucl/QHW6.1.html).
**Theorem (Uniqueness of solutions):**
Let $m$ be a renewal function and $F$ be cumulative distribution function for the inter-arrival times. Let
$$ \phi = H + H*m.$$
Then $\phi$ satisfies the renewal-type equation
$$ \phi = H + \phi*F;$$
moreover $\phi$ is the unique solution to the renewal-type equation, provided that $H$ is bounded on finite intervals, which also implies that $\phi$ is bounded on finite intervals.
If we are interested in $\lim_{t \to \infty} \phi(t)$, we can use the form $\phi = H + H*m$ and possibly apply the key renewal theorem:
$$\lim_{t \to \infty} \phi(t) = \lim_{t \to \infty} H(t) + \frac{1}{\mu} \int_0 ^{\infty} H(x)dx.$$
# Summary
* We stated Blackwell's renewal theorem and the key renewal theorem.
* We discussed the connection between the limiting distribution for the excess lifetime and how this distribution can be chosen to be the delayed distribution which results in stationary increments for the associated delayed process.
* We discussed the inspection paradox and its explanation via size-biasing
* We sketched a coupling arguement for Blackwell's renewal theorem.
* We worked with the basic mechanics of renewal equations.
## Endnotes

* Standard references include:
* Doob [(1948)](https://www.ams.org/journals/tran/1948-063-03/S0002-9947-1948-0025098-8/S0002-9947-1948-0025098-8.pdf)
* Grimmett and Stirzker [(2001)](https://zbmath.org/1015.60002)
* Cox [(1962)](https://zbmath.org/0103.11504)

* Version: `r format(Sys.time(), '%d %B %Y')`
* [Rmd Source](https://tsoo-math.github.io/ucl/intro-renewaltwo.Rmd)