Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
3.10 Finding s (n) 85
Find the probability that after three consecutive block accesses the system will
read a block from the cache.
The starting distribution vector is s(0) =
100
t
and we have
P
2
=
⎡
⎣
0.51 0.14 0.01
0.29 0.53 0.16
0.20 0.33 0.83
⎤
⎦
P
3
=
⎡
⎣
0.386 0.151 0.023
0.325 0.432 0.197
0.289 0.417 0.780
⎤
⎦
The distribution vector after three iterations is
s(3) = P
3
s(0) =
0.386 0.325 0.289
t
The probability that the system will read a block from the cache is 0.386.
3.9.1 Properties of P
n
Matrix P
n
has many interesting properties that we list below:
• P
n
remains a column stochastic matrix according to Lemma 3.1.
• A nonzero element in P can increase or decrease in P
n
but can never become
zero.
• A zero element in P could remain zero or increase in P
n
but can never become
negative.
As a result of Theorem 3.2 on page 77, we deduce the following two lemmas.
Lemma 3.1 Given a column stochastic matrix P, then P
n
,forn≥ 0, is also column
stochastic.
The proof is easily derived from Theorem 3.2.
Lemma 3.2 The state vector s(n) at instance n is given by
s(n) = P
n
s(0) (3.39)
This vector must be a distribution vector for all values of n ≥ 0. The proof is easily
derived from Theorem 3.2 after applying the theorem to the state vector s(0).
3.10 Finding s (n)
We can determine the state of our Markov chain at time step n if we are able to
calculate P
n
. In general, performing n matrix multiplications is tedious and leads to
computational noise. Besides, no insight can be gained from repeatedly multiplying
a matrix. Alternative techniques for obtaining an expression for s(n)orP
n
include
the following:
86 3 Markov Chains
1. Repeated multiplications to get P
n
.
2. Expanding the initial distribution vector s(0).
3. Diagonalizing the matrix P.
4. Using the Jordan canonic form of P.
5. Using the z-transform.
The first method is simple and is best done using a mathematical package such
as MATLAB. We have seen examples of this technique in the previous section. We
show in the following sections how the other techniques are used.
3.11 Finding s (n) by Expanding s(0)
In most cases the transition matrix P is simple, i.e. it has m distinct eigenvalues. In
that case we can express our initial distribution vector s(0) as a linear combination
of the m eigenvectors:
s(0) = c
1
x
1
+c
2
x
2
+···+c
m
x
m
(3.40)
where x
i
is the ith eigenvector of P and c
i
is the corresponding scalar expansion
coefficients. We can write the above equation as a simple matrix expression:
s(0) = Xc (3.41)
where X is an m × m matrix whose columns are the eigenvectors of P and c is an
m-component vector of the expansion coefficients:
X =
x
1
x
2
··· x
m
(3.42)
c =
c
1
c
2
··· c
m
t
(3.43)
We need not normalize the eigenvectors before we determine the coefficients
vector c because any normalization constant for X will be accounted for while de-
termining c.
To find s(n) we will use the technique explained below. Equation (3.41) is a
system of m-linear equations in m unknowns, namely the components of the column
vector c. There are many numerical techniques for finding these components like
Gauss elimination, Kramer’s rule, etc. MATLAB has a very simple function for
finding the eigenvectors of P:
X = eig(P) (3.44)
where matrix X will contain the eigenvectors in its columns. To find the coefficient
vector c we use MATLAB to solve the system of linear equations in (3.41) by typing
the MATLAB command
3.11 Finding s (n) by Expanding s (0) 87
c = X \ s(0) (3.45)
where the backslash operator “\” effectively solves for the unknown vector c using
Gaussian elimination.
Note: The function EIGPOWERS(P,s) can be used to expand s in terms of the
eigenvectors of P.
Example 3.14 A Markov chain has the state matrix
P =
⎡
⎢
⎢
⎣
0.30.20.20.2
0.30.40.20.2
0.20.20.20.2
0.20.20.40.4
⎤
⎥
⎥
⎦
Check to see if this matrix has distinct eigenvalues. If so, expand the initial dis-
tribution vector
s(0) =
1000
t
in terms of the eigenvectors of P.
The eigenvalues of P are λ
1
= 1, λ
2
= 0.1, λ
3
= 0.2, and λ
4
= 0. The eigenvec-
tors corresponding to these eigenvalues are
X =
⎡
⎢
⎢
⎣
0.439 −0.707 0.00.0
0.548 0.707 0.707 0.0
0.395 0.00.00.707
0.592 0.0 −0.707 −0.707
⎤
⎥
⎥
⎦
Therefore, we can expand s(0) in terms of the corresponding eigenvectors
s(0) = Xc
where c given by
c =
0.507 −1.10.707 0.283
t
88 3 Markov Chains
Now let us see how to get a simple expression for evaluating s(n) given the ex-
pansion of s(0). We start by using (3.41) to find s(1) as
s(1) = Ps(0) (3.46)
= P
(
c
1
x
1
+c
2
x
2
+···+c
m
x
m
)
(3.47)
= c
1
λ
1
x
1
+c
2
λ
2
x
2
+···+c
m
λ
m
x
m
(3.48)
where λ
i
is the i-th eigenvalue of P corresponding to the i-th eigenvector x
i
.
We can express s(1) in the above equation in matrix form as follows:
s(1) = XDc (3.49)
where X was defined before and D is the diagonal matrix whose diagonal elements
are the eigenvalues of P.
D =
⎡
⎢
⎢
⎢
⎣
λ
1
0 ··· 0
0 λ
2
··· 0
.
.
.
.
.
.
.
.
.
.
.
.
00··· λ
m
⎤
⎥
⎥
⎥
⎦
(3.50)
MATLAB provides a very handy function for finding the two matrices X and D
using the single command
[X, D] = eig(P) (3.51)
Having found s(1), we now try to find s(2)
s(2) = Ps(1) (3.52)
= PXDc (3.53)
but the eigenvectors satisfy the relation
Px
i
= λ
i
x
i
(3.54)
In matrix form we can write the above equation as
PX = XD (3.55)
By substituting (3.55) into (3.53) we get
s(2) = XD
2
c (3.56)
3.11 Finding s (n) by Expanding s (0) 89
where
D
2
=
⎡
⎢
⎢
⎢
⎣
λ
2
1
0 ··· 0
0 λ
2
2
··· 0
.
.
.
.
.
.
.
.
.
.
.
.
00··· λ
2
m
⎤
⎥
⎥
⎥
⎦
(3.57)
In general the distribution vector at time step n is given by
s(n) = XD
n
c (3.58)
where
D
n
=
⎡
⎢
⎢
⎢
⎣
λ
n
1
0 ··· 0
0 λ
n
2
··· 0
.
.
.
.
.
.
.
.
.
.
.
.
00··· λ
n
m
⎤
⎥
⎥
⎥
⎦
(3.59)
It is relatively easy to find the n-th power of a diagonal matrix by simply raising
each diagonal element to the n-th power. Then the distribution vector at time step n
is simply obtained from (3.58).
Example 3.15 Consider the Markov chain in Example 3.14. Find the values of the
distribution vector at time steps 2, 5, and 20.
For the given transition matrix, we can write
s(n) = XD
n
c
where the matrices X, D, and the vector c are given by
X =
⎡
⎢
⎢
⎣
0.439 −0.707 0.00.0
0.548 0.707 0.707 0.0
0.395 0.00.00.707
0.592 0.0 −0.707 −0.707
⎤
⎥
⎥
⎦
D =
⎡
⎢
⎢
⎣
1000
00.10 0
00 0.20
0000
⎤
⎥
⎥
⎦
c =
0.507 −1.10.707 0.283
t
90 3 Markov Chains
Thus we can simply write
s(2) = XD
2
c
=
0.23 0.29 0.20.28
t
s(5) = XD
5
c
=
0.22 0.28 0.20.3
t
s(20) = XD
20
c
=
0.22 0.28 0.20.3
t
We see that the distribution vector settles down to a fixed value after a few it-
erations. The above results could be confirmed by directly finding the distribution
vectors using the usual formula
s(n) = P
n
s(0)
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 coefficient c such that the end result s(n) is purely real.
Example 3.16 A Markov chain has the transition matrix
P =
⎡
⎣
0.10.40.2
0.10.40.6
0.80.20.2
⎤
⎦
Check to see if this matrix has distinct eigenvalues. If so,
(a) Expand the following initial distribution vector
s(0) =
100
t
in terms of the eigenvectors of P.
(b) Find the value of s(3).
The eigenvalues of P are
λ
1
= 1
λ
2
=−0.15 + j0.3122
λ
3
=−0.15 − j0.3122
3.12 Finding s (n) by Diagonalizing P 91
We see that complex eigenvalues appear as complex conjugate pairs. The eigen-
vectors corresponding to these eigenvalues are
X =
⎡
⎣
−0.4234 −0.1698 + j0.3536 −0.1698 − j0.3536
−0.6726 −0.5095 − j0.3536 −0.5095 + j0.3536
−0.6005 0.6794 0.6794
⎤
⎦
We see that the eigenvectors corresponding to the complex eigenvalues appear
also as complex conjugate pairs. Therefore, we can expand s(0) in terms of the
corresponding eigenvectors.
s(0) = Xc
where c given by
c =
−5863 −0.2591 − j0.9312 −0.2591 + j0.9312
t
We see that the expansion coefficients corresponding to the complex eigenvectors
appear as complex conjugate pairs also. 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) = XD
3
c =
0.2850 0.3890 0.3260
t
3.12 Finding s(n) by Diagonalizing P
According to [4], matrix P is diagonalizable when it has m distinct eigenvalues and
we can write
P = XDX
−1
(3.60)
where X is the matrix whose columns are the eigenvectors of P, and D is a diago-
nal matrix whose diagonal elements are the eigenvalues arranged according to the
ordering of the columns of X. MATLAB provides a very handy function for finding
the matrices X and D using the single command
[X, D] = eig(P)
It does not matter here whether the columns of X are normalized or not since any
scaling factor in X will be cancelled by X
−1
. MATLAB also offers a very simple
function for inverting a matrix by using the command
X
inv = inv(X)
92 3 Markov Chains
We can calculate P
2
as
P
2
=
XDX
−1
×
XDX
−1
(3.61)
= XD
2
X
−1
(3.62)
In general we have
P
n
= XD
n
X
−1
(3.63)
where
D
n
=
⎡
⎢
⎢
⎢
⎢
⎢
⎣
λ
n
1
00··· 0
0 λ
n
2
0 ··· 0
00λ
n
3
··· 0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
000··· λ
n
m
⎤
⎥
⎥
⎥
⎥
⎥
⎦
(3.64)
It is easy therefore to find s(n) for any value of n by simply finding D
n
and then
evaluate the simple matrix multiplication expression
s(n) = P
n
s(0)
= XD
n
X
−1
s(0) (3.65)
3.12.1 Comparing Diagonalization with Expansion of s(0)
Diagonalizing the matrix P is equivalent to the previous technique of expanding s(0)
in terms of the eigenvectors of P. As a proof, consider calculating s(n) using both
techniques.
Using diagonalization technique, we have
s(n) = P
n
s(0) (3.66)
= XD
n
X
−1
s(0) (3.67)
Using the expansion of s(0) technique in (3.41) we know that
s(0) = Xc (3.68)
By substituting this into (3.67) we get
s(n) = XD
n
X
−1
Xc
= XD
n
c (3.69)
3.12 Finding s (n) by Diagonalizing P 93
Now the value for c = X
−1
s(0) can be found to yield
s(n) = XD
n
X
−1
s(0) (3.70)
This last expression for s(n) is identical to (3.67). Thus we see that the two tech-
niques are equivalent. Before we finish this section we state the following lemma
which will prove useful later on.
Lemma 3.3 Assume the first column of X is the normalized eigenvector corre-
sponding to eigenvalue λ = 1. Then the matrix X
−1
will have ones in its first row.
In general, if the first column of X is not normalized, then the theorem would
state that the matrix X
−1
will have the value 1/σ (x
1
) in the elements in its first row.
Proof Assume Y = X
−1
then we can write
X ×Y = I (3.71)
where I is the m × m unit matrix. Let us express the above equation in terms of
the elements of the two matrices X and Y:
⎡
⎢
⎢
⎢
⎣
x
11
x
12
··· x
1m
x
21
x
22
··· x
2m
.
.
.
.
.
.
.
.
.
.
.
.
x
m1
x
m2
··· x
mm
⎤
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎣
y
11
y
12
··· y
1m
y
21
y
22
··· y
2m
.
.
.
.
.
.
.
.
.
.
.
.
y
m1
y
m2
··· y
mm
⎤
⎥
⎥
⎥
⎦
= I (3.72)
The element at location (i, j) is obtained from the usual formula
m
k=1
x
ik
y
kj
= δ(i − j) (3.73)
where δ(i − j) is the Dirac delta function which is one only when the argument is
zero, i.e. when i = j. The function is zero for all other values of i and j.
The sum of the j-th column on both sides of (3.71) and (3.73) is given by
m
i=1
m
k=1
x
ik
y
kj
= 1 (3.74)
Now reverse the order of summation on the left-hand side (LHS) of the above
equation
m
k=1
y
kj
m
i=1
x
ik
= 1 (3.75)
94 3 Markov Chains
Because of the properties of the eigenvectors in Theorem 3.3 on page 79 and
Theorem 3.4 on page 79, the second summation becomes
m
k=1
y
kj
δ(k − 1) = 1 (3.76)
δ(k − 1) expresses the fact that only the sum of the first column of matrix X
evaluates to 1. All other columns add up to zero. Thus the above equation becomes
y
1 j
= 1 (3.77)
This proves that the elements of the first row of matrix X
−1
must be all ones.
3.13 Expanding P
n
in Terms of Its Eigenvalues
We shall find that expanding P
n
in terms of the eigenvalues of P will give us addi-
tional insights into the transient behavior of Markov chains. Equation (3.63) related
P
n
to the n-th powers of its eigenvalues as
P
n
= XD
n
X
−1
(3.78)
Thus we can express P
n
in the above equation in the form
P
n
= λ
n
1
A
1
+λ
n
2
A
2
+···+λ
n
m
A
m
(3.79)
Assume that λ
1
= 1 and all other eigenvalues have magnitudes lesser than unity
(fractions) because P is column stochastic. In that case, the above equation becomes
P
n
= A
1
+λ
n
2
A
2
+···+λ
n
m
A
m
(3.80)
This shows that as time progresses, n becomes large and the powers of λ
n
i
will
quickly decrease. The main contribution to P
n
will be due to A
1
only.
The matrices A
i
can be determined from the product
A
i
= XY
i
X
−1
(3.81)
where Y
i
is the selection matrix which has zeros everywhere except for element
y
ii
= 1.
For a 3 × 3 matrix, we can write
P
n
=
x
1
x
2
x
3
⎡
⎣
λ
n
1
00
0 λ
n
2
0
00λ
n
3
⎤
⎦
x
1
x
2
x
3
−1
(3.82)