Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
3.13 Expanding P
n
in Terms of Its Eigenvalues 95
A
1
= X
⎡
⎣
100
000
000
⎤
⎦
X
−1
(3.83)
A
2
= X
⎡
⎣
000
010
000
⎤
⎦
X
−1
(3.84)
A
3
= X
⎡
⎣
000
000
001
⎤
⎦
X
−1
(3.85)
The selection matrix effectively ensures that A
i
is given by the product of the
i-th column of X and the i-th row of X
−1
WWW: We developed the function SELECT(P) that can be used to obtain the
different matrices A
i
for a diagonalizable matrix.
It will prove useful to write A
i
explicitly in terms of the corresponding eigenvec-
tor. A
i
can be written in the alternative form
A
i
= x
i
z
i
(3.86)
where x
i
is the i-th eigenvector of P, which is also the i-th column of X, and z
i
is
the m-row vector corresponding to the i-th row of X
−1
. Thus we have
A
i
=
z
i1
x
i
z
i2
x
i
z
i3
x
i
··· z
im
x
i
(3.87)
The following two theorems discuss some interesting properties of the expansion
matrices A
i
.
Theorem 3.5 Matrix A
1
is column stochastic and all its columns are identical.
Proof A
1
is found from (3.87) as
A
1
=
z
11
x
1
z
12
x
1
z
13
x
1
··· z
1m
x
1
(3.88)
But Lemma 3.3 on page 93 proved that z
11
, z
12
, ..., z
1m
are all equal to unity.
Thus the above equation becomes
A
1
=
x
1
x
1
··· x
1
(3.89)
This proves the theorem.
Theorem 3.5 results in the following very useful lemma.
Lemma 3.4 The steady-state distribution vector s(∞) = s must be independent of
the initial value s(0) and equals any column of A
1
.
From Theorem 3.5 and Lemma 3.4 we can state the following very useful
lemma.
96 3 Markov Chains
Lemma 3.5 Each column of A
1
represents the steady-state distribution vector for
the Markov chain.
We define a differential matrix as a matrix in which the sum of each column is
zero. The following theorem states that matrices A
i
corresponding to eigenvalues
λ
i
= 1 are all differential matrices.
Theorem 3.6 The expansion matrices A
i
corresponding to eigenvalues λ
i
= 1 are
differential, i.e. σ (A
i
) = 0.
Proof The sum of column j in (3.80) is given by
σ
j
(P
n
) = σ
j
(A
1
) +λ
n
2
σ
j
(A
2
) +λ
n
3
σ
j
(A
3
) +··· (3.90)
Lemma 3.1 on page 85 assures us that P
n
is column stochastic and Theorem 3.5
on page 95 assures us that A
1
is also column stochastic. Therefore, we can write the
above equation as
1 = 1 +λ
n
2
σ
j
(A
2
) +λ
n
3
σ
j
(A
3
) +··· (3.91)
Since this equation is valid for all values of λ
i
and n,wemusthave
σ
j
(A
2
) = σ
j
(A
3
) =···=σ
j
(A
m
) = 0 (3.92)
The above equations are valid for all values of 1 ≤ j ≤ m. Thus all the matrices
A
i
which correspond to λ
i
= 1 are all differential matrices. And we can write
σ (A
2
) = σ (A
3
) =···=σ (A
m
) = 0 (3.93)
This proves the theorem.
The following theorem is related to Theorem 3.2 on page 77. The theorem es-
sentially explains the effect of premultiplying any matrix by a differential matrix.
Theorem 3.7 Given any matrix A and a differential matrix V, then matrix B = VA
will be a differential matrix.
Proof When A is premultiplied by V matrix B results
B = VA (3.94)
Element b
ij
is given by the usual matrix product formula
b
ij
=
m
k=1
v
ik
a
kj
(3.95)
3.13 Expanding P
n
in Terms of Its Eigenvalues 97
The sum of the j-th column of matrix B is denoted by σ
j
(B) and is given by
σ
j
(B) =
m
i=1
b
ij
=
m
i=1
m
k=1
v
ik
a
kj
(3.96)
Now reverse the order of summation on the right-hand side of the above equation
σ
j
(B) =
m
i=1
b
ij
=
m
k=1
a
kj
m
i=1
v
ik
(3.97)
Because V is differential we have
σ
j
(V) =
m
i=1
v
ik
= 0 (3.98)
Therefore, (3.97) becomes
σ
j
(B) =
m
i=1
b
ij
=
m
k=1
a
kj
×0
= 0 (3.99)
Thus we proved that sum of columns of a matrix becomes zero when the matrix
is premultiplied by a differential matrix.
Example 3.17 The following is a diagonalizable state matrix.
P =
⎡
⎣
0.10.31
0.20.30
0.70.40
⎤
⎦
We would like to express P
n
in the form as in (3.80).
First thing is to check that P is diagonalizable by checking that it has three distinct
eigenvalues. Having assured ourselves that this is the case, we use the MATLAB
function select that we developed, to find that
P
n
= A
1
+λ
n
2
A
2
+λ
n
3
A
3
98 3 Markov Chains
where λ
1
= 1 and
A
1
=
⎡
⎣
0.476 0.476 0.476
0.136 0.136 0.136
0.388 0.388 0.388
⎤
⎦
A
2
=
⎡
⎣
0.495 0.102 −0.644
−0.093 −0.019 0.121
−0.403 −0.083 0.524
⎤
⎦
A
3
=
⎡
⎣
0.028 −0.578 0.168
−0.043 0.883 −0.257
0.015 −0.305 0.089
⎤
⎦
Notice that matrix A
1
is column stochastic and all its columns are equal. Notice
also that the sum of columns for matrices A
2
and A
3
is zero.
Sometimes two eigenvalues are the complex conjugate of each other. In that case
the corresponding eigenvectors will be complex conjugate and so are the corre-
sponding matrices A
i
such that the end result P
(n)
is purely real.
Example 3.18 A Markov chain has the transition matrix
P =
⎡
⎣
0.20.40.2
0.10.40.6
0.70.20.2
⎤
⎦
Check to see if this matrix has distinct eigenvalues. If so,
(a) expand the transition matrix P
n
in terms of its eigenvalues
(b) find the value of s(3) using the expression in (3.80).
The eigenvalues of P are λ
1
= 1, λ
2
=−0.1 + j0.3, and λ
3
=−0.1 − j0.3. We
see that complex eigenvalues appear as complex conjugate pairs. The eigenvectors
corresponding to these eigenvalues are
X =
⎡
⎣
0.476 −0.39 − j0.122 −0.39 + j0.122
0.660 0.378 − j0.523 0.378 + j0.523
0.581 0.011 + j0.645 0.011 − j0.645
⎤
⎦
We see that the eigenvectors corresponding to the complex eigenvalues appear
also as complex conjugate pairs. Using the function select(P), we express P
n
according to (3.80)
P
n
= A
1
+λ
n
2
A
2
+λ
n
3
A
3
3.13 Expanding P
n
in Terms of Its Eigenvalues 99
where
A
1
=
⎡
⎣
0.277 0.277 0.277
0.385 0.385 0.385
0.339 0.339 0.339
⎤
⎦
A
2
=
⎡
⎣
0.362 + j0.008 −0.139 − j0.159 −0.139 + j0.174
−0.192 + j0.539 0.308 − j0.128 −0.192 − j0.295
−0.169 − j0.546 −0.169 + j0.287 0.331 + j0.121
⎤
⎦
A
3
=
⎡
⎣
0.362 − j0.008 −0.139 + j0.159 −0.139 − j0.174
−0.192 − j0.539 0.308 + j0.128 −0.192 + j0.295
−0.169 + j0.546 −0.169 − j0.287 0.331 − j0.121
⎤
⎦
We see that the expansion coefficients corresponding to the complex eigenvec-
tors appear as complex conjugate pairs. This ensures that all the components of the
distribution vector will always be real numbers. The distribution vector at time step
n = 3is
s(3) = P
3
s(0)
=
A
1
+λ
3
2
A
2
+λ
3
3
A
3
s(0)
=
0.285 0.389 0.326
t
Example 3.19 Consider the on–off source example whose transition matrix was
given by
P =
s 1 −a
1 −sa
(3.100)
Express this matrix in diagonal form and find an expression for the n-th power
of P.
Using MAPLE or MATLAB’s SYMBOLIC packages, the eigenvectors for this
matrix are
x
1
=
(
1 −a
)
/
(
1 −s
)
1
t
; withλ
0
= 1 (3.101)
x
2
=
−11
t
; withλ
1
= s + a −1 (3.102)
Thus we have
X =
(1 −a)/(1 −s) −1
11
(3.103)
X
−1
=
1
α
1 −s 1 −s
s − 11−a
(3.104)
100 3 Markov Chains
where α =
(
s + a −1
)
.AndP
n
is given by
P
n
= X
10
0 α
n
X
−1
(3.105)
=
1
α
1 −a − α
n
(
s − 1
)(
1 −α
n
)(
1 −a
)
(
1 −α
n
)(
1 −s
)
1 −s +α
n
(
1 −a
)
(3.106)
We can write P
n
in the summation form
P
n
= A
1
+α
n
A
2
(3.107)
where
A
1
=
1
2 −a − s
1 −a 1 −a
1 −s 1 −s
(3.108)
A
2
=
1
2 −a − s
1 −sa−1
s − 11−a
(3.109)
The observations on the properties of the matrices A
1
and A
2
can be easily
verified.
For large values of n, we get the simpler form
lim
n→∞
P
n
= A
1
=
1
2 −a − s
1 −a 1 −a
1 −s 1 −s
(3.110)
and in the steady-state our distribution vector becomes
s =
1
2 −a − s
(
1 −a
)(
1 −s
)
t
and this is independent of the initial state of our source.
Example 3.20 Consider the column stochastic matrix
P =
⎡
⎣
0.50.80.4
0.50 0.3
00.20.3
⎤
⎦
.
This matrix is diagonalizable. Express it in the form given in (3.63) and ob-
tain a general expression for the distribution vector at step n. What would be the
distribution vector after 100 steps assuming an initial distribution vector s(0) =
100
t
The eigenvalues for this matrix are λ
1
= 1, λ
2
=−0.45, λ
3
= 0.25. Since
they are distinct, we know that the matrix is diagonalizable. The eigenvectors corre-
sponding to these eigenvalues are
3.13 Expanding P
n
in Terms of Its Eigenvalues 101
x
1
=
0.869 0.475 0.136
t
x
2
=
−0.577 0.789 −0.211
t
x
3
=
−0.577 −0.211 0.789
t
and matrix X in (3.63) is simply X =
x
1
x
2
x
3
which is given by
X =
⎡
⎣
0.869 −0.577 −0.577
0.475 0.789 −0.212
0.136 −0.212 0.789
⎤
⎦
Notice that the sum of the elements in the second and third columns is exactly
zero. We also need the inverse of this matrix which is
X
−1
=
⎡
⎣
0.676 0.676 0.676
−0.473 0.894 −0.106
−0.243 0.123 1.123
⎤
⎦
Thus we can express P
n
as
P
n
= X
⎡
⎣
10 0
0 λ
n
2
0
00λ
n
3
⎤
⎦
X
−1
= A
1
+λ
n
2
A
2
+λ
n
3
A
3
where the three matrices A
1
, A
2
, and A
3
are given using the following expressions.
A
1
= X
⎡
⎣
100
000
000
⎤
⎦
X
−1
(3.111)
A
2
= X
⎡
⎣
000
010
000
⎤
⎦
X
−1
(3.112)
A
3
= X
⎡
⎣
000
000
001
⎤
⎦
X
−1
(3.113)
102 3 Markov Chains
The above formulas produce
A
1
=
⎡
⎣
0.587 0.587 0.587
0.321 0.321 0.321
0.092 0.092 0.092
⎤
⎦
A
2
=
⎡
⎣
0.273 −0.516 0.062
−0.373 0.705 −0.084
0.1 −0.189 0.022
⎤
⎦
A
3
=
⎡
⎣
0.141 −0.071 −0.649
0.051 −0.026 −0.237
−0.192 0.097 0.886
⎤
⎦
We notice that all the columns in A
1
are identical while the sums of the columns
in A
2
and A
3
is zero. These properties of matrices A
i
guarantee that P
n
remains a
column stochastic matrix for all values of n between 0 and ∞.
Since each λ is a fraction, we see that the probabilities of each state consist of
a steady-state solution (independent of λ) and a transient solution that contains the
different λ
s. In the steady state (i.e., when n →∞) we have the distribution vector
that equals any column of A
1
:
s
(
∞
)
=
0.587 0.321 0.092
t
(3.114)
Thus we get after 100 steps
s(100) = P
100
s(0)
=
⎡
⎣
0.6 +0.3 ×λ
100
2
+0.1 ×λ
100
3
0.3 −0.4λ
100
2
0.1 +0.1λ
100
2
−0.2λ
100
3
⎤
⎦
=
0.587 0.321 0.092
t
Thus the distribution vector settles down to its steady-state value irrespective of
the initial state.
3.13.1 Test for Matrix Diagonalizability
The above two techniques expanding s(0) and diagonalizing P both relied on the
fact that P could be diagonalized. We mentioned earlier that a matrix could be diag-
onalized when its eigenvalues are all distinct. While this is certainly true, there is a
more general test for the diagonalizability of a matrix.
A matrix is diagonalizable only when its Jordan canonic form (JCF) is
diagonal [4].
3.14 Finding s (n) Using the Jordan Canonic Form 103
We will explore this topic more in the next section.
Example 3.21 Indicate whether the matrix in Example 3.6 on page 72 is diagonal-
izable or not.
The eigenvalues of this matrix are λ
1
= 1 and λ
2
= λ
3
=−1/4. Since some
eigenvalues are repeated, P might or might not be diagonalizable. Using Maple or
the MATLAB function JORDAN(P), the Jordan canonic form for this matrix is
J =
⎡
⎣
10 0
0 −1/41
00−1/4
⎤
⎦
Since J is not diagonal, P is not diagonalizable. It is as simple as that!
3.14 Finding s (n) Using the Jordan Canonic Form
We saw in Section 3.12 how easy it was to find s(n) by diagonalizing P. We would
like to follow the same lines of reasoning even when P cannot be diagonalized
because one or more of its eigenvalues are repeated.
3.14.1 Jordan Canonic Form (JCF)
Any m ×m matrix P can be transformed through a similarity transformation into its
Jordan canonic form (JCF) [4]
P = UJU
−1
(3.115)
Matrix U is a nonsingular matrix and J is a block-diagonal matrix
J =
⎡
⎢
⎢
⎢
⎢
⎢
⎣
J
1
00··· 0
0 J
2
0 ··· 0
00J
3
··· 0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
000··· J
t
⎤
⎥
⎥
⎥
⎥
⎥
⎦
(3.116)
where the matrix J
i
is an m
i
×m
i
Jordan block or Jordan box matrix of the form
J
i
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
λ
i
10··· 0
0 λ
i
1 ··· 0
00λ
i
··· 0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
000··· 1
000··· λ
i
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
(3.117)
104 3 Markov Chains
such that the following equation holds
m
1
+m
2
+···+m
t
= m (3.118)
The similarity transformation performed in (3.115) above ensures that the eigen-
values of the two matrices P and J are identical. The following example proves this
statement.
Example 3.22 Prove that if the Markov matrix P has Jordan canonic form matrix J,
then the eigenvalues of P are identical to those of J. Having proved that, find the
relation between the corresponding eigenvectors for both matrices.
We start first by proving that the characteristic equations for both matrices are
identical. The characteristic equation or characteristic polynomial of P is given by
x(λ) = det
(
P −λI
)
(3.119)
where det(A) is the determinant of the matrix A. The characteristic polynomial of J
is given by
y(α) = det
(
J −αI
)
(3.120)
where α is the assumed root or eigenvalue of J. But (3.115) indicates that J can be
expressed in terms of P and U as
J = U
−1
PU
Using this, we can express (3.120) as
y(α) = det
U
−1
PU −αU
−1
U
We can factor out the matrices U
−1
and U to get
y(α) = det
U
−1
(
P −αI
)
U
But the rules of determinants indicate that det(AB) = det(A)×det(B). Thus we
have
y(α) = det
U
−1
det
(
U
)
det
(
P −αI
)
But the rules of determinants also indicate that det(A
−1
)×det(A) = 1. Thus we
have
y(α) = det
(
P −αI
)
(3.121)