Renewal Limit Theorems

In the introduction to renewal processes, we noted that the arrival time process and the counting process are inverses, in a sense. The arrival time process is the partial sum process for a sequence of independent, identically distributed variables (the interarrival times). Thus, it seems reasonable that the fundamental limit theorems for partial sum processes (the law of large numbers and the central limit theorem theorem), should have analogs for the counting process. That is indeed the case, and the purpose of this section is to explore the limiting behavior of renewal processes. The main results that we will study, known appropriately enough as renewal theorems, are important for other stochastic processes, particularly Markov chains.

Thus, consider a renewal process with interarrival distribution

F

and mean

μ

, with the assumptions and basic notation established in the introductory section. When

μ

, we let

1 μ 0

. When

μ

, we let

σ

denote the standard deviation of the interarrival distribution.

Basic Theory

A Law of Large Numbers

Suppose that $μ$ . Show that $N t t 1 μ as t$ with probability 1. Thus, $1 μ$ is the limiting average rate of arrivals per unit time.

Recall that $T N t t T N t 1$ for $t 0$
Hence $T N t N t t N t T N t 1 N t$ when $N t 0$
Recall that $N t$ as $t$ with probability 1.
Conclude that $N t 1 N t 1$ as $t$ with probability 1.
Recall that by the strong law of large numbers, $T n n μ$ as $n$ with probability 1.

A Central Limit Theorem

The purpose of this paragraph is to show that the counting variable

N t

is asymptotically normal. Thus, suppose that

μ

and

σ

are finite, and let

Show that the distribution of $Z t$ converges to the standard normal distribution as $t$ .

Let $W n T n n μ σ n$ for $n$ and recall that the distribution of $W n$ converges to the standard normal distribution as $n$ , by the ordinary central limit theorem.
Show that for $z$ , $Z t z T n z t t$ where $n z t t μ z σ t μ 3$ .
Show that $Z t z W n z t w z t$ where $w z t z 1 z σ t μ$ .
Show that $n z t$ as $t$
Show that $w z t z$ as $t$
Recall that $1 Φ z Φ z$ , where as usual, $Φ$ is the standard normal distribution function.
Conclude that $Z t z Φ t$ as $t$

The Elementary Renewal Theorem

The Elementary Renewal Theorem states that the basic limit in the law of large numbers above holds in mean, as well as with probability 1. That is, the limiting mean average rate of arrivals is

1 μ

The elementary renewal theorem is of fundamental importance in the study of the limiting behavior of Markov chains. The proof, sketched in the following exercises, is not nearly as easy as one might hope (recall that convergence with probability 1 does not imply convergence in mean).

Show that $t m t t 1 μ$ .

Note first that the result is trivial if $μ$ , so assume that $μ$ .
Show that $N t 1$ is a stopping time for the sequence of interarrival times $X$ .
Recall that $T N t 1 t$ for $t 0$ .
Use Wald's equation to show that $m t 1 μ t$
Conclude that $m t t 1 μ 1 t$ for $t 0$ .

For the next part of the proof, we will truncate the arrival times, and use the basic comparison method. For

a 0

, let

and consider the renewal process with the sequence of interarrival times

X a X a 1 X a 2

. We will use the standard notation developed in the introductory section..

Show that $t m t t 1 μ$ .

Show that $T a N a t 1 t a$ for $t 0$ and for $a 0$ .
Use Wald's equation again to show that $m a t 1 μ a t a$
Conclude that $m a t t 1 μ a a t μ a 1 t$ for $t 0$ and $a 0$ .
Recall that $m t m a t$ for $t 0$ and $a 0$ .
Conclude that $m t t 1 μ a a t μ a 1 t$ for $t 0$ and $a 0$ .
Conclude that $t m t t 1 μ a$ . for $a 0$ .
Use the monotone convergence theorem to show that $μ a μ$ as $a$ .

The Renewal and Key Renewal Theorems

This section gives the deepest and most useful of the limit theorems in renewal theory. The proofs are rather complicated and are omitted. Suppose that the renewal process is aperiodic. The renewal theorem states that, asymptotically, the expected number of renewals in an interval is proportional to the length of the interval; the proportionality constant is

1 μ

. Specifically, for every

h 0

The renewal theorem is also known as Blackwell's theorem in honor of David Blackwell. The key renewal theorem is an integral version of the renewal theorem. Suppose again that the renewal process is aperiodic and suppose that

g

is a decreasing function from

0

0

with

t 0 g t

. Then

The key renewal theorem can be extended to a more general class of functions known as directly Riemann integrable functions. The name, of course, refers to Georg Riemann. See Stochastic Processes by Sheldon Ross for more details.

Use the renewal theorem to prove the elementary renewal theorem:

Let $a n m n n 1$ . for $n$ . Use the renewal theorem to show that $a n 1 μ$ as $n$ .
Conclude that $1 n k 0 n 1 a k 1 μ$ as $n$ .
Conclude that $m n n 1 μ$ as $n$ .
Use the fact that the renewal function $m$ is increasing to show that for $t 0$ , $t t m t t m t t t t m t t$
Use the squeeze theorem for limits to conclude that $m t t 1 μ$ as $t$ .

Conversely, the elementary renewal theorem almost implies the renewal theorem. Assume that $g x t m t x m t$ exists for each $x 0$ .

Note that $m t x y m t m t x y m t x m t x m t$
Let $t$ to conclude that $g x y g x g y$ for all $x 0$ and $y 0$ .
Show that $g$ is increasing.
Conclude that $g x c x$ for $x 0$ where $c$ is a constant.
Exactly as in parts (a)-(c) of the previous exercise, show that $m n n c$ as $n$ .
From the elementary renewal theorem, conclude that $c 1 μ$ .

Show that the key renewal theorem implies the renewal theorem: apply the key renewal theorem to $g h x 0 x h$ where $h 0$ .

Examples and Special Cases

The Poisson Process

Recall that the Poisson process, the most important of all renewal processes, has interarrival times that are exponentially distributed with rate parameter

r 0

. Thus, the interarrival distribution function is

F x 1 r x

for

x 0

and the mean interarrival time is

μ 1 r

Verify each of the following directly:

The law of large numbers for the counting process.
The central limit theorem for the counting process.
The elementary renewal theorem.
The renewal theorem.

Bernoulli Trials

Suppose that

X X 1 X 2

is a sequence of Bernoulli trials with success parameter

p 01

. Recall that

X

is a sequence of independent, identically distributed indicator variables with

p X 1

. We have studied a number of random processes derived from

X

Consider the renewal process with interarrival sequence $U$ . Thus, $μ 1 p$ is the mean interarrival time, and $Y$ is the counting process. Verify each of the following directly:

The law of large numbers for the counting process.
The central limit theorem for the counting process.
The elementary renewal theorem.

Consider the renewal process with interarrival sequence $X$ . Thus, the mean interarrival time is $μ p$ . and the number of arrivals in the interval $0 n$ is $V n 1 1$ for $n$ . Verify each of the following directly:

The law of large numbers for the counting process.
The central limit theorem for the counting process.
The elementary renewal theorem.

3. Renewal Limit Theorems