Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
Problems 115
3.18
0.80.5
0.30.5
3.19
−0.10.8
−0.90.2
3.20
1.20.8
−0.20.2
3.21
⎡
⎣
100
010
001
⎤
⎦
3.22
0.40.4
0.60.3
3.23
⎡
⎣
0.10.3
0.20.5
0.70.2
⎤
⎦
3.24
⎡
⎣
010
100
001
⎤
⎦
3.25
0.80.30.5
0.20
.70.5
116 3 Markov Chains
3.26
⎡
⎢
⎢
⎣
0.70.30.50.3
0.10.10.20.3
0.10.30.10.3
0.10.30.20.3
⎤
⎥
⎥
⎦
3.27 Choose any column stochastic matrix from the matrices in the above prob-
lems, or choose one of your own, then reduce the value of one of its nonzero
elements slightly (keeping the matrix nonnegative of course). In that way, the
matrix will not be a column stochastic matrix any longer. Observe the change
in the maximum eigenvalue and the corresponding eigenvector.
3.28 Assume a source is sending packets on a wireless channel. The source could
be in one of three states: (1) idle state. (2) successful transmission state where
source is active and transmitted packet is received without errors. (3) erro-
neous transmission state where source is active and transmitted packet is re-
ceived with errors.
Assume the probability the source switches from idle to active is a and the
probability that the source successfully transmits a packet is s. Draw a state
transition diagram indicating the transition probabilities between states and
find the transition matrix.
Transient Behavior
3.29 For problem 3.2 how much share of the traffic will be maintained by each hub
after one day and after two days?
3.30 For problem 3.3 how much share of the traffic will be maintained by each floor
after one hour and after two hours?
3.31 The transition matrix for a Markov chain is given by
P =
0.80.1
0.20.9
(a) Given that the system is in state s
0
, what is the probability the next state
will be s
1
?
(b) For the initial distribution vector s(0) find s(1):
s(0) =
0.40.6
t
Problems 117
3.32 The transition matrix for a Markov chain is given by
P =
⎡
⎣
0.50.30.5
00.30.25
0.50.40.25
⎤
⎦
(a) What does the entry p
01
represent?
(b) Given that the system is in state s
0
, what is the probability the next state
will be s
1
?
(c) For the initial distribution vector s(0)
s(0) =
0.40.60
t
find s(1).
3.33 Given a transition matrix
P =
0.20.7
0.80.3
what is the probability of making a transition to state s
0
given that we are in
state s
1
?
3.34 Assume a hypothetical city where yearly computer buying trends indicate that
95% of the people who own a desktop computer will purchase a desktop and
the rest will switch to laptops. On the other hand, 60% of laptop owners will
continue to buy laptops and the rest will switch to desktops. At the begin-
ning of the year 65% of the computer owners had desktops. What will be the
percentages of desktop and laptop owners after one, two, and ten years?
3.35 Assume the state of a typical winter day in Cairo to be sunny, bright, or partly
cloudy. Observing the weather pattern reveals the following. When today is
sunny, tomorrow will be bright with probability 80%, and partly cloudy with
probability 20%. When today is bright, tomorrow will be sunny with proba-
bility 60%, bright with probability 30%, and partly cloudy with probability
10%. When today is partly cloudy, tomorrow will be sunny with probability
30%, bright with probability 40%, and partly cloudy with probability 30%.
Assume state 1 represents a sunny day, state 2 represents a bright day, and
state 3 represents a partly cloudy day.
(a) Construct a state transition matrix.
(b) What is the probability that it will be partly cloudy tomorrow given that it
is sunny today?
(c) What is the probability that it will be bright day after tomorrow given that
is bright today?
3.36 Assume a gambler plays double or nothing game using a fair coin and starting
with one dollar.
118 3 Markov Chains
(a) Draw a state diagram for the amount of money with the gambler and ex-
plain how much money corresponds to each state.
(b) Derive the transition matrix.
(c) What is the probability that the gambler will have more than $500 after
playing the game for 10 tosses of the coin?
3.37 Suppose you play the following game with a friend, both of you start with $2.
The game starts when the coin is filipped. If the coin comes up heads, you win
$1. If the coin comes up tails, you lose $1. The game ends when either of you
do not have anymore money.
(a) Construct a Markov transition diagram and transition matrix for this game.
(b) Find the eigenvectors and eigenvalues for this matrix.
(c) What is the initial probability vector when you start the game?
3.38 Assume you are playing a truncated form of the snakes and ladder game using
a fair coin instead of the dice. The number of squares is assumed to be 10,
to make things simple, and each player starts at the first square (we label it
square 1 and the last square is labeled 10). Tails mean the player advances one
square and heads mean the player advances by two squares. To make the game
interesting, some squares have special transitions according to the following
rules which indicate the address on the next square upon the flip of the coin.
Square Heads Tails
242
361
572
894
Write the initial distribution vector and the transition matrix. What will be
the distribution vector be after 5 flips of the coin? What are the chances of a
player winning the game after 10 flips?
3.39 Assume a particle is allowed to move on a one-dimensional grid and starts at
the middle. The probability of the particle moving to the right is p and to the
left is q, where p +q = 1. Assume the size of the gird to extend from 1 to N,
with N assumed odd. Assume that at the end points of the grid, the particle is
reflected back with probability 1. Draw a Markov transition diagram and write
down the corresponding transition matrix. Assume p = 0.6 and q = 0.4, and
N = 7. Plot the most probable position for the particle versus time.
3.40 A parrot breeder has birds of two colors, blue and green. She finds that 60%
of the males are blue if the father was blue and 80% of the males are green
if the father was green. Write down the transition matrix for the males parrot.
What is the probability that a blue male has a blue male after two and three
generations?
Problems 119
3.41 A virus can mutate between N different states (typically N = 20). In each
generation it either stays the same or mutates to another sate. Assume that
the virus is equally likely to change state to any of the N states. You can
reduce the size of the transition matrix P from N ×N to 2×2 only by studying
two sates: original state and “others” state which contains all other mutations.
Construct the transition matrix describing the two-state Markov chain. What
is the probability that in the n-th generation it will return to its original state?
3.42 Consider the stock portfolio Problem 3.7.
(a) What will be the performance of the portfolio after one, two, and ten
years?
(b) Investigate the performance of the conservative portfolio that starts with
the following percentage distribution of stocks s(0) =
0.50.50
t
over the same period of time as in (a) above.
(c) Investigate the performance of a “very aggressive” portfolio that starts
with the following percentage distribution of stocks s(0) =
001
t
over the same period of time as in (a) above.
(d) Compare the long-term performance of the conservative and aggressive
portfolios.
3.43 A hidden Markov chain model can be used as a waveform generator. Your task
is to generate random waveforms using the following procedure.
(1) Define a set of quantization levels Q
1
, Q
2
, ···, Q
m
for the signal values.
(2) Define a m ×m Markov transition matrix for the system. Choose your own
transition probabilities for the matrix.
(3) Choose an initial state vector from the set with only one nonzero entry
chosen at random from the set of quantization levels
s(0) =
0 ··· 010··· 0
t
If that single element is in position k, then the corresponding initial
output value is Q
k
.
(4) Evaluate the next state vector using the iteration
s(i) = Ps(i − 1)
(5) Generate the cumulative function
F
j
(i) =
j
k=1
s
k
(i)
(6) Generate a random variable x using the uniform distribution and estimate
the index j for the output Q
j
that satisfies the inequality
F
j−1
(i) < x ≤ F
j
(i)
(7) Repeat 4.
120 3 Markov Chains
Finding P
n
by Expanding s(0)
3.44 In Section 3.11 we expressed s(0) in terms of the eigenvectors of the transition
matrix according to (3.41). Prove that if a pair of the eigenvectors is a complex
conjugate pair, then the corresponding coefficients of c are also a complex
conjugate pair.
3.45 The given transition matrix
P =
⎡
⎣
0.10.40.6
0.10.40.2
0.80.20.2
⎤
⎦
has distinct eigenvalues. Express the initial state vector
s(0) =
010
t
in terms of its eigenvectors, then find the distribution vector for n = 4.
3.46 The given transition matrix
P =
⎡
⎢
⎢
⎣
0.10.40.40.1
0.10.40.20.1
0.10.10.20.7
0.70.10.20.1
⎤
⎥
⎥
⎦
has distinct, but complex, eigenvalues. Express the initial state vector
s(0) =
0100
t
in terms of its eigenvectors, then find the distribution vector for n = 5.
3.47 The given transition matrix
P =
⎡
⎢
⎢
⎣
0.10.40.10.8
0.10.40.50
0.30.10.40.1
0.50.10.00.1
⎤
⎥
⎥
⎦
has distinct, but complex, eigenvalues. Express the initial state vector
s(0) =
0100
t
in terms of its eigenvectors, then find the distribution vector for n = 5.
References 121
3.48 The given transition matrix
P =
⎡
⎣
0.50.30.5
0.50.30
00.40.5
⎤
⎦
has distinct, but complex, eigenvalues. Express the initial state vector
s(0) =
010
t
in terms of its eigenvectors, then find the distribution vector for n = 7.
3.49 The given transition matrix
P =
0.50.75
0.50.25
has distinct, and real, eigenvalues. Express the initial state vector
s(0) =
01
t
in terms of its eigenvectors, then find the distribution vector for n = 7.
3.50 The given transition matrix
P =
0.90.75
0.10.25
has distinct, and real, eigenvalues. Express the initial state vector
s(0) =
01
t
in terms of its eigenvectors, then find the distribution vector for n = 7.
References
1. J. Warland and R. Varaiya High-Performance Communication Networks, Moragan Kaufmann,
San Francisco, 2000.
2. M. E. Woodward, Communication and Computer Networks, IEEE Computer Society Press,
Los Alamitos, CA, 1994.
3. W.J. Stewart, Introduction to Numerical Solutions of Markov Chains, Princeton University
Press, Princeton, New Jersey, 1994.
4. R. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge,
England, 1985.
5. M. Gardner, Aha! Insight, Scientific American, Inc./W.H.Freeman and Company, New York
City, 1978.
Chapter 4
Markov Chains at Equilibrium
4.1 Introduction
In this chapter we will study the long-term behavior of Markov chains. In other
words, we would like to know the distribution vector s(n) when n →∞. The state
of the system at equilibrium or steady state can then be used to obtain performance
parameters such as throughput, delay, loss probability, etc.
4.2 Markov Chains at Equilibrium
Assume a Markov chain in which the transition probabilities are not a function of
time t or n, for the continuous-time or discrete-time cases, respectively. This defines
a homogeneous Markov chain. At steady state as n →∞the distribution vector s
settles down to a unique value and satisfies the equation
Ps= s (4.1)
This is because the distribution vector value does not vary from one time instant
to another at steady state. We immediately recognize that s in that case is an eigen-
vector for P with corresponding eigenvalue λ = 1. We say that the Markov chain
has reached its steady state when the above equation is satisfied.
4.3 Significance of s at “Steady State”
Equation (4.1) indicates that if s is the present value of the distribution vector, then
after one time step the distribution vector will be s still. The system is now in equilib-
rium or steady state. The reader should realize that we are talking about probabilities
here.
At steady state the system will not settle down to one particular state, as one
might suspect. Steady state means that the probability of being in any state will not
change with time. The probabilities, or components, of the vector s are the ones that
F. Gebali, Analysis of Computer and Communication Networks,
DOI: 10.1007/978-0-387-74437-7
4,
C
Springer Science+Business Media, LLC 2008
123
124 4 Markov Chains at Equilibrium
are in steady state. The components of the transition matrix P
n
will also reach their
steady state. The system is then said to be in steady state.
Assume a five-state system whose equilibrium or steady-state distribution
vector is
s =
s
1
s
2
s
3
s
4
s
5
t
(4.2)
=
0.20.10.40.10.2
t
(4.3)
Which state would you think the system will be in at equilibrium? The answer
is, the system is in state s
1
with probability 20%, or the system is in state s
2
with
probability 10%, etc. However, we can say that at steady state the system is most
probably in state s
3
since it has the highest probability value.
4.4 Finding Steady-State Distribution Vector s
The main goal of this chapter is to find s for a given P. Knowledge of this vector
helps us find many performance measures for our system such as packet loss proba-
bility, throughput, delay, etc. The technique we choose for finding s depends on the
size and structure of P.
Since the steady-state distribution is independent of the initial distribution vector
s
(
0
)
, we conclude therefore that P
n
approaches a special structure for large values
of n. In this case we find that the columns of P
n
, for large values of n, will all be
identical and equal to the steady-state distribution vector s. We could see that in
Examples 3.11 on page 82 and Example 3.20 on page 100.
Example 4.1 Find the steady-state distribution vector for the given transition
matrix by
(a) calculating higher powers for the matrix P
n
(b) calculating the eigenvectors for the matrix.
P =
⎡
⎣
0.20.40.5
0.80 0.5
00.60
⎤
⎦
The given matrix is column stochastic and hence could describe a Markov chain.
Repeated multiplication shows that the entries for P
n
settle down to their stable
values.
4.5 Techniques for Finding s 125
P
2
=
⎡
⎣
0.36 0.38 0.30
0.16 0.62 0.40
0.48 0 0.30
⎤
⎦
P
5
=
⎡
⎣
0.3648 0.3438 0.3534
0.4259 0.3891 0.3970
0.2093 0.2671 0.2496
⎤
⎦
P
10
=
⎡
⎣
0.3535 0.3536 0.3536
0.4042 0.4039 0.4041
0.2424 0.2426 0.2423
⎤
⎦
P
20
=
⎡
⎣
0.3535 0.3535 0.3535
0.4040 0.4040 0.4040
0.2424 0.2424 0.2424
⎤
⎦
The entries for P
20
all reached their stable values. Since all the columns of P
20
are identical, the stable-distribution vector is independent of the initial distribution
vector. (Could you prove that? It is rather simple.) Furthermore, any column of P
20
gives us the value of the equilibrium distribution vector.
The eigenvector corresponding to unity eigenvalue is found to be
s =
0.3535 0.4040 0.2424
t
Notice that the equilibrium distribution vector is identical to the columns of the
transition matrix P
20
.
4.5 Techniques for Finding s
We can use one of the following approaches for finding the steady-state distribu-
tion vector s. Some approaches are algebraic while the others rely on numerical
techniques.
1. Repeated multiplication of P to obtain P
n
for high values of n.
2. Eigenvector corresponding to eigenvalue λ = 1forP.
3. Difference equations.
4. Z-transform (generating functions).
5. Direct numerical techniques for solving a system of linear equations.
6. Iterative numerical techniques for solving a system of linear equations.
7. Iterative techniques for expressing the states of P in terms of other states.
Which technique is easier depends on the structure of P. Some rough guidelines
follow.
1. The repeated multiplication technique in 1 is prone to numerical roundoff er-
rors and one has to use repeated trials until the matrix entries stop changing for
increasing values of n.