Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
136 4 Markov Chains at Equilibrium
Example 4.5 Use the z-transform technique to find the equilibrium distribution vec-
tor for the Markov chain whose transition matrix is
P =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
0.5714 0.4082 0 0 0 ···
0.2857 0.3673 0.4082 0 0 ···
0.1429 0.1837 0.3673 0.4082 0 ···
00.0408 0.1837 0.3673 0.4082 ···
000.0408 0.1837 0.3673 ···
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
We have the z-transforms of A(z) and B(z)as
A(z) = 0.5714 +0.2857z
−1
+0.1429z
−2
B(z) = 0.4082 +0.3673z
−1
+0.1837z
−2
+0.0408z
−3
Differentiation of the above two expressions gives
A(z)
=−0.2857z
−2
−0.2857z
−3
B(z)
=−0.3673z
−2
−0.3673z
−3
−0.1224z
−4
By substituting z
−1
= 1 in the above expressions, we get
A(1)
=−0.5714
B(1)
=−0.8571
By using (4.38) we get the probability that the queue is empty
s
0
=
1 + B
(1)
1 + B
(1) − A
(1)
= 0.2
From (4.34) we can write
S(z) =
0.0816 −0.0408z
−1
−0.0204z
−2
−0.0204z
−3
0.4082 −0.6326z
−1
+0.1837z
−2
+0.0408z
−3
We can convert the polynomial expression for S(z) into a partial-fraction expan-
sion (residues) using the MATLAB command residue:
b = [0.0816, -0.0408, -0.0204, -0.0204];
a = [0.4082, -0.6327, 0.1837, 0.0408];
[r,p,c] = residue(b,a)
r=
0.0000
0.2574
-0.0474
4.9 Finding s Using Forward- or Back-Substitution 137
p=
1.0000
0.6941
-0.0474
c=
0.2000
where the column vectors r, p, and c give the residues, poles, and direct terms,
respectively. Thus we have
s
0
= c = 0.2
which confirms the value obtained earlier. For i ≥ 1wehave
s
i
=
j
r
j
p
j
i−1
Thus the distribution vector at steady state is given by
s =
0.2100 0.1855 0.1230 0.0860 0.0597 ···
t
As as a check, we generated the first 50 components of s and ensured that their sum
equals unity.
4.9 Finding s Using Forward- or Back-Substitution
This technique is useful when the transition matrix P is a lower Hessenberg matrix
and the elements in each diagonal are not equal. In such matrices the elements p
ij
=
0for j > i +1. The following example shows a lower Hessenberg matrix of order 6:
P =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
h
11
h
12
0000
h
21
h
22
h
23
000
h
31
h
32
h
33
h
34
00
h
41
h
42
h
43
h
44
h
45
0
h
51
h
52
h
53
h
54
h
55
h
56
h
61
h
62
h
63
h
64
h
65
h
66
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
(4.42)
This matrix describes the M
m
/M/1 queue in which a maximum of m packets
may arrive as will be explained in Chapter 7. At steady state the distribution vector
s satisfies
Ps = s (4.43)
and when P is lower Hessenberg we have
138 4 Markov Chains at Equilibrium
⎡
⎢
⎢
⎢
⎣
h
11
h
12
00···
h
21
h
22
h
23
0 ···
h
31
h
32
h
33
h
34
···
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
⎤
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎣
s
1
s
2
s
3
.
.
.
⎤
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎣
s
1
s
2
s
3
.
.
.
⎤
⎥
⎥
⎥
⎦
(4.44)
where we assumed our states are indexed as s
1
, s
2
, ... Forward substitution starts
with estimating a value for s
1
then proceeding to find s
2
, s
3
, etc. The first row gives
s
1
= h
11
s
1
+h
12
s
2
(4.45)
We assume an arbitrary value for s
1
= 1. Thus the above equation gives us a
value for s
2
s
2
=
(
1 − h
11
)
/h
12
(4.46)
We remind the reader again that s
1
= 1 by assumption. The second row gives
s
2
= h
21
s
1
+h
22
s
2
+h
23
s
3
(4.47)
By substituting the values we have so far for s
1
and s
2
, we get
s
3
=
(
1 − h
11
)(
1 − h
22
)
/
(
h
12
h
23
)
−h
21
/h
23
(4.48)
Continuing in this fashion, we can find all the states s
i
where i > 1.
To get the true value for the distribution vector s, we use the normalizing equation
m
i=1
s
i
= 1 (4.49)
Let us assume that the sum of the components that we obtained for the vector s
gives
m
i=1
s
i
= b (4.50)
then we must divide each value of s by b to get the true normalized vector that we
desire.
Backward substitution is similar to forward substitution but starts by assuming
a value for s
m
then we estimate s
m−1
, s
m−2
, etc. Obviously, backward substitution
applies only to finite matrices.
Example 4.6 Use forward substitution to find the equilibrium distribution vector s
for the Markov chain with transition matrix given by
4.9 Finding s Using Forward- or Back-Substitution 139
P =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
0.40.20000
0.30.35 0.2000
0.20.25 0.35 0.20 0
0.10.15 0.25 0.35 0.20
00.05 0.15 0.25 0.35 0.2
00 0.05 0.20.45 0.8
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
Assume s
1
= 1. The distribution vector must satisfy the equation
s =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
0.40.20000
0.30.35 0.2000
0.20.25 0.35 0.20 0
0.10.15 0.25 0.35 0.20
00.05 0.15 0.25 0.35 0.2
00 0.05 0.20.70.8
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
1
s
2
s
3
s
4
s
5
s
6
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
1
s
2
s
3
s
4
s
5
s
6
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
The first row gives us a value for s
2
= 3. Continuing, with successive rows,
we get
s
3
= 8.25
s
4
= 22.0625
s
5
= 58.6406
s
6
= 156.0664
Summing the values of all the components gives us
6
j=1
s
j
= 249.0195 (4.51)
Thus the normalized distribution vector is
s =
0.0040 0.0120 0.0331 0.0886 0.2355 0.6267
t
(4.52)
140 4 Markov Chains at Equilibrium
4.10 Finding s Using Direct Techniques
Direct techniques are useful when the transition matrix P has no special structure
but its size is small such that rounding errors
1
are below a specified maximum level.
In that case we start with the equilibrium equation
Ps= s (4.53)
where s is the unknown n-component distribution vector. This can be written as
(
P −I
)
s = 0 (4.54)
As= 0 (4.55)
which describes a homogeneous system of linear equations with A = P −I. The
rank of A is n − 1 since the sum of the columns must be zero. Thus, there are
many possible solutions to the system and we need an extra equation to get a unique
solution.
The extra equation that is required is the normalizing condition
m
i=1
s
i
= 1 (4.56)
where we assumed our states are indexed as s
1
, s
2
, ..., s
m
. We can delete any row
matrix A in (4.55) and replace it with (4.56). Let us replace the last row with (4.56).
In that case we have the system of linear equations
⎡
⎢
⎢
⎢
⎢
⎢
⎣
a
11
a
12
··· a
1m
a
21
a
22
··· a
2m
.
.
.
.
.
.
.
.
.
.
.
.
a
m−1,1
a
m−1,2
··· a
m−1,m
11··· 1
⎤
⎥
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎢
⎢
⎣
s
1
s
2
.
.
.
s
m−1
s
m
⎤
⎥
⎥
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎢
⎢
⎣
0
0
.
.
.
0
1
⎤
⎥
⎥
⎥
⎥
⎥
⎦
(4.57)
This gives us a system of linear equations whose solution is the desired steady-
state distribution vector.
Example 4.7 Find the steady-state distribution vector for the state transition matrix
P =
⎡
⎣
0.40.20
0.10.50.6
0.50.30.4
⎤
⎦
1
Rounding errors occur due to finite word length in computers. In floating-point arithmetic,
rounding errors occur whenever addition or multiplication operations are performed. In fixed-point
arithmetic, rounding errors occur whenever multiplication or shift operations are performed.
4.11 Finding s Using Iterative Techniques 141
First, we have to obtain matrix A = P −I
A =
⎡
⎣
−0.60.20
0.1 −0.50.6
0.50.3 −0.6
⎤
⎦
Now we replace the last row in A with all ones to get
A =
⎡
⎣
−0.60.20
0.1 −0.50.6
111
⎤
⎦
The system of linear equations we have to solve is
⎡
⎣
−0.60.20
0.1 −0.50.6
111
⎤
⎦
⎡
⎣
s
1
s
2
s
3
⎤
⎦
=
⎡
⎣
0
0
1
⎤
⎦
The solution for s is
s =
0.1579 0.4737 0.3684
t
4.11 Finding s Using Iterative Techniques
Iterative techniques are useful when the transition matrix P has no special structure
and its size is large such that direct techniques will produce too much rounding er-
rors. Iterative techniques obtain a solution to the system of linear equations without
arithmetic rounding noise. The accuracy of the results is limited only by machine
precision. We enumerate below three techniques for doing the iterations. These tech-
niques are explained in more detail in Appendix D.
1. Successive overrelaxation
2. Jacobi iterations
3. Gauss-Seidel iterations.
Basically, the solution is obtained by first assuming a trial solution, then this is
improved through successive iterations. Each iteration improves the guess solution
and an answer is obtained when successive iterations do not result in significant
changes in the answer.
142 4 Markov Chains at Equilibrium
4.12 Balance Equations
In steady state the probability of finding ourselves in state s
i
is given by
s
i
=
j
p
ij
s
j
(4.58)
The above equation is called the balance equation because it provides an expres-
sion for each state of the queue at steady state.
From the definition of transition probability, we can write
j
p
ji
= 1 (4.59)
which is another way of saying that the sum of all probabilities of leaving state i is
equal to one. From the above two equations we can write
s
i
j
p
ji
=
j
p
ij
s
j
(4.60)
Since s
i
is independent of the index of summation on the LHS, we can write
j
p
ji
s
i
=
j
p
ij
s
j
(4.61)
Now the LHS represents all the probabilities of flowing out of state i. The RHS
represents all the probabilities of flowing into state i. The above equation describes
the flow balance for state i.
Thus we proved that in steady state, the probability of moving out of a state
equals the probability of moving into the same state. This conclusion will help us
derive the steady-state distributions in addition to the other techniques we have dis-
cussed above.
Problems
Finding s Using Eigenvectors
4.1 Assume s is the eigenvector corresponding to unity eigenvalue for matrix P.
Prove that this vector cannot have a zero component in it if P does not have any
zero elements.
Problems 143
4.2 Find the steady-state distribution vector corresponding to the unity eigenvalue
for the following transition matrix.
P =
⎡
⎣
0.45 0.20.5
0.50.20.3
0.05 0.60.2
⎤
⎦
4.3 Find the steady-state distribution vector corresponding to the unity eigenvalue
for the following transition matrix.
P =
⎡
⎣
0.29 0.46 0.4
0.40.45 0.33
0.31 0.09 0.27
⎤
⎦
4.4 Find the steady-state distribution vector corresponding to the unity eigenvalue
for the following transition matrix.
P =
⎡
⎣
0.33 0.48 0.41
0.30.01 0.48
0.37 0.51 0.11
⎤
⎦
4.5 Find the steady-state distribution vector corresponding to the unity eigenvalue
for the following transition matrix.
P =
⎡
⎣
0.33 0.51 0.12
0
.24 0.17 0.65
0.43 0.32 0.23
⎤
⎦
4.6 Find the steady-state distribution vector corresponding to the unity eigenvalue
for the following transition matrix.
P =
⎡
⎣
0.03 0.19 0.07
0.44 0.17 0.53
0.53 0.64 0.4
⎤
⎦
4.7 Find the steady-state distribution vector corresponding to the unity eigenvalue
for the following transition matrix.
P =
⎡
⎣
0.56 0.05 0.2
0.14 0.57 0.24
0.30.38 0.56
⎤
⎦
144 4 Markov Chains at Equilibrium
4.8 Find the steady-state distribution vector corresponding to the unity eigenvalue
for the following transition matrix.
P =
⎡
⎢
⎢
⎣
0.08 0.19 0.07
0.04 0.17 0.53
0.18 0.17 0.53
0.70.64 0.4
⎤
⎥
⎥
⎦
4.9 Find the steady-state distribution vector corresponding to the unity eigenvalue
for the following transition matrix.
P =
⎡
⎢
⎢
⎢
⎢
⎣
0.12 0.06 0.42 0.10.09
0.18 0.14 0.03 0.14 0.01
0.23 0.33 0.17 0.14 0.32
0.26 0.32 0.38 0.43 0.18
0.21 0.15 0 0.19 0.
4
⎤
⎥
⎥
⎥
⎥
⎦
Finding s by Difference Equations
4.10 A queuing system is described by the following transition matrix:
P =
⎡
⎢
⎢
⎢
⎢
⎣
0.80.50 0 0
0.20.30.50 0
00.20.30.50
000.20.30.5
0000.20.5
⎤
⎥
⎥
⎥
⎥
⎦
(a) Find the steady-state distribution vector using the difference equations ap-
proach.
(b) What is the probability that the queue is full?
4.11 A queuing system is described by the following transition matrix.
P =
⎡
⎢
⎢
⎢
⎢
⎣
0.30.20 0 0
0.70.10.20 0
00.70.10.20
000.70.10.2
0000.70.8
⎤
⎥
⎥
⎥
⎥
⎦
(a) Find the steady-state distribution vector using the difference equations ap-
proach.
(b) What is the probability that the queue is full?
Problems 145
4.12 A queuing system is described by the following transition matrix.
P =
⎡
⎢
⎢
⎢
⎢
⎣
0.90.10 0 0
0.10.80.10 0
00.10.80.10
000.10.80.1
0000.10.9
⎤
⎥
⎥
⎥
⎥
⎦
(a) Find the steady-state distribution vector using the difference equations ap-
proach.
(b) What is the probability that the queue is full?
4.13 A queuing system is described by the following transition matrix.
P =
⎡
⎢
⎢
⎢
⎢
⎣
0.75 0.25 0 0 0
0.25 0.50.25 0 0
00.25 0.50.25 0
000.25 0.50.25
0000.25 0.75
⎤
⎥
⎥
⎥
⎥
⎦
(a) Find the steady-state distribution vector using the difference equations ap-
proach.
(b) What is the probability that the queue is full?
4.14 A queuing system is described by the following transition matrix.
P =
⎡
⎢
⎢
⎢
⎢
⎣
0.60.20 0 0
0.20.40.20 0
0.20.20.40.20
00.20.20.40.2
000.20.40.8
⎤
⎥
⎥
⎥
⎥
⎦
(a) Find the steady-state distribution vector using the difference equations ap-
proach.
(b) What is the probability that the queue is full?
4.15 A queuing system is described by the following transition matrix.
P =
⎡
⎢
⎢
⎢
⎢
⎢
⎣
0.80.50 ···
0.20.30.5 ···
00.20.3 ···
000.2 ···
.
.
.
.
.
.
.
.
.
.
.
.
⎤
⎥
⎥
⎥
⎥
⎥
⎦
Find the steady-state distribution vector using the difference equations ap-
proach.