Definition 4.1 A DPH is called acyclic DPH (ADPH) if its states can be ordered in such a way that matrix B is an upper triangular matrix.
By Definition 4.1, a generic ADPH of order n is characterized by NF = n2/2+3/2 n−1 free parameters (n · (n + 1)/2 in the upper triangular matrix B and n − 1 in the initial probability vector α).
Definition 4.1 implies that a state i can be directly connected to a state j only if j ≥ i. In an ADPH, each state is visited at most once before absorption. We define an absorbing path, or simply a path, the sequence of states visited from an initial state to the absorbing one. In an ADPH of order n, the number of paths is finite and is at most 2n− 1.
A path r of length ` ≤ n, is characterized by a set of indices, representing the states visited before absorption:
r = (x1, x2, . . . , x`) such that
1 ≤ xj ≤ n ∀j : 1 ≤ j ≤ ` xj< xj+1 ∀j : 1 ≤ j < ` bxj,xj+1> 0 ∀j : 1 ≤ j < ` bx`,n+1> 0
(4.13)
where the last two conditions mean that in a path any two subsequent indices represent states that must be connected by a direct arc (non-zero entry in the B matrix), and the last index represents a state that must be connected by a direct arc to the absorbing state (n + 1).
Assuming that the underlying DTMC starts in state with index x1, the path r in (4.13), occurs with probability:
P (r) = bx`,n+1
1 − bx`,x`
`−1Y
j=1
bxj,xj+1
1 − bxj,xj
(4.14)
and the generating function of the time to arrive to the absorbing state through path r is
F(z, r) = Y` j=1
(1 − bxj,xj)z
1 − bxj,xjz . (4.15)
Let Libe the set of all the paths starting from state i (i.e., for which x1= i). The generating function
of the time to absorption assuming the DTMC starts from state i is:
Fi(z) = X
r∈Li
P (r) F(z, r) (4.16)
where it is clear from (4.14) thatP
r∈LiP (r) = 1.
Corollary 4.1 The generating function of an ADPH is the mixture of the generating functions of its paths (see also [21]):
Example 4.2 Let us consider the ADPH in Figure 4.2, with representation:
α= [α1 α2] , B =
Figure 4.2: An example of ADPH.
Three different paths can be identified to reach the absorbing state. The paths are depicted in Figure 4.3 and have the following description:
• r1 is a path of length 1 starting from state 1. (4.14) and (4.15) applied to r1 provide:
P (r1) = b13
1 − b11 = 2
7 ; F(z, r1) = (1 − b11)z
1 − b11z = 0.7z
1 − 0.3z ; (4.19)
• r2 is a path of length 2 starting from state 1. (4.14) and (4.15) provide:
P (r2) = b12
• r3 is a path of length 1 starting from state 2. (4.14) and (4.15) provide:
P (r3) = b23
1 − b22 = 1 ; F(z, r3) = (1 − b22)z
1 − b22z = 0.4z
1 − 0.6z ; (4.22)
Figure 4.3: Possible paths of the ADPH of Figure 4.2.
From (4.15) and from Corollary 4.1, it follows that the generating function of the time to absorption does not depend on the particular order of the geometrically distributed sojourn times. Hence, we can reorder the eigenvalues (diagonal elements) of the matrix B into a decreasing sequence. The entries of this sequence will be denoted by qi, 1 ≤ i ≤ n and the sequence itself is q1 ≥ q2 ≥ . . . ≥ qn. For the sake of convenience, we define the symbols pi= (1 − qi) as well which represent the exit rate from state i. Since the sequence of the qi’s is in decreasing order, the sequence of the pi’s is in increasing order:
p1≤ p2≤ . . . ≤ pn.
Any path r can be described as a binary vector u = [ui] of length n defined over the ordered sequence of the qi’s. Each entry of the vector is equal to 1 if the corresponding eigenvalue qi is present in the path, otherwise the entry is equal to 0. Hence, any path r of length ` has ` ones in the vector u. With this representation any path is characterized by a unique number 1 ≤ #u ≤ 2n− 1 where #u denotes the number represented by the binary vector u.
Definition 4.2 A path r of length ` of an ADPH is called a basic path (basic series [21]) if it contains the ` fastest phases qn−`+1, . . . , qn−1, qn. The binary vector associated to a basic path is called a basic vector and it contains (n − `) initial 0’s and ` terminal 1’s, so that the number represented by a basic vector is #u = 2`− 1.
Theorem 4.2 The generating function of a path of an ADPH is a mixture of the generating functions of its basic paths.
Proof: The following lemma gives the basic relationship to prove the theorem.
Lemma 4.3 The generating function of a phase with parameter qi can be represented as the mixture of the generating functions of a phase with parameter qi+1 and a sequence of two phases with parameter qi
and qi+1.
The above lemma is a consequence of the relationship:
piz
A path r is composed by geometric phases according to its associated binary vector u. Starting from the rightmost component of u which is not ordered as a basic path (Definition 4.2), the application of (4.23) splits the path into two paths which are enriched in components with higher indices. Repeated application of (4.23) can transform any path in a mixture of basic paths. Cumani [21] has provided an algorithm which performs the transformation of any path into a mixture of basic paths in a finite number of steps.
Example 4.3 Let n = 5 and let r be a path of length ` = 2 characterized by the binary vector u = [0, 1, 0, 1, 0] (corresponding to the phases with parameters q2 and q4). By applying Lemma 4.3 to the rightmost phase of r (phase 4), the associated binary vector u can be decomposed in a mixture of two binary vectors one containing phase 5 and the second one containing the sequence of phases (4, 5). Thus the original path is split into the mixture of the following two paths:
u= [0, 1, 0, 1, 0] =⇒
[0, 1, 0, 0, 1]
[0, 1, 0, 1, 1] (4.24)
Now for each obtained binary vector, we take the rightmost phase which is not already ordered in a basic path, and we decompose the corresponding path into two paths according to equation (4.23). The complete decomposition tree is shown next, where all the final binary vectors are basic vectors according to Definition 4.2.
Corollary 4.4 Canonical Form CF1.
Any ADPH has a unique representation as a mixture of basic paths called Canonical Form 1 (CF1). The DTMC associated to the CF1 is given in Figure 4.4, and its matrix representation (a, P ) has the form:
a = [a1, a2, . . . , an] , P =
q1 p1 0 0 . . . 0 0 q2 p2 0 . . . 0 ... ... ... ... ... 0 0 0 0 . . . qn
(4.26)
with:
Xn 1
ai = 1 and: p1≤ p2≤ . . . ≤ pn (4.27)
a1 a2 an
pn
p2
p1
q1 q2 qn
Figure 4.4: Canonical Form CF1.
Proof: The Corollary is a direct consequence of Theorem 4.2.
Due to the particular structure of the matrix in (4.26), the relevant elements can be stored into an n-dimensional vector p containing the pi’s, so that we will use the notation (a, p) as the representation of a CF1, where a and p are n-dimensional vectors (where 0 ≤ ai≤ 1, 0 < pi≤ 1).
Example 4.4 The transformation of the ADPH introduced in Example 4.2 (Figure 4.2) into the canonical form CF1 proceeds along the following steps. We first order the eigenvalues of the matrix B into a decreasing sequence to obtain: q1= b22= 0.6 and q2= b11= 0.3 with q1≤ q2. Then, any path is assigned its characteristic binary vector. If the binary vector is not in basic form, each path is transformed into a mixture of basic paths by repeated application of (4.23), along the line shown in Example 4.3. Since the ADPH of Figure 4.2 is of order n = 2, we have two basic paths b1= [0, 1] and b2= [1, 1].
Path r1- The associated binary vector is u1= [0, 1] and is coincident with the basic path b1. Hence:
F(z, r1) = F(z, b1) (4.28)
Path r2- The associated binary vector is u2= [1, 1] and is coincident with the basic path b2. Hence:
Path r3 - The associated binary vector is u3 = [1, 0] and is not a basic path. Hence, r3 must be transformed in a mixture of basic paths as shown in Figure 4.5. Application of (4.23) provides:
F(z, r3) = w1F(z, b1) + (1 − w1)F(z, b2) (4.30)
with w1=p1
p2
= 4 7.
w
1:
1 − w
1:
q2
q1
p1
p2
q2
q1
p1 p2
b
1= [0, 1]
b
2= [1, 1]
u
3= [1, 0]
Figure 4.5: Transformation of the path r3. The generating function of the ADPH can be finally written as:
F(z) = α1[P (r1)F(z, r1) + P (r2)F(z, r2)] + α2P (r3)F(z, r3)
= α1P (r1)F(z, b1) + α1P (r2)F(z, b2) + (4.31) α2P (r3)w1F(z, b1) + α2P (r3)(1 − w1)F(z, b2)
(4.32) can be rearranged in the following CF1 form, with a1= 27α1+47α2
, and a2= 57α1+37α2
:
F(z) = a1F(z, b1) + a2F(z, b2) (4.32)
a2
a1
0.4 0.7
0.3 0.6
Figure 4.6: Canonical form of the ADPH of Figure 4.2.
The DTMC associated to the obtained CF1 is depicted in Figure 4.6, and its representation is:
a= [a1 a2] , p = [0.4 0.7] (4.33)
4.2.1 Properties of Canonical Forms
Property 4.5 The CF1 is a minimal representation of an ADPH and its degree of freedom is 2n − 1.
Given a canonical form CF1 of order n and representation (a, p) (Figure 4.4), the mean, the second moment and the probability generating function are expressed as:
m =
Even if the canonical form CF1 is the simplest minimal form to use in computations, sometimes it can be more convenient to have a minimal representation in which the initial probability is concentrated in the first state. Borrowing terminology from the continuous case [21], we define:
Definition 4.3 Canonical Form CF2.
An ADPH is in canonical form CF2 (Figure 4.7) if transitions are possible from phase 1 to all the other phases (including the absorbing one), and, from phase i (2 ≤ i ≤ n) to phase i itself and i + 1. The initial probability is 1 for phase i = 1 and 0 for any phase i 6= 1.
The matrix representation of the canonical form CF2 is:
α= [1 0 · · · 0] , B =
established by the following relationship:
Figure 4.7: Canonical Form CF2
Definition 4.4 Canonical Form CF3.
An ADPH is in canonical form CF3 (Figure 4.8) if from any phase i (1 ≤ i ≤ n) transitions are possible to phase i itself, i + 1 and n + 1. The initial probability is 1 for phase i = 1 and 0 for any phase i 6= 1.
The matrix representation of CF3 is:
α= [1 0 · · · 0] , B =
It is trivial to verify that CF3 is a minimal form and that the relationships between CF1 and CF3 is established by the following relationships:
si =
If an ADPH r.v. τ is expressed in CF1, its mean, second moment and generating function can be evaluated according to (4.34), (4.35) and (4.36). In the following recursive expressions are discussed to compute the same quantities. These expressions will be necessary in the sequel.
1
qn−1 qn−2
en
e,n e,n−1 e,n−2 e,2 e,1 en−2
qn
en−1
q1
Figure 4.8: Canonical Form CF3
Definition 4.5 Given an ADPH r.v. τ of order n with CF1 representation (a, p), the conditional ab-sorption time τi is defined as the time to reach state i + 1 (≤ n) conditioned to the fact that the DTMC started from one of the preceding phases (from phase 1 to i).
The conditional absorption time τi is obtained by making state i + 1 absorbing and renormalizing the initial probabilities. The conditional absorption time τi is a CF1 of order i and representation (a(i)/si, p(i)), where:
- a(i) is the vector grouping the first i elements of a, i.e., a(i) = {a1, ..., ai};
- p(i) is the vector grouping the first i elements of p, i.e., p(i) = {p1, ..., pi};
- si is a normalization factor and is equal to the sum of the first i elements of the initial probability vector, i.e., si=Pi
j=1aj, sn= 1.
Let us denote by mi, di and Fi the mean, the second moment and the generating function of the conditional absorbing time τi, respectively. The following recursive relations hold:
mi+1 = si
si+1
mi+ 1 pi+1
, (4.43)
di+1 = si
si+1
di+ 2mi
pi+1
+2 − pi+1
(pi+1)2 , (4.44)
Fi+1(z) = si
si+1Fi(z) pi+1z
1 − (1 − pi+1)z +ai+1
si+1
pi+1z
1 − (1 − pi+1)z . (4.45)