Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
3.14 Finding s (n) Using the Jordan Canonic Form 105
This proves that the polynomial x(λ) in (3.119) and the polynomial y(α)in
(3.121) are identical and the matrices P and J have the same roots or eigenvalues.
So far, we proved that the two matrices P and J have the same roots or eigen-
values. Now we want to prove that they have related eigenvectors. Assume x is an
eigenvector of P associated with eigenvalue λ.
Px = λx
but P = UJU
−1
and we can write the above equation as
UJU
−1
x = λx
Now we premultiply both sides of the equation by U
−1
to get
JU
−1
x = λU
−1
x
We write u = U
−1
x to express the above equation as
Ju= λu
Thus the relation between the eigenvectors of P and J is
u = U
−1
x
This is why the transformation
P = UJU
−1
is called a similarity transformation. In other words, a similarity transformation
does not change the eigenvalues and scales the eigenvectors.
MATLAB offers the command [U,J] = JORDAN(P) to obtain the Jordan
canonic form as the following example shows.
Example 3.23 Obtain the Jordan canonic form for the transition matrix
P =
⎡
⎣
00.25 0.25
0.75 0 0.25
0.25 0.75 0.5
⎤
⎦
106 3 Markov Chains
Using MATLAB we are able to obtain the Jordan canonic form
[U, J] = jordan(P)
U =
0.2000 0 0.8000
0.2800 0.4000 −0.2800
0.5200 −0.4000 −0.5200
J =
1.0000 0 0
0 −0.2500 1.0000
00−0.2500
3.14.2 Properties of Jordan Canonic Form
We make the following observations on the properties of the Jordan canonic form:
1. The number of Jordan blocks equals the number of linearly independent eigen-
vectors of P.
2. The elements in P are real but matrix U might have complex elements.
3. Matrix U can be written as
U =
U
1
U
2
··· U
t
where each matrix U
i
is a rectangular matrix of dimension m ×m
i
such that
m
1
+m
2
+···+m
t
= m
4. Rectangular matrix U
i
corresponds to the Jordan block J
i
and eigenvalue λ
i
.
5. Each rectangular matrix U
i
can be decomposed into m
i
column vectors:
U
i
=
u
i,1
u
i,2
··· u
i,m
i
(3.122)
where each column vector has m components.
6. The first column u
i,1
is the eigenvector of matrix P and corresponds to the
eigenvalue λ
i
:
Pu
i,1
= λ
i
u
i,1
(3.123)
7. The other column vectors of U
i
satisfy the recursive formula
Pu
i, j
= λ
i
u
i, j
+u
i, j−1
(3.124)
where 2 ≤ j ≤ m
i
.
3.15 Properties of Matrix U 107
8. There could be one or more blocks having the same eigenvalue. In other words,
we could have two Jordan blocks J
1
and J
2
such that both have the same eigen-
value on their main diagonals.
9. The eigenvalue λ
i
is said to have algebraic multiplicity of m
i
.
10. If all Jordan blocks are one-dimensional (i.e., all m
i
= 1), then the Jordan
matrix J becomes diagonal. In that case, matrix P is diagonalizable.
Example 3.24 Given the following Jordan matrix, identify the Jordan blocks and
find the eigenvalues and the number of linearly independent eigenvectors.
J =
⎡
⎢
⎢
⎢
⎢
⎣
0.51 0 0 0
00.50 0 0
000.21 0
0000.20
00001
⎤
⎥
⎥
⎥
⎥
⎦
We have three Jordan blocks as follows:
J
1
=
0.51
00.5
J
2
=
0.21
00.2
J
3
=
[
1
]
From the three Jordan blocks, we determine the eigenvalues as λ
1
= 0.5,
λ
2
= 0.2, and λ
3
= 1. We also know that we must have three linearly independent
eigenvectors. Using MATLAB, the eigenvectors of J are
x
1
=
10000
t
x
2
=
00100
t
x
3
=
00001
t
we notice that these eigenvectors are linearly independent because they are orthog-
onal to each other.
3.15 Properties of Matrix U
According to Theorem 3.3 on page 79, Theorem 3.4 on page 79, and Lemma 3.3 on
page 93, the columns of matrix U must satisfy the following properties:
1. The sum of the elements of the vector u corresponding to the eigenvalue λ = 1
is arbitrary and could be taken as unity, i.e. σ (u) = 1.
2. The sum of the elements of the vectors u belonging to Jordan blocks with eigen-
value λ = 1 must be zero, i.e. σ (u) = 0.
3. Matrix U
−1
has ones in its first row.
108 3 Markov Chains
3.16 P
n
Expressed in Jordan Canonic Form
We explained in the previous subsection that the transition matrix could be ex-
pressed in terms of its Jordan canonic form which we repeat here for convenience:
P = UJU
−1
(3.125)
where U is a unitary matrix. Equation 3.125 results in a very simple expression for
P
n
in (3.38). To start, we can calculate P
2
as
P
2
=
UJU
−1
×
UJU
−1
(3.126)
= UJ
2
U
−1
(3.127)
In general we have
P
n
= UJ
n
U
−1
(3.128)
where J
n
has the same block structure as J
J
n
=
⎡
⎢
⎢
⎢
⎢
⎢
⎣
J
n
1
00··· 0
0 J
n
2
0 ··· 0
00J
n
3
··· 0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
000··· J
n
t
⎤
⎥
⎥
⎥
⎥
⎥
⎦
(3.129)
In the above equation, the Jordan block J
n
i
of dimension m
i
× m
i
is an upper
triangular Toeplitz matrix in the form
J
n
i
=
⎡
⎢
⎢
⎢
⎢
⎢
⎣
f
n
i0
f
n
i1
f
n
i2
f
n
i3
··· f
n
i,m
i
−1
0 f
n
i0
f
n
i1
f
n
i2
··· f
n
i,m
i
−2
00f
n
i0
f
n
i1
··· f
n
i,m
i
−3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0000··· f
n
i0
⎤
⎥
⎥
⎥
⎥
⎥
⎦
(3.130)
where f
n
ij
is given by
f
n
ij
=
n
j
λ
n−j
i
0 ≤ j < m
i
(3.131)
3.17 Expressing P
n
in Terms of Its Eigenvalues 109
We assumed the binomial coefficient vanishes whenever j > n. In fact, the term
f
n
ij
equals the j-th term in the binomial expansion
(
λ
i
+1
)
n
=
m
i
−1
j=0
f
n
ij
(3.132)
3.17 Expressing P
n
in Terms of Its Eigenvalues
Equation (3.128) related P
n
to the n-th power of its Jordan canonic form as
P
n
= UJ
n
U
−1
(3.133)
Thus we can express P
n
in the above equation in the form
P
n
=
m
1
−1
j=0
f
n
1 j
A
1 j
+
m
1
−1
j=0
f
n
2 j
A
2 j
+
m
2
−1
j=0
f
n
3 j
A
3 j
+··· (3.134)
The above equation can be represented as the double summation
P
n
=
t
i=1
m
i
−1
j=0
f
n
ij
A
ij
(3.135)
where t is the number of Jordan blocks and it was assumed that f
n
ij
is zero whenever
j > n.
The matrices A
ij
can be determined from the product
A
ij
= UY
ij
U
−1
(3.136)
where Y
ij
is the selection matrix which has zeros everywhere except for the ele-
ments corresponding to the superdiagonal j in Jordan block i which contains the
values 1. For example, assume a 6×6 Markov matrix whose Jordan canonic form is
J =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
100000
00.21 0 0 0
00 0.21 0 0
0000.20 0
00000.51
000000.5
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
This Jordan canonic form has three Jordan blocks (t = 3) and the selection
matrix Y
21
indicates that we need to access the first superdiagonal of the second
Jordan block:
110 3 Markov Chains
Y
21
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
000000
001000
000100
000000
000000
000000
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
WWW: We have prepared the MATLAB function J
POWERS(n,P) that accepts
a Markov matrix (or any square matrix) and expresses the matrix P
n
in the form
given by (3.134).
Example 3.25 Consider the Markov matrix
P =
⎡
⎣
00.25 0.4
0.75 0 0.3
0.25 0.75 0.3
⎤
⎦
Use the Jordan canonic form technique to find the decomposition of P
3
according
to (3.134).
We start by finding the Jordan canonic form for the given matrix to determine
whether P can be diagonalized or not. The Jordan decomposition produces
U =
⎡
⎣
0.20 0.00 0.80
0.44 0.20 −0.44
0.36 −0.20 −0.36
⎤
⎦
J =
⎡
⎣
100
0 −0.25 1
00−0.25
⎤
⎦
The given Markov matrix has two eigenvalues λ
1
= 1 and λ
2
=−0.25, which is
repeated twice. Since the Jordan matrix is not diagonal, we cannot diagonalize the
transition matrix and we need to use the Jordan decomposition techniques to find
P
n
. By using the function J POWERS, we get
P
3
= A
1
+ f
3
20
A
20
+ f
3
21
A
21
where
f
3
20
= 0.0156
f
3
21
= 0.187
3.19 Renaming the States 111
and the corresponding matrices are given by
A
1
=
⎡
⎣
0.20 0.20 0.20
0.44 0.44 0.44
0.36 0.36 0.36
⎤
⎦
A
20
=
⎡
⎣
0.80 −0.20 −0.20
−0.44 0.56 −0.44
−0.36 −0.36 0.64
⎤
⎦
A
21
=
⎡
⎣
00 0
0.2 −0.05 −0.05
−0.20.05 0.05
⎤
⎦
3.18 Finding P
n
Using the Z-Transform
The z-transform technique has been proposed for finding expressions for P
n
.In
our opinion, this technique is not useful for the following reasons. Obtaining the
z-transform is very tedious since it involves finding the inverse of a matrix using
symbolic, not numerical, techniques. This is really tough for any matrix whose
dimension is above 2 × 2 even when symbolic arithmetic packages are used. Fur-
thermore, the technique will not offer any new insights that have not been already
covered in this chapter. For that reason, we delegate discussion of this topic to
Appendix C on page xxx. The interested reader can gloss over the appendix and
compare it to the techniques developed in this chapter.
3.19 Renaming the States
Sometimes we will need to rename or relabel the states of a Markov chain. When we
do that, the transition matrix will assume a simple form that helps in understanding
the behavior of the system.
Renaming or relabeling the states amounts to exchanging the rows and columns
of the transition matrix. For example, if we exchange states s
2
and s
5
, then rows 2
and 5 as well as columns 2 and 5 will be exchanged. We perform this rearranging
through the elementary exchange matrix E(2, 5) which exchanges states 2 and 5:
E(2, 5) =
⎡
⎢
⎢
⎢
⎢
⎣
10000
00001
00100
00010
01000
⎤
⎥
⎥
⎥
⎥
⎦
112 3 Markov Chains
In general, the exchange matrix E(i, j) is similar to the identity matrix except
that rows i and j of the identity matrix are exchanged. The exchange of states is
achieved by pre and post multiplying the transition matrix:
P
= E(2, 5) PE(2, 5)
Assume for example that P is given by
P =
1
2
3
4
5
12345
⎡
⎢
⎢
⎢
⎢
⎣
00.100.11
00.300.20
10.200.20
00.300.40
00.110.10
⎤
⎥
⎥
⎥
⎥
⎦
where the state indices are indicated around P for illustration.
Exchanging states 2 and 5 results in
P
=
1
5
3
4
2
15342
⎡
⎢
⎢
⎢
⎢
⎣
0100.10.1
0010.10.1
1000.20.2
0000.40.1
0000.20.3
⎤
⎥
⎥
⎥
⎥
⎦
Problems
Markov Chains
3.1 Consider Example 3.2 where the time step value is chosen as T = 8/λ
a
.
Estimate the packet arrival probability a.
3.2 Three workstation clusters are connected to each other using switching hubs.
At steady state the following daily traffic share of each hub was observed. For
hub A, 80% of its traffic is switched to its local cluster, 5% of its traffic is
switched to hub B, and 15% of its traffic is switched to hub C. For hub B,
90% of its traffic is switched to its local cluster, 5% of its traffic is switched
to hub A, and 5% of its traffic is switched to hub C. For hub C, 75% of its
traffic is switched to its local cluster, 10% of its traffic is switched to hub A,
and 15% of its traffic is switched to hub B. Assuming initially the total traffic
is distributed among the three hubs as 60% in hub A, 30% in hub B, and 10%
in hub C,
(a) write the initial distribution vector for the total traffic
(b) construct the transition matrix for the Markov chain that describes the
traffic share of the three hubs.
Problems 113
3.3 In order to plan the volume of LAN traffic flow in a building, the system
administrator divided the building into three floors. Traffic volume trend in-
dicated the following hourly pattern. In the first floor, 60% of traffic is local,
30% of traffic goes to second floor, 10% of traffic goes to third floor. In the
second floor, 30% of traffic is local, 40% of traffic goes to first floor, 30%
of traffic goes to third floor. In the third floor, 60% of traffic is local, 30%
of traffic goes to first floor, 10% of traffic goes to second floor. Assuming
initially traffic volume is distributed as 10% in first floor, 40% in second floor,
and 50% in third floor,
(a) write the initial distribution vector for the total traffic
(b) construct the transition matrix for the Markov chain that describes the
traffic share of the three floors.
3.4 The transition matrix for a Markov chain is given by
P =
0.30.6
0.70.4
What does each entry represent?
3.5 A traffic data generator could be either idle or is generating data at five dif-
ferent rates λ
1
<λ
2
< ···<λ
5
. When idle, the source could equally likely
remain idle or it could start transmitting at the lowest rate λ
1
. When in the
highest rate state λ
5
, the source could equally likely remain in that state or it
could switch to the next lower rate λ
4
. When in the other states, the source
is equally likely to remain in its present state or it could start transmitting at
the next lower or higher rate. Identify the system states and write down the
transition matrix.
3.6 Repeat the above problem when transitions between the different states is
equally likely.
3.7 The market over reaction theory proposes that stocks with low return (called
“losers”) subsequently outperform stocks with high return (called “winners”)
over some observation period. The rest of the market share is stocks with
medium return (called “medium”). It was observed that winners split accord-
ing to the following ratios: 70% become losers, 25% become medium, and
5% stay winners. Medium stocks split according to the following ratios: 5%
become losers, 90% stay medium, and 5% become winers. Losers split ac-
cording to the following ratios: 80% stay losers, 5% become medium, and
15% become winners. The Markov chain representing the state of a stock is
defined as follows: s
0
represents loser stock, s
1
represent medium stock, and
s
2
represent winner stocks. Assuming an aggressive manager’s portfolio is
initially split among the stocks in the following percentages, 5% losers, 70%
medium, and 25% winners,
(a) write the initial distribution vector for the portfolio
(b) construct the transition matrix for the Markov chain that describes the
stock share of the portfolio.
114 3 Markov Chains
3.8 Consider Example 3.8, but this time the source is transmitting packets having
random lengths. Assume for simplicity that the transmitted packets can be one
out of three lengths selected at random with probability l
i
(i = 1, 2, 3).
(a) Identify the different states of the system.
(b) Draw the corresponding Markov state transition diagram.
(c) Write down the transition matrix.
Time Step Selection
3.9 Develop the proper packet arrival statistics for the case considered in Section
3.3.1 when the line is sampled at a rate r while the packets arrive at an average
rate λ
a
.
Markov Transition Matrices
3.10 Explain what is meant by a homogeneous Markov chain.
3.11 By Assuming P is a transition matrix, prove that the unit row vector
u =
111··· 1
is a left eigenvector of the matrix and its associated eigenvalue is λ = 1.
3.12 Prove (3.11) on page 70 which states that at any time step n, the sum of the
components of the distribution vector s(n) equals 1. Do your proof by pro-
ceeding as follows:
(a) Start with an initial distribution vector s(0) of an arbitrary dimension m
such that
m
i=1
s
i
(0) = 1.
(b) Prove that s(1) satisfies (3.11).
(c) Prove that s(2) also satisfies (3.11) and so on.
3.13 Prove the properties stated in Section 3.9.1 on page 85.
3.14 Prove Lemma 3.1 on page 85.
3.15 Given a column stochastic matrix P with an eigenvector x that corresponds to
the eigenvalue λ =−1, prove that σ(x) = 0 in accordance with Theorem 3.4.
3.16 In problems 3.17–3.26 determine which of the given matrices are Markov
matrices and justify your answer. For the Markov matrices, determine the
eigenvalues, the corresponding eigenvectors, and the rank.
3.17
0.40.4
0.60.3