Page 36 - A First Course In Stochastic Models

MARKOV MODULATED BATCH POISSON PROCESSES 27

differential equations, we obtain
∗
∗
P (z, t) = e D(z)t P (z, 0) (1.4.4)
i i
∗
∗
where P (z, t) is the ith row of the matrix P (z, t). Since P (z, 0) equals the ith
∗
i i
unit vector e i = (0, . . . , 1, . . . , 0), it next follows that P (z, t) = e D(z)t , as was
∗
to be proved.
In general it is a formidable task to obtain the numerical values of the prob-
abilities P ij (k, t) from the expression (1.4.4), particularly when m is large. The
∗
numerical approach of the discrete FFT method is only practically feasible when
the computation of the matrix e D(z)t is not too burdensome. Numerous algorithms
for the computation of the matrix exponential e At have been proposed, but they do
not always provide high accuracy. The computational work is simplified when the
m×m matrix A has m different eigenvalues µ 1 , . . . , µ m (say), as is often the case
in applications. It is well known from linear algebra that the matrix A can then be
diagonalized as
A = SχS −1 ,

where the diagonal matrix χ is given by χ = diag(µ 1 , . . . , µ m ) and the column
vectors of the matrix S are the linearly independent eigenvectors associated with
n −1
n
the eigenvalues µ 1 , . . . , µ m . Moreover, by A = Sχ S , it holds that
e At = S diag(e µ 1 t , . . . , e µ m t )S −1 .
Fast codes for the computation of eigenvalues and eigenvectors of a (complex)
matrix are widely available.
To conclude this section, it is remarked that the matrix D(z) in the matrix expo-
nential e D(z)t has a very simple form for the important case of single arrivals (i.e.
(1)
a = 1 for i = 1, . . . , m). It then follows from (1.4.1) and (1.4.2) that
i
D(z) = Q − + z, |z| ≤ 1.
The arrival process with single arrivals is called the Markov modulated Poisson
process. A special case of this process is the switched Poisson process which has
only two arrival rates (m = 2). This model is frequently used in applications. In
the special case of the switched Poisson process, the following explicit expressions
can be given for the generating functions P (z, t):
∗
ij
1
∗ −r 1 (z)t
P (z, t) = {r 2 (z) − (λ i (1 − z) + ω i )}e
ii
r 2 (z) − r 1 (z)

− {r 1 (z) − (λ i (1 − z) + ω i )}e −r 2 (z)t , i = 1, 2,
∗ It is also possible to formulate a direct probabilistic algorithm for the computation of the probabilities
P ij (k, t). This algorithm is based on the uniformization method for continuous-time Markov chains; see
Section 4.5.