Proof. The proof of this proposition can be found in [3] pages 306-310.
If T is an m×mmatrix, the corresponding matrix-exponential distribution is said to be of order m.If we write L(s) = p(s)q(s) thend= deg(q) is the degree of the matrix-exponential distribution.
Note that Proposition 3.2 is of great importance as it gives a method to find an order-d representation of a matrix-exponential density that has a Laplace transform of degreed.
3.2 Examples of matrix-exponential distributions
In this section we will give three examples of matrix-exponential distributions.
Our main aim with these examples is to illustrate that the class of matrix-exponential distributions is strictly larger than the class of phase-type distri-butions and that it is sometimes more convenient to use a matrix-exponential representation for a distribution because it can be represented with a lower or-der representation (i.e. the matrix T has a lower dimension).
To be able to say whether or not a distribution is of phase-type we use the follow-ing Characterization Theorem for phase-type distributions by C.A. O’Cinneide [14].
Theorem 3.3 (Characterization of phase-type distributions) A distribu-tion on [0,∞) with rational Laplace-Stieltjes transform is of phase-type if and only if it is either the point mass at zero, or (a) it has a continuous positive density on the positive reals, and (b) its Laplace-Stieltjes transform has a unique pole of maximal real part.
The proof of this theorem is far from simple and can be found in [14]. Condition (a) of the characterization, stating that a phase-type density is always positive on (0,∞),has already been addressed in Chapter 2 on page 20. Condition (b) implies that a distribution can only be of phase-type if the sinusoidal effects in the tail behavior of the density of a phase-type distribution (which cause two conjugate complex poles in the Laplace-Stieltjes transform) decay at a faster exponential rate than the dominant effects.
The first example is of a matrix-exponential distribution that does not satisfy Condition (a) and (b) of Theorem 3.3, and hence is not of phase-type.
Example 3.1 A distribution that is genuinely matrix-exponential (hence not of phase-type) is represented by the following density:
f(t) =Ke−λt(1−cos(ωπt)), t≥0 forλandωreal coefficients andK a scaling coefficient given by
K= λ(λ2+π2ω2) π2ω2 .
Figure 3.1 shows this density forλ= 1 andω= 2, which impliesK= 1 +4π12. This density is zero whenever t equals 2nω for n ∈ N and therefore violates Condition (a) of Theorem 3.3. By rewriting this density using the identity cosx= eix+e2−ix we find a matrix-exponential representation for this density:
f(t) = Ke−λt(1−cos(ωπt))
3.2 Examples of matrix-exponential distributions 27
1 2 3 4
t 0.2
0.4 0.6 0.8 1.0 1.2 fHtL
Figure 3.1: Density plot of f(t) = (1 +4π12)e−t(1−cos(2πt)).
The Laplace transform of f(t) is given by L(s) = K
Z ∞ 0
e−ste−λx(1−cos(ωπt))dt
= Kπ2ω2
(s+λ)(s−iπω+λ)(s+iπω+λ)
= Kπ2ω2
s3+ 3λs2+ (π2ω2+ 3λ2)s+π2ω2λ+λ3. (3.3)
This is a rational expression in s which again shows that f(n) is a matrix-exponential density. The poles of the Laplace transform are−λ,−λ+iπω and
−λ−iπω which all have−λas real part. Hence this distribution violates also Condition (b) of the Characterization Theorem for phase-type distributions.
Now by using Proposition 3.2 and Formula (3.3) we find that another matrix-exponential representation forf(t) =αeT ttis given by
α = (Kπ2ω2,0,0),
T =
0 1 0
0 0 1
−π2ω2λ−λ3 −π2ω2−3λ2 −3λ
and
t=
0 0 1
.
1 2 3 4 5 t 0.2
0.4 0.6 0.8 1.0 1.2 1.4 gHtL
Figure 3.2: Density plot ofg(t) = 1+ 11 2+8π2
e−t 1 + 12cos(2πt) .
A slight change in this first example leads to a density that violates Condition (b) but not Condition (a) of Theorem 3.3 and hence is again matrix-exponential and not of phase-type.
Example 3.2 The distribution represented by the density g(t) = 1
1 + 2+8π1 2
e−t
1 +1
2cos(2πt)
, t≥0 is genuine matrix-exponential. Its Laplace transform is given by
L(t) = K
s+ 1+ K
4(s+ 1−2πi)+ K 4(s+ 1 + 2πi), whereK= 1+ 11
2+8π2
.
The poles of the Laplace transform are−1,−1 + 2πiand−1−2πihence there is no pole of maximum real part and Condition (b) of Theorem 3.3 is not satisfied.
We do haveg(n)>0 for allt≥0.Figure 3.2 shows a plot of this density.
In ‘Phase-Type Distributions and Invariant Polytopes’ by C.A. O’Cinneide, [15]
the author states the following theorem on the minimal order of a phase-type distribution.
Theorem 3.4 Let µ be a phase-type distribution with −λ1 for the pole of its transform of maximal real part, and with poles at −λ2±iθ,where θ >0.Then the ordern ofµsatisfies
θ
λ2−λ1 ≤cotπ n.
3.2 Examples of matrix-exponential distributions 29
Using the fact thattanx≥x, for0≤x≤ 12π,this implies that n≥ πθ
λ2−λ1
. (3.4)
Using this theorem we can give an example of a distribution that has a lower order when represented as a matrix-exponential density than when represented as a phase-type density.
Example 3.3 This is an elaboration of an example in [15] on page 524. The density
h(t) = 1
1 2+1−1
!
e−(1−)t+e−tcost
, t≥0 for 0< <1 has Laplace transform
L(s) = 2(−1 +)(−3 +−4s+s−2s2) (−3 +)(−1 +−s)(2 + 2s+s2).
The denominator ofL(s) is of degree three and henceh(t) has a matrix-exponential representation of order three, which can again be found by using Proposition 3.2. The poles of the Laplace transform are −1−i,−1 +iand −1 +.Thus by Theorem 3.4 and Inequality (3.4) we have for the ordermof the phase-type representation forh(t) that
m≥π .
Hence we have a phase-type density of degree three but with arbitrarily large order. Note that for= 0 this density is not of phase-type since it then doesn’t have a unique pole of maximum real part. Figure 3.3 shows the density plot of h(t) for= 0,7/9 and 1/2.
In this chapter we have shown that the class of matrix-exponential distributions is strictly larger than the class of phase-type distributions. We have seen that there are phase-type distributions that have a larger order than their degree.
In the next chapter we will explore the relation between matrix-geometric dis-tributions, which are the discrete analogous of matrix-exponential distributions and discrete phase-type distributions.
1 2 3 4 t 0.2
0.4 0.6 0.8 1.0 1.2 hHtL
Ε =12 Ε =79 Ε =0
Figure 3.3: Density plot ofh(t) for= 0,79 and 12
Chapter 4
Matrix-geometric distributions
This chapter is about the class of matrix-geometric distributions (MG). They are distributions on the non-negative integers with a density of the same form as discrete phase-type distributions,
f(n) =αTn−1t.
However, matrix-geometric distributions do not necessarily posses the proba-bilistic interpretation as the time until absorption in a discrete-time Markov chain. They can equivalently be defined as distributions with a rational proba-bility generating function.
The main question of this thesis, to be answered in this chapter, is how matrix-geometric distributions relate to discrete phase-type distributions. We will show that
DPH(MG
and that there is possible order reduction by taking the matrix-geometric re-presentation for a discrete phase-type distribution.
Matrix-geometric distributions are mentioned by Asmussen and O’Cinneide in [4] as the discrete equivalent of matrix-exponential distributions, but no explicit example of such a distribution is given. They are used by Akar in [1] to study the queue lengths and waiting times of a discrete time queueing system, but no explicit examples are given in this article either. Sengupta [17] shows a class of
distributions that are obviously in MG, but by the use of a transformation he shows that they are actually in DPH.
In Section 4.1 matrix-geometric distributions are defined. In Section 4.2 we show that there exist distributions that are genuinely matrix-geometric, hence not of discrete phase-type, by the use of the Characterization Theorem of dis-crete phase-type distributions stated by O’Cinneide in [14]. In Section 4.3 we will show that there exist phase-type distributions that have a lower degree, and hence lower order matrix-geometric representation, than the order of their discrete phase-type representation. Finally, in Section 4.4 we will revisit some properties of discrete phase-type distributions and show that they also hold for the class MG, by proving them analytically.
4.1 Definition
Definition 4.1 (Matrix-geometric distribution) A random variableXhas a matrix-geometric distribution if the density ofX is of the form
f(n) =αTn−1t, n∈N
where α and t are a row and column vector of length m and T is anm×m matrix with entries inC.
We have to make a note about the support of these distributions. Matrix-geometric distributions have support on the non-negative integers, and the matrix-geometric density is actually a mixture of the above density defined on n∈N and the point mass at zero. For convenience we will assume in this chapter thatf(0) = 0.
The following proposition shows that we can equivalently define matrix-geometric distributions as distributions that have a rational probability generating func-tion. It is the discrete equivalent of Proposition 3.2.
Proposition 4.2 The probability generating function of a matrix-geometric dis-tribution can be written as
H(z) = bnz+bn−1z2+. . .+b2zn−1+b1zn
1 +a1z+a2z2+. . .+an−1zn−1+anzn, (4.1) for some n ≥ 1 and constants a1, . . . , an, b1, . . . , bn in R. The corresponding density is given by
f(n) =αTn−1t
4.1 Definition 33
We call this the canonical formof the matrix-geometric density.
Proof. From Equation (2.9) and Proposition 3.2 we know that we have the following formula for the Laplace transform of a matrix-exponential distribution:
L(s) =α(sI−T)−1t= b1+b2s+b3s2+. . .+bnsn−1 sn+a1sn−1+. . .+an−1s+an
.
In Proposition 3.2 the corresponding vectorsαandtand a matrixT are given, using the coefficients of the Laplace transform.
The probability generating function of a matrix-geometric distribution is given by
H(z) =αz(I−zT)−1t.
This formula is equal to the matrix formula of the Laplace transform if s is replaced by 1/z, which leads to the following fractional form of the probability generating function:
The corresponding vectors α and t and a matrix T are hence the same as in Proposition 3.2 in Formula (3.2). To obtain the canonical form for a matrix-geometric density given in Formula (4.2) we take the transpose of α,t and T and rename the states to obtain α= (1,0, . . . ,0).
As in the continuous case, the order of a matrix-geometric distribution is said to bemifT is anm×mmatrix. If we writeH(z) =p(z)q(z), the degree of a matrix-geometric distribution is given by n = deg(p). It follows from Proposition 4.2 that for a matrix-geometric distribution we can always find a representation that has the same order as the degree of the distribution.
If a random variable X has a matrix-geometric distribution with parameters α, T andtwe write
X ∼MG (α, T,t).
Although the relationTe+t=edoes not necessarily holds, it is always possible to find a representation that does satisfies this relation. For a non-singular matrixM we can write for the densityf(n) ofX:
f(n) = αTn−1t
= αM M−1Tn−1M M−1t
= αM(M−1T M)n−1M−1t.
For this density we now want the relation
M−1T Me+M−1t=e
to hold, which can found to be true whenM satisfies the relation Me= (I−T)−1t.