Renewal theory
Renewal theory
1
Renewal process
A renewal process (Nt)t≥0 is a counting process for which the
times τj ≥ 0 between successive events, called renewals, are
independent and identically-distributed non-negative-real-valued
random variables with an arbitrary common distribution function F .
I We assume F (0) < 1.
I A Poisson process is a renewal process where the τi have an
exponential distribution.
I A renewal process that is not a Poisson process is not
Markovian.
2
A picture of Nt
0 1 2 3 4 5 6
0
1
2
3
4
5
t
N
t
Tn =
∑n
i=1 τi is time of nth jump.
3
Counting vs waiting representations
When we looked at the Poisson process, we saw that we could use
a counting process description in terms of the number Nt of points
in the interval [0, t] or a waiting time description in terms of the
time Tn until the nth event. This carries over to the study of
renewal processes. Specifically
I {Nt ≥ n} = {Tn ≤ t}
I {Nt < n} = {Tn > t}
I {Nt = n} = {Tn ≤ t < Tn+1}
I TNt ≤ t < TNt+1.
4
Example
Light bulbs have a lifetime that has distribution function F . If a
light bulb burns out, it is immediately replaced. Let Nt be the
number of bulbs that have failed by time t. Then (Nt)t≥0 is a
renewal process.
5
Nt goes to ∞ as t →∞
For any fixed n,
lim
t→∞
P(Nt ≥ n) = lim
t→∞
P(Tn ≤ t)
= 1.
This implies that with probability 1, Nt →∞ as t →∞.
6
Questions
I Can there be an explosion (that is an infinite number of
renewals in a finite time)?
I What is the distribution of Nt?
I What is the average renewal rate? That is, at which rate does
Nt →∞?
7
Explosion?
For any fixed t <∞, P(Nt =∞) = 0. To see this, write
P(Nt =∞) = lim
n→∞
P(Nt ≥ n) = lim
n→∞
P(Tn ≤ t)
= lim
n→∞
P(
n∑
i=1
τi ≤ t)
= lim
n→∞
P(e−
∑n
i=1 τi ≥ e−t).
Using Markov’s inequality (P(X ≥ a) ≤ E[X ]/a for X ≥ 0 and
a > 0) we have
P(e−
∑n
i=1 τi ≥ e−t) ≤ etE[e−
∑n
i=1 τi ] = et
(
E[e−τ1 ]
)n
,
which goes to 0 as n→∞ since E[e−τ1 ] < 1 (why?) 8 Distribution of Nt P(Nt = n) = P(Tn ≤ t < Tn+1) = P(Tn ≤ t)− P(Tn ≤ t,Tn+1 ≤ t) = P(Tn ≤ t)− P(Tn+1 ≤ t) = FTn(t)− FTn+1(t) where FTn is the distribution function of Tn. There are very few F for which this is easy to evaluate (can you name one?) 9 Distribution of Nt Above, we saw that TNt ≤ t < TNt+1. It follows that Nt Nt + 1 · Nt + 1 TNt+1 = Nt TNt+1 < Nt t ≤ Nt TNt Since Nt →∞ as t →∞, the Law of Large Numbers tells us that, with probability one, both the first and last terms approach µ−1. Therefore, with probability one, lim t→∞ Nt t = µ−1, and we see that, for large t, Nt grows like t/µ. 10 The LLN for Nt 0 10 20 30 0 1 0 2 0 3 0 4 0 5 0 t N _ t ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● 11 Example Jenny uses her smart phone a lot, so she carries a powerful portable charger with her. Whenever her phone gives her a low energy warning she immediately charges her phone for 30 minutes and that charge lasts for a U(30, 60) (minutes, independent of previous charges) amount of time before she receives a warning. On average how many times per hour does Jenny charge her phone? I µ = E[τ1] = (45 + 30)/60, so the rate is lim t→∞ Nt t = 1 µ = 60 75 = 4 5 per hour 12 M/G/1/1 queue The arrival process is Poisson with parameter λ. There is no “queue”: when an arriving customer finds the server busy, s/he does not enter. Service times are independent and identically-distributed with distribution function G (with mean µG ). I What is the rate at which customers actually enter the system? I What proportion of potential customers actually receive service? 13 M/G/1/1 queue Let Nt be the number of customers who have been admitted by t. Then the times between successive entries of customers are made up of: I a service time, and then I a waiting time from the end of service until the next arrival. 0 2 4 6 8 0 .0 0 .5 1 .0 1 .5 2 .0 t X _ t ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● 14 M/G/1/1 queue The mean time between renewals is µ = 1 λ + µG . So the rate at which customers actually enter the system is 1 µ = 1 1 λ + µG = λ 1 + λµG . Customers arrive at rate λ, and so the proportion that actually enter the system is entry rate arrival rate = λ 1+λµG λ = 1 1 + λµG . If λ = 10 per hour and µG = 0.2 hours, then on average only 1 out of 3 customers will actually get served! 15 G/G/n/m queue In the very general setting of the G/G/n/m queue, the beginnings of busy periods (i.e. times at which a customer arrives to find the system empty) constitute renewal times. The time of the first “renewal” will typically have a different distribution though 16 The Renewal Central Limit Theorem If E[τj ] = µ, Var(τj) = σ2 <∞, then Nt − tµ√ tσ2/µ3 d−→ N (0, 1) as t →∞. So for each x , lim t→∞ P ( Nt − tµ√ tσ2/µ3 ≤ x ) = Φ(x), where Φ is the standard normal cdf. 17 Residual lifetime The residual lifetime Rt at time t is the amount of time until the next renewal time. Since TNt ≤ t < TNt+1, the residual lifetime at time t is Rt = TNt+1 − t > 0.
If τi are exponential(δ) then what is the distribution of Rt?
Let F be the c.d.f. of τ1. We will study the large t behaviour of Rt
assuming that F is non-lattice (that is, it does not concentrate its
mass at multiples of a fixed amount), and has finite mean µ.
18
Residual lifetime for large t
Theorem: If F is non-lattice with finite mean µ and x ≥ 0 then
lim
t→∞
P(Rt ≤ x) =
1
µ
∫ x
0
(1− F (y))dy .
Recall that for Z ≥ 0,
E[Z ] =
∫ ∞
0
(1− FZ (z))dz ,
so
1−F (y)
µ
, y ≥ 0, is a probability density function.
19
Example
A computer receives packets of information whose sizes are
uniformly distributed between 1 and 5 GB. It saves them on hard
drives of total size 700GB, until the a hard drive is full.
I For the first file for which there is not enough space on a hard
drive, find the approximate distribution and the mean of the
length of the residual part that the hard drive does not have
space for.
0 20 700
× ×× ××× × × × ×× × × × × ×
R700
I Give a (symmetric) interval to which, the total number of
saved files belongs with probability ≈ 0.95.
20
Example solution
Here, “time” is measured in GB! We are looking for the residual
lifetime at time t = 700, where t is considered to be large
(compared to the size of a packet).
I The limiting distribution of the residual part has density
1
µ
(1− F (x)) =
{
1
3
if x ∈ [0, 1)
5−x
12
if x ∈ [1, 5].
I The mean of the residual part is 31/18, which is greater than half of the
mean interval length, which is 3/2.
I We have
Nt − tµ√
t
µ
× σ2
µ2
d
≈ N (0, 1).
With t = 700, µ = 3, σ2 = 4/3, the desired (symmetric) interval is
233.33± 5.88× 1.96 = (221.81, 244.85).
21
Age
The age of the renewal process at time t is the time since the most
recent renewal, i.e. At = t − TNt .
Theorem: If F is non-lattice with finite mean µ and x ≥ 0 then
lim
t→∞
P(At ≤ x) =
1
µ
∫ x
0
(1− F (y))dy .
22
Age – some intuition
I Consider the process after it has been in operation for a long
time.
I When we look backwards in time, the times between
successive renewals are still independent and
identically-distributed with distribution F .
I Looking backwards, the residual lifetime at t is exactly the
age at t of the original process.
23
Example
Suppose (Nt)t≥0 is a Poisson process with rate λ, find the
(approximate) distributions of Rt , At and (Rt ,At) when t is large.
What is the expected duration of the inter-event time
TNt+1 − TNt ?
24
Renewal CLT – sketch proof
Recall that Tn =
∑n
i=1 τi .
Let Z = Tn−nµ√
nσ2
d
≈ N (0, 1). Then
P(Nt ≥ n) = P(Tn ≤ t)
≈ P
(
Z ≤
t − nµ
√
nσ2
)
= P
(
Z ≥
nµ− t
√
nσ2
)
.
25
Renewal CLT – sketch proof
Now, we choose n = n(x , t) such that nµ−t√
nσ2
≈ x . That is, we put
n(x , t) ≈ t
µ
+ x
√
t
µ
· σ2
µ2
.
Then, reversing the above argument, we have
P (Z ≥ x) ≈ P(Nt ≥ n(x , t))
≈ P
(
Nt − tµ√
tσ2/µ3
≥ x
)
.
26
Residual lifetime for large t – sketch of proof
Consider a period of n renewals. The proportion of time that the
residual lifetime is greater than x is, by the strong Law of Large
Numbers,∑n
i=1(τi − x)1{τi>x}∑n
i=1 τi
=
1
n
∑n
i=1(τi − x)1{τi>x}
1
n
∑n
i=1 τi
→
E
[
(τ1 − x)1{τ1>x}
]
E[τ1]
.
as n approaches infinity.
27
Residual lifetime for large t – sketch of proof
Under the stated conditions, it can also be shown that∑n
i=1(τi − x)1{τi>x}∑n
i=1 τi
=
∫ Tn
0
1{Rs>x}ds
Tn
→ lim
t→∞
P(Rt > x).
Hence
lim
t→∞
P(Rt > x) =
E
[
(τ1 − x)1{τ1>x}
]
E[τ1]
=
1
µ
∫ ∞
0
P
(
(τ1 − x)1{τ1>x} > y
)
dy
=
1
µ
∫ ∞
x
P(τ1 > u)du.
28
Age proof
For x , y ≥ 0 the events {Rt > x ,At > y} and {Rt−y > x + y} are
equal so
lim
t→∞
P(Rt > x ,At > y) = lim
t→∞
P(Rt−y > x + y)
=
1
µ
∫ ∞
x+y
[1− F (z)]dz .
Setting x = 0 we get
lim
t→∞
P(At ≤ y) =
1
µ
∫ y
0
[1− F (z)]dz
= lim
t→∞
P(Rt ≤ y).
29
Example
For large t, find the joint probability density function of (Rt ,At) in
the computer packets example.
I First,
P(At ≤ x ,Rt ≤ y) = P(At ≤ x)−P(Rt > y)+P(At > x ,Rt > y),
so
∂2P(At ≤ x ,Rt ≤ y)
∂x∂y
=
∂2P(At > x ,Rt > y)
∂x∂y
.
I When t is large, P(At > y ,Rt > x) ≈
∫∞
x+y
1−F (z)
µ
dz .
I Hence, the joint pdf is 1/12 if 1 < x + y < 5 and 0 otherwise. 30