Renewal Processes

(1)

Renewal Processes

Bo Friis Nielsen¹

1DTU Informatics

02407 Stochastic Processes 8, October 27 2020

Bo Friis Nielsen Renewal Processes

Renewal Processes

Today:

I Renewal phenomena Next week

I Markov Decision Processes Three weeks from now

I Brownian Motion

A Poisson proces

SequenceX_i, whereX_i ∼exp(λ_i)orX_i ∼PH((1),[−λ]).

W_n=Pn i=1X_i

N(t) = max

n≥0{W_n≤t}= max

n≥0

( X

i=n

X_i ≤t )

Let us consider a sequence, whereX_i ∼PH(α,S).

Underlying Markov Jump Process

LetJ_i(t)be the (absorbing) Markov Jump Process related toX_i. DefineJ(t) =J_i(t−PN(t)

j=1 τ_i)

P(J(t+ ∆) =j|J(t) =i) =S_ij +s_iα_j Such that

A=S+sα

is the generator for the continued phase proces -J(t)Note the similarity with the expression for a sum of two phase-type distributed variables

(2)

Distribution of N (t )

ForX_i∼exp(λ)P(N(t) =n) = ^(λt_n!⁾ⁿe^−λt What ifX_i ∼PH(α,S) Generator up to finiten

A_n=







S sα 0 0 . . . 0 0

0 S sα 0 . . . 0 0

0 0 S sα . . . 0 0

0 0 0 S . . . 0 0

... ... ... ... . .. ... ... ... ...

0 0 0 0 . . . S sα

0 0 0 0 . . . 0 S







A quasi-birth process - to calculateP(N(t) =n)we would need the matrix-exponential of an(n+1)pdimensional square matrix P(N(t)>n) =P(W_n≤t),W_nis an “Erlang-type” PH variable

Renewal function

X_i∼exp(λ)thenM(t) =E(N(t)) =λt Probability of having a point in[t;t+dt(P(∃n:Wn∈[t;t+dt()The probability of a point is the probability thatJ(t)has an instantaneous visit to an absorbing state (J(t)shifts from someJ_n()toJ_n+1

P(N(t+dt)−N(t) =1|J(t) =i) = s_idt+o(dt) P(J(t) =i) = αe^At1_i

P(N(t+dt)−N(t) =1) = αe^Atsdt+o(dt) M(t) =E(N(t) =

Z t 0

αe^Ausdu =α Z t

0

e^Audus The generatorAis singular (A1=0,πA=0)

Calculation of R

t

0

e

^Au

du

First we note that1π−Ais non-singular

Z t 0

e^Audu = Z t

0

(1π−A)⁻¹(1π−A)e^Audu

= (1π−A)⁻¹ Z t

0

1πe^Audu− Z t

0

Ae^Audu

Z t 0

1πe^Audu = Z t

0

1π

∞

X

n=0

(Au)ⁿ n! du=

Z t 0

1

∞

X

n=0

π(Au)ⁿ n! du

= Z t

0

1πdu=t1π

Z t 0

Ae^Audu = e^At −I

Back to M(t )

We have(1π−A)1=1 andπ(1π−A) =π, so M(t) = α(1π−A)⁻¹h

t1π−

e^At −Ii s

= πst+α(1π−A)⁻¹s−α(1π−A)⁻¹e^Ats We haveα(1π−A)⁻¹e^Ats→α(1π−A)⁻¹1πs=πs

(3)

Renewal Processes

F(x) = P{X ≤x} W_n = X₁+· · ·+X_n N(t) = max{n:Wn≤t}

E(N(t)) = M(t) Renewal function

Age, Residual Life, and Total Life (Spread)

γ_t = W_N(t)+1−t(excess or residual life time) δ_t = t−W_N(t₎(current life or age)

β_t = δ_t +γ_t(total life or spread

Topics in renewal theory

Elementary renewal theorem ^M(t_t ⁾ → _µ¹ E W_N(t)+1

=µ(1+M(t)) M(t) =P∞

n=1F_n(t), F_n(t) =Rt

0F_n−1(t−x)dF(t) Renewal equationA(t) =a(t) +Rt

0A(t−u)dF(u) Solution to renewal equation

A(t) =Rt

0a(t−u)dM(u)→ _µ¹R∞ 0 a(t)dt Limiting distribution of residual life time lim_t→∞P{γ_t ≤x}= _µ¹Rx

0(1−F(u))du

Limiting distribution of joint distribution of age and residual life timelim_t→∞P{γ_t ≥x, δ_t ≥y}= _µ¹R∞

x+y(1−F(z))dz Limitng distribution of total life time (spread)

lim P{β ≤x}=

Rx 0tdF(t)

Continuous Renewal Theory (7.6)

P{W_n≤x} = F_n(x) with Fn(x) =

Z x 0

Fn−1(x −y)dF(y) The expression forF_n(x)is generally quite complicated Renewal equation

v(x) =a(x) + Z x

0

v(x −u)dF(u)

v(x) = Z x

0

a(x−u)dM(u)

(4)

Expression for M(t )

P{N(t)≥k} = P{W_k ≤t}=F_k(t)

P{N(t) =k} = P{W_k ≤t,W_k+1>t}=F_k(t)−F_k+1(t) M(t) = E(N(t)) =

∞

X

k=1

kP{N(t) =k}

=

∞

X

k=0

P{N(t)>k}=

∞

X

k=1

P{N(t)≥k}

=

∞

X

k=1

F_k(t)

E [W

_N(t₎₊₁

]

E[W_N(t)+1] = E





N(t)+1

X

j=1

X_j



=E[X₁] +E





N(t)+1

X

j=1

X_j





= µ+

∞

X

j=2

E

X_j1(X₁+· · ·+X_j−1≤t) X_jand1(X₁+· · ·+X_j−1≤t)are independent

=µ+

∞

X

j=2

E X_j

E

1(X₁+· · ·+X_j−1≤t)

=µ+µ

∞

X

j=2

F_j−1(t) E[W_N(t)+1] = exp[X₁]E[N(t) +1] =µ(M(t) +1)

Poisson Process as a Renewal Process

Fn(x) =

∞

X

i=n

(λx)ⁿ

n! e^−λx =1−

n

X

i=0

(λx)ⁿ n! e^−λx M(t) = λt

Excess life, Current life, mean total life

The Elementary Renewal Theorem

t→∞lim M(t)

t = lim

t→∞

E[N(t)]

t = 1 µ The constant in the linear asymptote

t→∞lim h

M(t)−µ t

i

= σ²−µ² 2µ² Example with gamma distribution Page 367

(5)

Asymptotic Distribution of N (t )

WhenE[X_k] =µandVar[X_k] =σ²both finite

t→∞lim P

(N(t)−t/µ ptσ²/µ³ ≤x

)

= 1

√2π Z x

−∞

e^−y²^/2dy

Limiting Distribution of Age and Excess Life

tlim→∞P{γ_t ≤x}= 1 µ

Z x 0

(1−F(y))dy =H(x) P{γ_t >x, δ_t >y}= 1

µ Z ∞

x+y

(1−F(z))dz

Size biased distributions

f_i(t) = tⁱf(t) E Xⁱ The limiting distribution ogβ(t)

Delayed Renewal Process

Distribution ofX₁different

(6)

Stationary Renewal Process

Delayed renewal distribution where P{X₁≤x}=G_s(x) =µ⁻¹Rx

0(1−F(y))dy M_S(t) = t

µ Prob{γ_t ≤x} = G_s(x)

Additional Reading

S. Karlin, H. M. Taylor: “A First Course in Stochastic Processes” Chapter 5 pp.167-228

William Feller: “An introduction to probability theory and its applications. Vol. II.” Chapter XI pp. 346-371

Ronald W. Wolff: “Stochastic Modeling and the Theory of Queues” Chapter 2 52-130

D. R. Cox: “Renewal Processes”

Søren Asmussen: “Applied Probability and Queues” Chapter V pp.138-168

Darryl Daley and Vere-Jones: “An Introduction to the Theory of Point Processes” Chapter 4 pp. 66-110

Discrete Renewal Theory (7.6)

P{X =k}=p_k

M(n) =

n

X

k=0

p_k[1+M(n−k)]

= F(n) +

n

X

k=0

p_kM(n−k) A renewal equation. In general

v_n=b_n+

n

X

k=0

p_kv_n−k

The solution is unique, which we can see by solving recursively v₀ = b₀

1−p₀ v₁ = b₁+p₁v₀

1−p₀

Discrete Renewal Theory (7.6) (cont.)

Letunbe the renewal density (p₀=0) i.e. the probability of having an event at timen

u_n=δ_n+

n

X

k=0

p_ku_n−k

Lemma

7.1 Page 381 If{v_n}satisifiesv_n=b_n+Pn

k=0p_kv_n−k andu_n satisfiesu_n=δ_n+Pn

k=0p_ku_n−k then v_n=

n

X

k=0

b_n−ku_k

(7)

The Discrete Renewal Theorem

Theorem

7.1 Page 383 Suppose that 0<p₁<1 and that{u_n}and{v_n} are the solutions to the renewal equations

vn=bn+Pn

k=0p_kvn−k andun=δ_n+Pn

k=0p_kun−k, respectively. Then

(a) lim_n→∞un= P∞¹ k=0kpk

(b) ifP∞

k=0|b_k|<∞thenlimn→∞v_n=

P∞ k=0bk

P∞ k=0kp_k