Suppose we have phenomena which take place at discrete instants of time, separated by
random waiting or interarrival times. These may be arrivals of customers in a store,
of noise pulses on a communications line, vehicles passing a position on a road, the
failures of a system, etc. We refer to these occurrences as arrivals and
designate the times of occurrence as arrival times. A stream of arrivals may be described in three equivalent ways.
- Arrival times: {Sn:0≤n}{Sn:0≤n}, with 0=S0<S1<⋯a.s.0=S0<S1<⋯a.s. (basic sequence)
- Interarrival times: {Wi:1≤i}{Wi:1≤i}, with each Wi>0a.s.Wi>0a.s. (incremental sequence)
The strict inequalities imply that with probability one there are no simultaneous arrivals.
The relations between the two sequences are simply
S
0
=
0
,
S
n
=
∑
i
=
1
n
W
i
and
W
n
=
S
n
-
S
n
-
1
for
all
n
≥
1
S
0
=
0
,
S
n
=
∑
i
=
1
n
W
i
and
W
n
=
S
n
-
S
n
-
1
for
all
n
≥
1
(34)The formulation indicates the essential equivalence of the problem with that of the
compound demand. The notation and terminology are changed to correspond to that
customarily used in the treatment of arrival and counting processes.
The stream of arrivals may be described in a third way.
- Counting processes: Nt=N(t)Nt=N(t) is the number of arrivals in time period
(0,t](0,t]. It should be clear that this is a random quantity for each nonnegative
t. For a given t,ωt,ω the value is N(t,ω)N(t,ω). Such a family of random
variables constitutes a random process. In this
case the random process is a counting process.
We thus have three equivalent descriptions for the stream of arrivals.
{
S
n
:
0
≤
n
}
{
W
n
:
1
≤
n
}
{
N
t
:
0
≤
t
}
{
S
n
:
0
≤
n
}
{
W
n
:
1
≤
n
}
{
N
t
:
0
≤
t
}
(35)Several properties of the counting process N should be noted:
- N(t+h)-N(t)N(t+h)-N(t) counts the arrivals in the interval (t,t+h](t,t+h], h>0h>0,
so that N(t+h)≥N(t)N(t+h)≥N(t) for h>0h>0.
- N0=0N0=0 and for t>0t>0 we have
Nt=∑i=1∞I(0,t](Si)=max{n:Sn≤t}=min{n:Sn+1>t}Nt=∑i=1∞I(0,t](Si)=max{n:Sn≤t}=min{n:Sn+1>t}
(36) - For any given ω, N(·,ω)N(·,ω) is a nondecreasing, right-continuous,
integer-valued function defined on [0,∞)[0,∞), with N(0,ω)=0N(0,ω)=0.
The essential relationships between the three ways of describing the stream of arrivals
is displayed in
W
n
=
S
n
-
S
n
-
1
,
{
N
t
≥
n
}
=
{
S
n
≤
t
}
,
{
N
t
=
n
}
=
{
S
n
≤
t
<
S
n
+
1
}
W
n
=
S
n
-
S
n
-
1
,
{
N
t
≥
n
}
=
{
S
n
≤
t
}
,
{
N
t
=
n
}
=
{
S
n
≤
t
<
S
n
+
1
}
(37)This imples
P
(
N
t
=
n
)
=
P
(
S
n
≤
t
)
-
P
(
S
n
+
1
≤
t
)
=
P
(
S
n
+
1
>
t
)
-
P
(
S
n
>
t
)
P
(
N
t
=
n
)
=
P
(
S
n
≤
t
)
-
P
(
S
n
+
1
≤
t
)
=
P
(
S
n
+
1
>
t
)
-
P
(
S
n
>
t
)
(38)Although there are many possibilities for the interarrival time distributions, we assume
{
W
i
:
1
≤
i
}
is
iid,
with
W
i
>
0
a
.
s
.
{
W
i
:
1
≤
i
}
is
iid,
with
W
i
>
0
a
.
s
.
(39)Under such assumptions, the counting process is often referred to as a renewal
process and the interrarival times are called renewal times. In the literature
on renewal processes, it is common for the random variable to count an arrival at
t=0t=0. This requires an adjustment of the expressions relating Nt and the
Si. We use the convention above.
Exponential iid interarrival times
The case of exponential interarrival times is natural in many applications and
leads to important mathematical results. We utilize the following
propositions about the arrival times Sn, the interarrival times Wi, and the
counting process N.
- If {Wi:1≤i}{Wi:1≤i} is iid exponential (λ)(λ), then Sn∼Sn∼
gamma (n,λ)(n,λ) for all n≥1n≥1.
This is worked out in the unit on TRANSFORM METHODS, in the discussion
of the connection between the
gamma distribution and the exponential distribution.
- Sn∼Sn∼ gamma (n,λ)(n,λ) for all n≥1n≥1, and S0=0S0=0,
iff Nt∼Nt∼ Poisson (λt)(λt) for all t>0t>0.
This follows the result in the unit DISTRIBUTION APPROXI9MATIONS on
the relationship between the Poisson and gamma
distributions, along with the fact that {Nt≥n}={Sn≤t}{Nt≥n}={Sn≤t}.
Remark. The counting process is a Poisson process in the sense that Nt∼Nt∼
Poisson (λt)(λt) for all t>0t>0. More advanced treatments
show that the process has independent, stationary increments. That is
- N(t+h)-N(t)=N(h)N(t+h)-N(t)=N(h) for all t,h>0t,h>0, and
- For t1<t2≤t3<t4≤⋯≤tm-1<tmt1<t2≤t3<t4≤⋯≤tm-1<tm, the class
{N(t2)-N(N1),N(t4)-N(t3),⋯,N(tm)-N(tm-1)}{N(t2)-N(N1),N(t4)-N(t3),⋯,N(tm)-N(tm-1)} is independent.
In words, the number of arrivals in any time interval depends upon the length of the
interval and not its location in time, and the numbers of arrivals in nonoverlapping
time intervals are independent.
Emergency calls arrive at a police switchboard with interarrival times (in hours)
exponential (15). Thus, the average interarrival time is 1/15 hour (four minutes).
What is the probability the number of calls in an eight hour shift is no more than
100, 120, 140?
p = 1 - cpoisson(8*15,[101 121 141])
p = 0.0347 0.5243 0.9669
We develop next a simple computational result for arrival processes for which Sn∼Sn∼ gamma (n,λ)(n,λ).
Suppose the arrival times Sn∼Sn∼ gamma (n,λ)(n,λ) and g is such that
∫
0
∞
|
g
|
<
∞
and
E
∑
n
=
1
∞
|
g
(
S
n
)
|
<
∞
∫
0
∞
|
g
|
<
∞
and
E
∑
n
=
1
∞
|
g
(
S
n
)
|
<
∞
(40)Then
E
∑
n
=
1
∞
g
(
S
n
)
=
λ
∫
0
∞
g
E
∑
n
=
1
∞
g
(
S
n
)
=
λ
∫
0
∞
g
(41)VERIFICATION
We use the countable sums property (E8b) for expectation and the corresponding property
for integrals to assert
E
∑
n
=
1
∞
g
(
S
n
)
=
∑
n
=
1
∞
E
[
g
(
S
n
)
]
=
∑
n
=
1
∞
∫
0
∞
g
(
t
)
f
n
(
t
)
d
t
where
f
n
(
t
)
=
λ
e
-
λ
t
(
λ
t
)
n
-
1
(
n
-
1
)
!
E
∑
n
=
1
∞
g
(
S
n
)
=
∑
n
=
1
∞
E
[
g
(
S
n
)
]
=
∑
n
=
1
∞
∫
0
∞
g
(
t
)
f
n
(
t
)
d
t
where
f
n
(
t
)
=
λ
e
-
λ
t
(
λ
t
)
n
-
1
(
n
-
1
)
!
(42)We may apply (E8b) to assert
∑
n
=
1
∞
∫
0
∞
g
f
n
=
∫
0
∞
g
∑
n
=
1
∞
f
n
∑
n
=
1
∞
∫
0
∞
g
f
n
=
∫
0
∞
g
∑
n
=
1
∞
f
n
(43)Since
∑
n
=
1
∞
f
n
(
t
)
=
λ
e
-
λ
t
∑
n
=
1
∞
(
λ
t
)
n
-
1
(
n
-
1
)
!
=
λ
e
-
λ
t
e
λ
t
=
λ
∑
n
=
1
∞
f
n
(
t
)
=
λ
e
-
λ
t
∑
n
=
1
∞
(
λ
t
)
n
-
1
(
n
-
1
)
!
=
λ
e
-
λ
t
e
λ
t
=
λ
(44)the proposition is established.
A critical unit in a production system has life duration exponential (λ)(λ). Upon failure the unit is replaced immediately by a similar unit. Units fail independently.
Cost of replacement of a unit is c dollars. If money is discounted at a rate α,
then a dollar spent t units of time in the future has a current value e-αte-αt. If Sn is the time of replacement of the nth unit, then Sn∼Sn∼ gamma (n,λ)(n,λ)
and the present value of all future replacements is
C
=
∑
n
=
1
∞
c
e
-
α
S
n
C
=
∑
n
=
1
∞
c
e
-
α
S
n
(45)The expected replacement cost is
E
[
C
]
=
E
∑
n
=
1
∞
g
(
S
n
)
where
g
(
t
)
=
c
e
-
α
t
E
[
C
]
=
E
∑
n
=
1
∞
g
(
S
n
)
where
g
(
t
)
=
c
e
-
α
t
(46)Hence
E
[
C
]
=
λ
∫
0
∞
c
e
-
α
t
d
t
=
λ
c
α
E
[
C
]
=
λ
∫
0
∞
c
e
-
α
t
d
t
=
λ
c
α
(47)Suppose unit replacement cost c=1200c=1200, average time (in years) to failure 1/λ=1/41/λ=1/4, and the discount rate per year α=0.08α=0.08 (eight percent). Then
E
[
C
]
=
1200
·
4
0
.
08
=
60
,
000
E
[
C
]
=
1200
·
4
0
.
08
=
60
,
000
(48)Suppose the cost of the nth replacement in Example 11 is a random quantity Cn, with
{Cn,Sn}{Cn,Sn} independent and E[Cn]=cE[Cn]=c, invariant with n. Then
E
[
C
]
=
E
∑
n
=
1
∞
C
n
e
-
α
S
n
=
∑
n
=
1
∞
E
[
C
n
]
E
[
e
-
α
S
n
]
=
∑
n
=
1
∞
c
E
[
e
-
α
S
n
]
=
λ
c
α
E
[
C
]
=
E
∑
n
=
1
∞
C
n
e
-
α
S
n
=
∑
n
=
1
∞
E
[
C
n
]
E
[
e
-
α
S
n
]
=
∑
n
=
1
∞
c
E
[
e
-
α
S
n
]
=
λ
c
α
(49)The analysis to this point assumes the process will continue endlessly into the future. Often,
it is desirable to plan for a specific, finite period. The result of Example 10 may be
modified easily to account for a finite period, often referred to as a finite horizon.
Under the conditions assumed in Example 10, above, let Nt be the counting random
variable for arrivals in the interval (0,t](0,t].
If
Z
t
=
∑
n
=
1
N
t
g
(
S
n
)
,
then
E
[
Z
t
]
=
λ
∫
0
t
g
(
u
)
d
u
If
Z
t
=
∑
n
=
1
N
t
g
(
S
n
)
,
then
E
[
Z
t
]
=
λ
∫
0
t
g
(
u
)
d
u
(50)VERIFICATION
Since Nt≥nNt≥n iff Sn≤tSn≤t, ∑n=1Ntg(Sn)=∑n=0∞I(0,t](Sn)g(Sn)∑n=1Ntg(Sn)=∑n=0∞I(0,t](Sn)g(Sn). In the result of Example 10,
replace g by I(0,t]gI(0,t]g and note that
∫
0
∞
I
(
0
,
t
]
(
u
)
g
(
u
)
d
u
=
∫
0
t
g
(
u
)
d
u
∫
0
∞
I
(
0
,
t
]
(
u
)
g
(
u
)
d
u
=
∫
0
t
g
(
u
)
d
u
(51)Under the conditions of Example 11, consider the replacement costs over a two-year
period.
SOLUTION
E
[
C
]
=
λ
c
∫
0
t
e
-
α
u
d
u
=
λ
c
α
(
1
-
e
-
α
t
)
E
[
C
]
=
λ
c
∫
0
t
e
-
α
u
d
u
=
λ
c
α
(
1
-
e
-
α
t
)
(52)Thus, the expected cost for the infinite horizon λc/αλc/α is reduced by the
factor 1-e-αt1-e-αt. For t=2t=2 and the numbers in Example 11, the
reduction factor is 1-e-0.16=0.14791-e-0.16=0.1479 to give
E[C]=60000·0.1479=8,871.37E[C]=60000·0.1479=8,871.37.
In the important special case that g(u)=ce-αug(u)=ce-αu, the expression for
E∑n=1∞g(Sn)E∑n=1∞g(Sn) may be put into a form which
does not require the interarrival times to be exponential.
Suppose S0=0S0=0 and Sn=∑i=1nWiSn=∑i=1nWi, where {Wi:1≤i}{Wi:1≤i} is iid.
Let {Vn:1≤n}{Vn:1≤n} be a class such that each E[Vn]=cE[Vn]=c and each pair {Vn,Sn}{Vn,Sn}
is independent. Then for α>0α>0
E
[
C
]
=
E
∑
n
=
1
∞
V
n
e
-
α
S
n
=
c
·
M
W
(
-
α
)
1
-
M
W
(
-
α
)
E
[
C
]
=
E
∑
n
=
1
∞
V
n
e
-
α
S
n
=
c
·
M
W
(
-
α
)
1
-
M
W
(
-
α
)
(53)where MW is the moment generating function for W.
DERIVATION
First we note that
E
[
V
n
e
-
α
S
n
]
=
c
M
S
n
(
-
α
)
=
c
M
W
n
(
-
α
)
E
[
V
n
e
-
α
S
n
]
=
c
M
S
n
(
-
α
)
=
c
M
W
n
(
-
α
)
(54)Hence, by properties of expectation and the geometric series
E
[
C
]
=
c
∑
n
=
1
∞
M
W
n
(
-
α
)
=
M
W
(
-
α
)
1
-
M
W
(
-
α
)
,
provided
|
M
W
(
-
α
)
|
<
1
E
[
C
]
=
c
∑
n
=
1
∞
M
W
n
(
-
α
)
=
M
W
(
-
α
)
1
-
M
W
(
-
α
)
,
provided
|
M
W
(
-
α
)
|
<
1
(55)Since α>0α>0 and W>0W>0, we have 0<e-αW<10<e-αW<1, so that
MW(-α)=E[e-αW]<1MW(-α)=E[e-αW]<1.
Suppose each Wi∼Wi∼ uniform (a,b)(a,b). Then (see Appendix C),
M
W
(
-
α
)
=
e
-
a
α
-
e
-
b
α
α
(
b
-
a
)
so
that
E
[
C
]
=
c
·
e
-
a
α
-
e
-
b
α
α
(
b
-
a
)
-
[
e
-
a
α
-
e
-
b
α
]
M
W
(
-
α
)
=
e
-
a
α
-
e
-
b
α
α
(
b
-
a
)
so
that
E
[
C
]
=
c
·
e
-
a
α
-
e
-
b
α
α
(
b
-
a
)
-
[
e
-
a
α
-
e
-
b
α
]
(56)Let a=1a=1, b=5b=5, c=100c=100 and α=0.08α=0.08. Then,
a = 1;
b = 5;
c = 100;
A = 0.08;
MW = (exp(-a*A) - exp(-b*A))/(A*(b - a))
MW = 0.7900
EC = c*MW/(1 - MW)
EC = 376.1643
Catalogue of Useful Matlab Files
