Introduction

A renewal process is an idealized stochastic model for events that occur randomly in time. These temporal events are generically referred to as renewals or arrivals. Here are some typical interpretations and applications.

Basic Processes

The basic model actually gives rise to several interrelated random processes: the sequence of interarrival times, the sequence of arrival times, a counting process, and several age processes. In this section we will define and study the basic properties of each of these processes in turn.

Interarrival Times

Let

X i

denote the

i

interarrival time, that is, the time between the

i 1

and

i

arrivals. Our basic assumption is that

X X 1 X 2

is a sequence of independent, identically distributed, random variables. In statistical terms,

X

corresponds to sampling from the distribution of a generic interarrival time

X

. We assume that

0 X 1

and

X 0 0

, so that the interarrival times are nonnegative, but not identically 0. Let

μ X

denote the common mean of the interarrival times. We allow that possibility that

μ

On the other hand, show that $μ 0$ .

μ

, we will let

σ 2 X

denote the common variance of the interarrival times. Let

F

denote the common distribution function of the interarrival times, so that

The distribution function

F

turns out to be of fundamental importance in the study of renewal processes. We will let

f

denote the probability density function of the interarrival times if the distribution is discrete or if the distribution is continuous and has a density function.

The renewal process is said to be periodic if there exists a positive number

d

such that

n X n d 1

. The largest such

d

is the period.

The Arrival Times

We follow our usual convention that the sum over an empty index set is 0; thus

T 0 0

. On the other hand,

T n

is the time of the

n

arrival for

n

. The sequence

T T 0 T 1

is called the arrival time process, although note that

T 0 0

is not considered an arrival. A renewal process is so named because the process starts over, independently of the past, at each arrival time.

The sequence

T

is the partial sum process associated with the independent, identically distributed sequence of interarrival times

X X 1 X 2

. Partial sum processes associated with independent, identically distributed sequences have been studied in several places in this project. In the remainder of this subsection, we will collect some of the more important facts about such processes.

Recall that if

X

has probability density function

f

(in either the discrete or continuous case), then

T n

has probability density function

f n f n f f f

, the

n

-fold convolution power of

f

Recall that the sequence of arrival times $T$ has stationary, independent increments:

If $m n$ then $T n T m$ has the same distribution as $T n m$ . and thus has distribution function $F n m$ .
If $n 1 n 2 n 3$ then $T n 1 T n 2 T n 1 T n 3 T n 2$ is a sequence of independent random variables.

Show or recall that

$T n n μ$
$T n n σ 2$
$T m T n m n σ 2$

Recall the law of large numbers: $T n n μ$ as $n$ :

With probability 1 (the strong law).
In probability (the weak law).

Show that $T n$ as $n$ with probability 1.

Note that $T n T n 1$ .
Show that $T n T n 1 F 0$ . This can be positive, so with positive probability, more than one arrival can occur at the same time.
Show that there exits $t 0$ such that $X t 0$ .
Use the second Borel-Cantelli lemma to conclude that with probability 1, $X i t$ for infinitely many $i$ .
Conclude that $i 1 X i$ with probability 1.

The Counting Process

Show that $N t n T n t$ for $t 0$ .

Show that if $s t$ then $N t N s$ is the number of arrivals in $s t$ .

Note that as a function of

t

N t

is a (random) step function. with jumps at the distinct values of

T 1 T 2

; the size of the jump at an arrival time is the number of arrivals at that time. In particular,

N t

is an increasing function of

t

More generally, we can define the (random) counting measure corresponding to the sequence of random points

T T 1 T 2

0

. Thus, if

A

is a (measurable) subset of

0

, we will let

N A

denote the number of the random points in

A

In particular, note that with our new notation,

N 0 t N t

and

N s t N t N s

. Thus, the random counting measure is completely determined by the counting process. The counting process is the cumulative measure function for the counting measure, analogous the cumulative distribution function of a probability measure.

Show that for $t 0$ and $n$ ,

$T n t$ if and only if $N t n$ . This event means that at there are at least $n$ arrivals in $0 t$ .
$N t n$ if and only if $T n t T n 1$ . This event means that there are exactly $n$ arrivals in $0 t$ .

Prove the following results:

$N t$ for all $t 0$ if and only if $T n$ as $n$ . Thus conclude that this event has probability 1.
$N t$ as $t$ if and only if $T n$ for all $n$ . Thus conclude that this event has probability 1.

All of the exercises so far in this subsection show that the arrival time process

T

and the counting process

N

are inverses of one another in a sense. The important equivalences in Exercise 8 can be used to obtain the probability distribution of the counting variables in terms of the interarrival distribution function

F

Show that for $t 0$ and $n$ ,

$N t n F n t$
$N t n F n t F n 1 t$

The Renewal Function

The expected number of arrivals up to time

t

is known as the renewal function:

The renewal function turns out to be of fundamental importance in the study of renewal processes. Indeed, the renewal function essentially characterizes the renewal process. It will take awhile to fully understand this, but as a first step, the expansion in terms of indicator variables leads to a nice connection between the renewal function and the interarrival distribution function.

Show that

m t n 1 F n t, t 0

Note that we have not yet shown that

m t

, and note also that this does not follow from the previous exercise. However, we will establish this finiteness condition in the subsection on Moment Generating Functions below.

More generally, if

A

is a (measurable) subset of

0

, let

m A N A

, the expected number of arrivals in

A

Show that $m$ is a positive measure on the measurable subsets of $0$ ; this measure is known as the renewal measure.

Show that

m A n 1 T n A

Show that if $s t$ then $m t m s m s t$ , the expected number of arrivals in $s t$

The last exercise implies that the renewal function actually determines the entire renewal measure. The renewal function is the cumulative measure function, analogous to the cumulative distribution function of a probability measure. Thus, every renewal process naturally leads to two measures on

0

, the random counting measure corresponding to the arrival times, and the measure associated with the expected number of arrivals.

The Age Processes

For $t 0$ , show that $T N t t T N t 1$ . That is, $t$ is in the random renewal interval $T N t T N t 1$ .

is called the current life at time

t

. This variable takes values in the interval

0 t

and is the age of the device that is in service at time

t

. The random process

C C t t 0

is the current life process.

is called the remaining life at time

t

. This variable takes values in the interval

0

and is the time remaining until the device that is in service at time

t

fails. The random process

R R t t 0

is the remaining life process.

is called the total life at time

t

; this variable gives the total life of the device that is in service at time

t

. The random process

L > L t t 0

is the total life process.

Tail events of the current and remaining life can be written in terms of each other and in terms of the counting variables. Suppose that $t 0$ , $x 0 t$ , and $y 0$ . Show that

$R t y N t y N t 0$
$C t x R t x x N t N t x 0$
$C t x R t y R t x x y N t y N t x 0$

Of course, the various equivalent events in the last exercise must have the same probability. In particular, it follows that if we know the distribution of

R t

for all

t

then we also know the distribution of

C t

for all

t

, and in fact we know the joint distribution of

R t

and

C t

for all

t

and hence also the distribution of

L t

for all

t

Basic Comparison

The basic comparison in the following exercise is often useful, particularly for obtaining various bounds. The idea is very simple: if the interarrival times are shortened, the arrivals occur more frequently.

Suppose now that we have two interarrival sequences, $X X 1 X 2$ and $Y Y 1 Y 2$ defined on the same probability space, with $Y i X i$ (with probability 1) for each $i$ . Show that

$T Y n T X n$ for each $n$ .
$N Y t N X t$ for each $t$ .
$m Y t m X t$ for each $t$ .

Examples and Special Cases

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

It is natural to view the successes as arrivals in a discrete-time renewal process.

Consider the renewal process with interarrival sequence $U$ .

Show that the basic assumptions are satisfied and that the mean interarrival time is $μ 1 p$ .
Show that $V$ is the sequence of arrival times.
Show that $Y$ is the counting process (restricted to ).
Show that the renewal function is $m n n p$ for $n$

Run the binomial timeline experiment 1000 times with an update frequency of 10 for various values of the parameters $n$ and $p$ . Note the apparent convergence of the empirical distribution of the counting variable to the true distribution.

Run the negative binomial experiment 1000 times with an update frequency of 10 for various values of the parameters $k$ and $p$ . Note the apparent convergence of the empirical distribution of the arrival time to the true distribution.

Consider again the renewal process with interarrival sequence $U$ . For $n$ , show that

The current life and remaining life at time $n$ are independent.
The remaining life at time $n$ has the same distribution as an interarrival time $U$ , namely the geometric distribution with parameter $p$ .
The current life at time $n$ has a truncated geometric distribution with parameters $n$ and $p$ : $C n k p 1 p k k 01 n 1 1 p n k n$

This renewal process starts over, independently of the past, not only at the arrival times, but at fixed times

n

as well. The Bernoulli trials process (with the successes as arrivals) is the only discrete-time renewal process with this property, which is a consequence of the memoryless property of the geometric interarrival distribution.

We can also use the indicator variables as the interarrival times. This may seem strange at first, but actually turns out to be useful.

Consider the renewal process with interarrival sequence $X$ .

Show that the basic assumptions are satisfied and that the mean interarrival time is $μ p$ .
Show that $Y$ is the sequence of arrival times.
Show that the number of arrivals at time 0 is $U 1 1$ and the number of arrivals at time $i$ is $U i 1$ for $i$ .
Show that the number of arrivals in the interval $0 n$ is $V n 1 1$ for $n$ . This gives the counting process.
Show that the renewal function is $m n n 1 p 1$ for $n$

The age processes are not very interesting for this renewal process. Show that with probability 1,

$C n 0$
$R n 1$

The Moment Generating Function of the Counting Variables

As an application of the last renewal process, we can show that the moment generating function of the counting variable

N t

in an arbitrary renewal process is finite in an interval about 0 for any

t

. This implies that

N t

has finite moments of all orders and in particular that

m t

for any

t

Suppose that

X X 1 X 2

is the interarrival sequence for a renewal process. By the basic assumptions, there exists

a 0

such that

We now consider the renewal process with interarrival sequence

X a X a 1 X a 2

, where

The renewal process with interarrival sequence

X a

is just like the renewal process in Exercise 22, except that the arrival times occur at the points in the sequence

0 a 2 a

For each $t$ , $N t$ has finite moment generating function in an interval about 0.

Show that $X a i X i$ for each $i$ .
Compute the moment generating function of the geometric distribution with parameter $p$ .
Show that $θ N a t$ for $θ 1 p$
Conclude that $θ N t$ for $θ 1 p$

The Poisson Process

The Poisson process, named after Simeon Poisson, is the most important of all renewal processes. The Poisson process is so important that it is treated in a separate chapter in this project. Please review the essential properties of this process:

Consider again the Poisson process with rate parameter $r$ . For $t 0$ , show that

The current life and remaining life at time $t$ are independent.
The remaining life at time $t$ has the same distribution as an interarrival time $X$ , namely the exponential distribution with rate parameter $r$ .
The current life at time $t$ has a truncated exponential distribution with parameters $t$ and $r$ : $C t s r s 0 s t 0 s t$

The Poisson process starts over, independently of the past, not only at the arrival times, but at fixed times

t 0

as well. The Poisson process is the only renewal process with this property, which is a consequence of the memoryless property of the exponential interarrival distribution.

Run the Poisson experiment 1000 times with an update frequency of 10 for various values of the parameters $t$ and $r$ . Note the apparent convergence of the empirical distribution of the counting variable to the true distribution.

Run the gamma experiment 1000 times with an update frequency of 10 for various values of the parameters $k$ and $r$ . Note the apparent convergence of the empirical distribution of the arrival time to the true distribution.

1. Introduction

Basic Processes

Interarrival Times

The Arrival Times

The Counting Process

The Renewal Function

The Age Processes

Basic Comparison

Examples and Special Cases

Bernoulli Trials

The Moment Generating Function of the Counting Variables

The Poisson Process