Page 476 - A First Course In Stochastic Models

G. THE ROOT-FINDING PROBLEM 471

∞

numbers λ and D are positive constants such that λDβ/c < 1 with β = j=1 jβ j .
X
This root-finding problem arises in the analysis of the multi-server M /D/c queue
with batch arrivals. The equation (G.1) has c roots inside or on the unit circle. The
proof is not given here, but is standard in complex analysis and uses the so-called
Rouch´ e theorem; see for example Chaudry and Templeton (1983). Moreover, all
the c roots of (G.1) are distinct. This follows from the following general result in
Dukhovny (1994): if K(z) is the generating function of a non-negative, integer-
! !
′
′
′
valued random variable such that K (1) < c and zK (z) ≤ K (1) |K(z)| for
!
!
c
|z| ≤ 1, then all the roots of the equation z = K(z) in the region |z| ≤ 1 are
distinct. Apply this result with K(z) = e −λD{1−β(z)} and note that K(z) is the
generating function of the total number of arrivals in a compound Poisson arrival
process; see Section 1.2.
To obtain the roots of (G.1) it is not recommended to directly apply New-
ton–Raphson iteration to (G.1). In this procedure numerical difficulties arise when
roots are close together. This difficulty can be circumvented by a simple idea. The
key to the numerical solution of equation (G.1) is the observation that it can be
written as
c λD{1−β(z)}
z e = e 2πik (G.2)
where k is any integer. The next step is to use logarithms. The general logarithmic
function of a complex variable is defined as the inverse of the exponential function
z
and is therefore a many-valued function (as a consequence of e z+2πi = e ). It
suffices to consider the principal branch of the logarithmic function. This principal
branch is denoted by ln(z) and adds to each complex number z = 0 the unique
complex number w in the infinite strip −π < Im(w) ≤ π such that e w = z. The
principal branch of the logarithmic function of a complex variable can be expressed
in terms of elementary functions by

ln(z) = ln(r) + iθ
using the representation z = re iθ with r = |z| and −π < θ ≤ π. Since e ln(z) = z
for any z = 0, we can write (G.2) as
e c ln(z)+λD{1−β(z)} = e 2πik

with k is any integer. This suggests we should consider the equation
c ln(z) + λD{1 − β(z)} = 2πik (G.3)
where k is any integer. If for fixed k the equation (G.3) has a solution z k , then
this solution also satisfies (G.2) and so z k is a solution of (G.1). The question is
to find the values of k for which the equation (G.3) has a solution in the region
|z| ≤ 1. It turns out that the c distinct solutions of (G.1) are obtained by solving
(G.3) for the c consecutive values of k satisfying −π < 2πk/c ≤ π. These values
of k are k = −⌊(c−1)/2⌋, . . . , ⌊c/2⌋, where ⌊a⌋ is the largest integer smaller than
or equal to a. In solving (G.3) for these values of k, we can halve the amount of
computational work by letting k run only from 0 to ⌊c/2⌋. To see this, note that the