Page 316 - A First Course In Stochastic Models

THE RENEWAL FUNCTION 311

In Section 2.1.1 we have already seen that the renewal function can be directly
computed from the series representation (8.1.1) when the interoccurrence times
have a gamma distribution. If the interoccurrence times have a Coxian-2 distribution
an explicit expression can be given for the renewal function; see Exercise 8.1. In
general the renewal function M(x) can be computed by numerical inversion of its
∞ −sx
∗
Laplace transform. The Laplace transform M (s) = e M(x) dx is given by
0
f (s)
∗
∗
M (s) = ,
s[1 − f (s)]
∗
∞ −sx
∗
where f (s) = e f (x) dx denotes the Laplace transform of the probabil-
0
ity density of the interoccurrence times; see Appendix E. How to proceed with
numerical Laplace inversion is discussed in Appendix F. In this appendix it is
also discussed how to proceed when the Laplace transform f (s) is analytically
∗
intractable.
Next we discuss a simple but useful discretization method. The renewal equation
(8.1.3) for M(t) is a special case of an integral equation which is known in numer-
ical analysis as a Volterra integral equation of the second kind. Many numerical
methods have been proposed to solve such equations. Unfortunately, these meth-
ods typically suffer from the accumulation of round-off errors when t gets larger.
However, using basic concepts from the theory of Riemann–Stieltjes integration, a
simple and direct solution method with good convergence properties can be given
for the renewal equation (8.1.3). This method discretizes the time and computes
recursively the renewal function on a grid of points. For fixed t > 0, let [0, t] be
partitioned according to 0 = t 0 < t 1 , < . . . < t n = t, where t i = ih for a given
grid size h > 0. Put for abbreviation

M i = M(ih), F i = F((i − 0.5)h) and A i = F(ih), 1 ≤ i ≤ n.

The recursion scheme for computing the M i is as follows:
 
i−1
1
M i =  A i + (M j − M j−1 )F i−j+1 − M i−1 F 1 , 1 ≤ i ≤ n,

1 − F 1
j=1
starting with M 0 = 0. This recursion scheme is a minor modification of the Rie-
mann–Stieltjes method proposed in Xie (1989) (the original method uses F i instead
of A i ). The recursion scheme is easy to program and gives surprisingly accurate
results. It is remarkable how well the recursion scheme is able to resist the accu-
mulation of round-off errors as t gets larger. How to choose the grid size h > 0
depends not only on the desired accuracy in the answers, but also on the shape of
the distribution function F(x) and the length of the interval [0, t]. The usual way
to find out whether the answers are accurate enough is to do the computations for
both a grid size h and a grid size h/2. In many cases of practical interest a four-
digit accuracy is obtained for a grid size h in the range 0.05 − 0.01. In Table 8.1.1
some results are given for the renewal function of the Weibull distribution, where