CS计算机代考程序代写 Renewal theory

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