**Renewal Processes**

Bo Friis Nielsen^{1}

1DTU Informatics

02407 Stochastic Processes 8, October 27 2020

**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

**Distribution of** N (t )

ForX_{i} ∼exp(λ)P(N(t) =n) = ^{(λt)}_{n!}^{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_{n}is an “Erlang-type” PH variable

**Renewal function**

X_{i} ∼exp(λ)thenM(t) =E(N(t)) =λtProbability 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_{i}dt+o(dt)
P(J(t) =i) = αe^{At}**1**_{i}

P(N(t+dt)−N(t) =1) = αe^{At}**sdt**+o(dt)
M(t) =E(N(t) =

Z t 0

αe^{Au}**sdu**=α
Z t

0

e** ^{Au}**dus
The generator

**A**is singular (A1=

**0,**πA=

**0)**

**Calculation of** R

_{t}

0

## e

^{Au}**du**

First we note that**1π**−**A**is non-singular

Z t 0

e** ^{Au}**du =
Z t

0

(1π−**A)**^{−1}(1π−**A)**e** ^{Au}**du

= (1π−**A)**^{−1}
Z t

0

**1πe**** ^{Au}**du−
Z t

0

**Ae**** ^{Au}**du

Z t 0

**1πe**** ^{Au}**du =
Z t

0

**1π**

∞

X

n=0

(Au)^{n}
n! du=

Z t 0

**1**

∞

X

n=0

π(Au)^{n}
n! du

= Z t

0

**1πdu**=t1π

Z t 0

**Ae**** ^{Au}**du = e

**−**

^{At}**I**

**Back to** M (t )

We have(1π−**A)1**=1 andπ(1π−**A) =**π, so
M(t) = α(1π−**A)**^{−1}h

t1π−

e** ^{At}** −

**I**i

**s**

= πst+α(1π−**A)**^{−1}**s**−α(1π−**A)**^{−1}e^{At}**s**
We haveα(1π−**A)**^{−1}e^{At}**s**→α(1π−**A)**^{−1}**1πs**=πs

**Renewal Processes**

F(x) = P{X ≤x}
W_{n} = X_{1}+· · ·+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} → _{µ}^{1}
E W_{N(t)+1}

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

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

0Fn−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)→ _{µ}^{1}R∞
0 a(t)dt
Limiting distribution of residual life time
limt→∞P{γ_{t} ≤x}= ^{1}_{µ}Rx

0(1−F(u))du

Limiting distribution of joint distribution of age and residual life
timelimt→∞P{γ_{t} ≥x, δ_{t} ≥y}= ^{1}_{µ}R∞

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

lim_{t}→∞P{β_{t} ≤x}=

Rx 0tdF(t)

µ

**Continuous Renewal Theory (7.6)**

P{W_{n} ≤x} = F_{n}(x) with
F_{n}(x) =

Z x 0

F_{n−1}(x−y)dF(y)
The expression forFn(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)

**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}

_{)+1}

## ]

E[W_{N(t}_{)+1}] = E

N(t)+1

X

j=1

X_{j}

=E[X_{1}] +E

N(t)+1

X

j=1

X_{j}

= µ+

∞

X

j=2

E

X_{j}**1(X**_{1}+· · ·+Xj−1≤t)
X_{j} and**1(X**_{1}+· · ·+X_{j−1}≤t)are independent

=µ+

∞

X

j=2

E
X_{j}

E

**1(X**_{1}+· · ·+Xj−1≤t)

=µ+µ

∞

X

j=2

Fj−1(t)
E[W_{N(t)+1}] = exp[X_{1}]E[N(t) +1] =µ(M(t) +1)

**Poisson Process as a Renewal Process**

F_{n}(x) =

∞

X

i=n

(λx)^{n}

n! e^{−λx} =1−

n

X

i=0

(λx)^{n}
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}−µ^{2}
2µ^{2}
Example with gamma distribution Page 367

**Asymptotic Distribution of** N (t )

WhenE[X_{k}] =µandVar[X_{k}] =σ^{2}both finite

tlim→∞P

(N(t)−t/µ
ptσ^{2}/µ^{3} ≤x

)

= 1

√2π Z x

−∞

e^{−y}^{2}^{/2}dy

**Limiting Distribution of Age and Excess Life**

t→∞lim 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^{i}f(t)
E X^{i}
The limiting distribution ogβ(t)

**Delayed Renewal Process**

Distribution ofX_{1}different

**Stationary Renewal Process**

Delayed renewal distribution where
P{X_{1}≤x}=Gs(x) =µ^{−1}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_{k}M(n−k)
A renewal equation. In general

v_{n}=b_{n}+

n

X

k=0

p_{k}v_{n−k}

The solution is unique, which we can see by solving recursively
v_{0} = b_{0}

1−p_{0}
v_{1} = b_{1}+p_{1}v_{0}

1−p_{0}

**Discrete Renewal Theory (7.6) (cont.)**

Letunbe the renewal density (p_{0}=0) i.e. the probability of
having an event at timen

u_{n}=δ_{n}+

n

X

k=0

p_{k}u_{n−k}

**Lemma**

7.1 Page 381 If{v_{n}}satisifiesvn=bn+Pn

k=0p_{k}vn−k andun

satisfiesun=δn+Pn

k=0p_{k}un−k then
v_{n}=

n

X

k=0

b_{n−k}u_{k}

**The Discrete Renewal Theorem**

**Theorem**

7.1 Page 383 Suppose that 0<p_{1}<1 and that{u_{n}}and{v_{n}}
are the solutions to the renewal equations

v_{n}=b_{n}+Pn

k=0p_{k}v_{n−k} andu_{n}=δn+Pn

k=0p_{k}u_{n−k},
respectively. Then

**(a)** limn→∞un= ^{P}^{∞}^{1}

k=0kpk

**(b)** ifP∞

k=0|b_{k}|<∞thenlimn→∞vn =

P∞ k=0bk

P∞ k=0kpk