Renewal Process

This is a fundamental stochastic process useful in modelling arrivals and interarrival times. Some definitions will make the usage clear.

Let $S_i$ denote the $i$th renewal time or the time when the $i$th arrival takes place. By definition, $S_0=0$. We can also define $$\begin{array}{rl}{S}_n& =S_{n-1}+{\xi }_n\\ S_n& ={\xi }_1+{\xi }_2+\cdots +{\xi }_{n-1}\end{array}$$ where ${\xi }_i$ are positive ($P(\xi >0)=1$) independent identically distributed variables representing the interarrival times. We also define $$\begin{array}{rl}{N}_t& ={\mathrm{argmax}}_k{S}_k\le t\\ S_n>t& =N_t<n\end{array}$$ or, $N_t$ is simply the number of arrivals till the time $t$.

Define the following quantity $$\begin{array}{rl}{F}^{n\ast }& =F_{\xi }\ast \dots \ast F_{\xi }n\text{ times}\\ u(t)& =\sum _{i=1}^{\mathrm{\infty }}{F}^{n\ast }(t)\end{array}$$ It can be shown that the function $u(t)$ converges. The expectation of $N_t$ then becomes $$\begin{array}{rl}E[N_t]& =E[\text{number of }n\text{ such that }{S}_n\le t]\\ & =E[\sum _{n=1}^{\mathrm{\infty }}I(S_n\le t)]\text{ sum of Indicators will equal }n\\ & =\sum _{n=1}^{\mathrm{\infty }}P(S_n\le t)\text{ since }E[\text{Indicator}]\text{ is just the function inside indicator}\\ & =\sum _{n=1}^{\mathrm{\infty }}{F}^{n\ast }(t)\text{ by defining cumulative as sum of }\xi \text{s}\\ & =u(t)\end{array}$$

Laplace Transform

For a density function $f$ defined from ${\mathbb{R}}^{\ge 0}\to \mathbb{R}$, Laplace transform is $$\begin{array}{r}{L}_f(s)={\int }_{{\mathbb{R}}^{\ge 0}}{e}^{-sx}f(x)dx\end{array}$$ The following properties hold for this transform

1. If $f$ is a probability density function, then $$\begin{array}{r}E[e^{-sx}]=L_f(s)\end{array}$$

2. if $f_1$ and $f_2$ are two probability density functions, then $$\begin{array}{r}{L}_{f_1\ast f_2}(s)=L_{f_1}(s)L_{f_2}(s)\end{array}$$

3. If $F$ is the cumulative probability distribution for $X$ and $p$ is the probability density function, then $$\begin{array}{r}{L}_{F_X}(s)=\frac{L_{p_X}(s)}{s}\end{array}$$ which can be proven using integration by parts as follows $$\begin{array}{r}{L}_{F_X}(s)={\int }_{{\mathbb{R}}^{\ge 0}}{F}_X(x)\frac{d(e(-sx))}{s}=0+\frac{1}{s}{\int }_{{\mathbb{R}}^{\ge 0}}{p}_X(x)e^{-sx}dx\end{array}$$

Calculating the Expectation

Armed with the concept of a Laplace transform, we make the following observation first $$\begin{array}{rl}u(t)& =\sum _{i=1}^{\mathrm{\infty }}{F}^{n\ast }(t)=F(t)+\sum _{i=2}^{\mathrm{\infty }}{F}^{n\ast }(t)\\ & =F(t)+(\sum _{i=1}^{\mathrm{\infty }}{F}^{n\ast }(t))\ast F(t)\\ & =F(t)+u(t)\ast F(t)\\ u(t)& =F(t)+u(t)\ast p(t)\end{array}$$ where $p$ is the probability density function and the last line stems from the fact that $\int u\ast F=\int u(x-y)dF(y)=\int u(x-y)p(y)dy$. Taking Laplace transform on both sides,

$$\begin{array}{rl}{L}_u(s)& =L_F(s)+L_u(s)L_p(s)\\ L_u(s)& =\frac{L_p(s)}{s}+L_u(s)L_p(s)\text{ from point 3 above}\\ L_{u(s)}& =\frac{L_p(s)}{s(1-L_p(s))}\end{array}$$

The last equation can be used to calculate the laplace transform of $u(t)$ and consecutively guess the functional form of $u(t)$.

Limit Theorems for Renewal Processes

The following two theorems hold true for Renewal processes

1. If $E[\xi ]=\mu <\mathrm{\infty }$, then $$\begin{array}{r}\underset{t\to \mathrm{\infty }}{lim}\frac{N_t}{t}=\frac{1}{\mu }\end{array}$$ which is analogous to the strong law of large numbers. This can be proven as follows $$\begin{array}{r}{S}_{N_t}\le t\le S_{N_t+1}\text{ from the definition of }{N}_t\\ \text{or, }\frac{N_t}{S_{N_t+1}}\le \frac{N_t}{t}\le \frac{N_t}{S_{N_t}}\end{array}$$ we can calculate the limits on the two bounds as $$\begin{array}{r}\underset{t\to \mathrm{\infty }}{lim}\frac{N_t}{S_{N_t}}=\underset{n\to \mathrm{\infty }}{lim}\frac{n}{S_n}=\frac{1}{\mu }\end{array}$$ from the strong law of large numbers applied to $\underset{n\to \mathrm{\infty }}{lim}\frac{S_n}{n}$. Similarly, one can show $$\begin{array}{r}\underset{t\to \mathrm{\infty }}{lim}\frac{N_t}{S_{N_t+1}}=\underset{t\to \mathrm{\infty }}{lim}\frac{N_t}{N_t+1}\underset{t\to \mathrm{\infty }}{lim}\frac{N_t+1}{S_{N_t+1}}=1\ast \frac{1}{\mu }\end{array}$$

2. If $Var(\xi )={\sigma }^2<\mathrm{\infty }$, then $$\begin{array}{r}\underset{t\to \mathrm{\infty }}{lim}\frac{N_t-t/\mu }{\sigma \sqrt{t}/{\mu }^{3/2}}=\mathcal{N}(0,1)\end{array}$$ which is analogous to the central limit theorem. It can be proven by considering the CLT on $\xi$s $$\begin{array}{rl}\underset{n\to \mathrm{\infty }}{lim}P(\frac{S_n-n\mu }{\sigma \sqrt{n}}\le x)& =\text{CDF of }\mathcal{N}(0,1)\\ \text{or, }\underset{n\to \mathrm{\infty }}{lim}P(S_n\le n\mu +\sigma \sqrt{n}x)& =\text{CDF of }\mathcal{N}(0,1)\\ \text{or, }\underset{n\to \mathrm{\infty }}{lim}P(N_t\ge n)& =\text{CDF of }\mathcal{N}(0,1)\text{ from definition of }{N}_t\text{, where }t=n\mu +\sigma \sqrt{n}x\end{array}$$ We substitute $n\mu =t$ for very large value of $n$, since the total time will become total variables into the expected time for one $\xi$ when $n$ is large. Hence, $$\begin{array}{rl}n& =\frac{t}{\mu }-\frac{\sigma \sqrt{t}}{{\mu }^{3/2}}x\\ \underset{n\to \mathrm{\infty }}{lim}P(N_t\ge n)& =\underset{n\to \mathrm{\infty }}{lim}P(\frac{N_t-t/\mu }{\sigma \sqrt{t}/{\mu }^{3/2}}\le x)=\text{CDF of }\mathcal{N}(0,1)\end{array}$$