Renewal Theory

In this section we will study another generalization of the Poisson process. There we had a counting process with interarrival times that were iid exponential. Now we will allow other distributions for the interarrival times.

Let {X_n;n≥1} be a sequence of nonnegative iid rv’s with common cdf F. Let {N(t);t≥0 } be counting process such that X_n is the time between the (n-1)^st and the n^th event. Then {N(t);t≥0 } is called a renewal process, and the times when an event happens are called “renewals”.

In order to avoid some technical issues we will also assume that F(0)=P(X_n=0)<1. The condition F(0)<1 means that there is some chance that the process stays in the same state for some time, it does not (necessarily) immediately jump away.

Let μ=E[X_n] denote the mean time until the next event, and note that because of the condition that X_n be nonnegative we have 0<μ≤∞.

Set S₀=0 and S_n=∑_i=1ⁿX_i

so S_n is the time of the n^th event (or renewal). As the number of events by time t will equal the largest value of n for which the n^th event has occurred before or at time t, we have

N(t) = max{n: S_n≤t}

Here is the reasoning: say S₄≤t and S₅>t so the fourth renewal had occurred before time t but the fifth renewal occurred after time t, so N(t), the number of renewals at time t, is 4

Note that S_n is the sum of independent identically distributed rv’s, so by the law of large numbers

S_n/n → μ in probability.

Since μ>0 this means that S_n must be going to infinity as n goes to infinity. Thus S_n can be less than or equal to any finite t for at most a finite number of n. Hence N(t) must be finite with probability 1.

For the Poisson process we found that

N(t)≥n S_n≤t

The same equivalence holds here and can in principle be used to find the distribution of N(t):

Now since the {X_i;i≥1} are iid F, it follows that S_n=∑_i=1ⁿX_i has cdf F_n, the n-fold convolution of F. Therefore we find

P(N(t)=n) = F_n(t)-F_n+1(t)

Example

let’s find out what this means in a case where we already know the answer: say X_n~Exp(μ). So the interarrival times have an exponential distribution, therefore this should be a regular Poisson process. Now

so this works fine. The difficulty in using this theorem is usually calculating the n-fold convolution

Example

Say X_n~Ber(p). So S_n is the sum of independent Bernoulli rv’s, and so S_n~B(n,p). Now

Let m(t)=E[N(t)]. m(t) is called the renewal function, and one of the main issues in renewal theory is to determine its properties. To find it we first need a well-know lemma:

Lemma

Say X is a non-negative rv. Then

proof see Theory of Probability

Proposition

m(t)= ∑_n=1^∞ F_n(t)

proof

Example

again let’s find out what this means in a case where we already know the answer: say X_n~Exp(μ). So the interarrival times have an exponential distribution, therefore this should be a regular Poisson process, and therefore m(t)=μt. To make the calculation easier let’s define

Proposition

m(t)<∞ \(\forall\) 0≤t<∞

without proof

Let’s assume the interarrival times X_n have a continuous distribution F. Then we find

Now suppose that the time of the first renewal x is less than t. Then, using the fact that a renewal process essentially starts over when a renewal occurs, it follows that the number of renewals by time t would have the same distribution as 1 plus the number of renewals in the first x-t time units. Therefore

Example

again let’s find out what this means in a case where we already know the answer: say X_n~Exp(μ). So the interarrival times have an exponential distribution, therefore this should be a regular Poisson process, and therefore m(t)=μt. We will do this simply by verifying that m(t)=μt satisfies the integral equation:

Example

say X_n~U[0,1] let t<1, then

unfortunately this is one of the few cases were these calculations can be done analytically. Quite generally integral equations are hard to solve.

---

Next we will derive one of the main results known as the elementary renewal theorem :

Theorem

m(t)/t→1/μ as t→∞

proof

We begin by considering S_N(t). N(t) is the number of arrivals at time t. S_n is the time of the n’th arrival , so S_N(t) is the time of the last event prior to or at time t. Similarly S_N(t)+1 is the time of the first arrival after time t.

Here is an illustration:

Proposition

N(t)/t →1/μ as t→∞ with probability 1

proof

clearly we have S_N(t) ≤ t < S_N(t)+1, so

Note that the same proof works even if μ=∞, with 1/μ=0

The number 1/μ is called the rate of the renewal process.

The elementary renewal theorem follows from this, with some technical details we will omit.

Remark

it might seem that

m(t)/t→1/μ as t→∞

should just follow directly from the fact that

N(t)/t→1/μ as t→∞

but things turn out to be a bit more complicated:

Example:

Say U~U[0,1], and let Y_n = n I_[0,1/n](U). Now

P(|Y_n -0|>ε) = P(Y_n>ε) = 1/n → 0 if n>1/ε

so Y_n → 0 in probability.

but E[Y_n] = nP(U<1/n) = n(1/n) = 1

Example

You have a radio which uses a single battery. When the battery fails you replace it with a new one. Say a battery has a lifetime with a U[30,60] distribution, then at what rate do you change batteries?

let N(t) be the times when the batteries failed, then N(t)/t →1/μ = 1/45

Example

Say we play the following game: we pick cards form a standard card deck (52 cards). After each draw we put the card back and shuffle. We do this until the same card gets drawn twice in a row. What is the expected number of trials needed?

Actually let’s consider a much more general game: in each trial there are n items numbered 1-n to choose from, and item i is chosen with probability p_i. What is the expected number of trials until an item is chosen k times in a row?

We begin by computing the expected number of Bernoulli trials with success probability p until k successive successes occur. Let this be E[T]. Let Z be the first time a failure occurs, then of course Z~Geom(1-p). Now

For example, when flipping a fair coin the expected number trials needed until 5 “heads” in a row is

(1-(½)⁵)/{(½)⁵(1-½))} = (1-(½)⁵)/(½)⁶ = 48

Let’s return to the game and assume that as soon as one “round” ends we play again, and so on. For each i let us determine the rate at which item i is the “winner” (appears first k times in a row). Now, every time this happens constitutes a renewal. Let N_i be the number of trials between successive wins of i, then by the renewal theorem

Rate at which i wins =1/E[N_i]

But now we are only interested in “i wins”, so each trial is a Bernoulli trial and the above shows

and so the long run proportion of games won by i is

and by the strong law of large numbers this is also the probability that i wins.

Finally, the

rate at which games end =

∑ rate at which games i wins =

Now, as everything starts over when a game ends, it follows from the elementary renewal theorem that the rate at which games end is equal to the reciprocal of the mean time of a game, so

As a numerical example, say we roll a die until the same number gets rolled 4 times in a row. What is the expected number of rolls?

Now p_i=1/6 i=1,..,6, so

---

Above we saw essentially a Weak Law of Large Numbers for renewal processes. Next we have a Central Limit Theorem

Theorem

Let μ and σ be the mean and the standard deviation of an interarrival time. Let Z~N(0,1). Then

proof

Let

r_t = t/μ +yσ√t/μ³. Note that r_t→∞ as t→∞. Then

Definition

A nonnegative rv X is said to be lattice if there exists d≥0 such that

∑_nP(X=nd) = 1

That is, X is lattice if it only takes values that are integral multiples of some nonnegative number d. The largest d having this property is called the period of X. If F is the distribution of a rv X that is lattice, F is also called lattice.

Theorem (Blackwell)

1. if F is not lattice, then

m(t+a)-m(t) → a/μ

2. if F is lattice with period d, then

E[number of renewals at nd] → d/μ

proof (outline)

1. let

g(a) = lim_t→∞[m(t+a)-m(t)]

and we will assume that this limit exists (the missing part of the proof). Now

g(a+b) =

lim_t→∞[m(t+a+b)-m(t)] =

lim_t→∞[m(t+a+b)-m(t+a) + m(t+a)-m(t)] =

lim_t→∞[m(t+a+b)-m(t+a)] + lim_t→∞[m(t+a)-m(t)]=

g(b) + g(a)

for any a, b. But

g(a) = g(a+0) = g(a)+g(0)

so g(0)=0

Also

g(a+h)-g(a) = g(a)+g(h)-g(a) = g(h)

so g’(a) = lim_h→0 [(g(a+h)-g(a)/h] =lim_h→0 [g(h)/h] =: c

so g(a) =ca

What is c? To find out define

x_n = m(n) - m(n-1) n=1,2,..

Then

lim_n→∞[m(n+1)-m(n)] = g(1) = c

and therefore

lim_n→∞[(x₁+..+x_n)/n] = c

or

lim_n→∞[m(n)/n] = c

but by the elementary renewal theorem c = 1/μ

2. when F is lattice with period d clearly this limit can not exist because it would have to depend on how many points of the form nd are in the interval. So the relevant version of the theorem concerns the limit at points of the form nd, and again the result follows from the elementary renewal theorem.

---

Definition

Let h be a function on [0,∞). For any a>0 define

m_n(a) = inf{h(t); (n-1)a ≤ t ≤ na}

and

M_n(a) = sup{h(t); (n-1)a ≤ t ≤ na}

h is called directly Riemann integrable if

∑_n m_n(a) and ∑_n M_n(a) are finite for all a>0 and

lim_a→0 a∑_n m_n(a) = lim_a→0 a∑_n M_n(a)

Theorem

say we have

1. h(t)≥0 for all t ≥0

2. h(t) is non increasing

3. ∫h(t)dt < ∞

then h is directly Riemann integrable

proof omitted

Theorem (The Key Renewal Theorem)

If F is not lattice, and if h(t) is directly Riemann integrable, then

proof omitted

Lemma

Let S_N(t) be the time of the last renewal before time t. Then

proof

Example

say {N(t)} is a Poisson process with rate λ, then

1-F(t) = exp(-λt)

and