Page 367 - A First Course In Stochastic Models

362 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

from a state in the set {k +1, k +2, . . . } to a state outside this set during one cycle
equals the number of upcrossings from a state outside the set {k + 1, k + 2, . . . } to
a state in this set during one cycle. Thus relation (9.2.5) generalizes to

k

E(N k ) = E(T i )λ β s , k = 0, 1, . . . .
i=0 s>k−i
The remainder of the proof is analogous to the proof of Theorem 9.2.1.

The recursion scheme (9.3.2) is not as easy to apply as the recursion scheme
(9.2.1). The reason is that the computation of the constants a n is quite burden-
some. In general, numerical integration must be used, where each function eval-
uation in the integration procedure requires an application of Adelson’s recursion
scheme for the computation of the compound Poisson probabilities r n (t), n ≥ 0;
see Section 1.2.
The best general-purpose approach for the computation of the state probabilities
is the discrete FFT method. An explicit expression for the generating function

∞
j
P (z) = p j z , |z| ≤ 1
j=0
can be given. It is a matter of tedious algebra to derive from (9.3.2) that

1 − λα(z){1 − G(z)}
P (z) = (1 − ρ) , (9.3.3)
1 − λα(z){1 − G(z)}/(1 − z)
where
∞ ∞
j −λ{1−G(z)}t
G(z) = β j z and α(z) = e (1 − B(t)) dt.
0
j=1
The derivation uses that e −λ{1−G(z)}t is the generating function of the compound
Poisson probabilities r n (t); see Theorem 1.2.1. Moreover, the derivation uses that
the generating function of the convolution of two discrete probability distributions
is the product of the generating functions of the two probability distributions. The
other details of the derivation of (9.3.3) are left to the reader. For constant and
phase-type services, no numerical integration is required to evaluate the function
α(z) in the discrete FFT method.

Asymptotic expansion
The state probabilities allow for an asymptotic expansion when it is assumed that
the batch-size distribution and the service-time distribution are not heavy-tailed.
Let us make the following assumption.