## Transcribed Text

Exercise 1 A transition matrix is doubly stochastic if each column sum is 1. Find the stationary
distribution for a doubly stochastic chain with M states.
Exercise 2 Trials are performed in sequence. If the last two trials were successes, then the next
trial is a success with probability 0.8; otherwise the next trial is a success with probability 0.5. In
the long run, what proportion of trials are successes?
Exercise 3 Let {Xn} be a regular finite state Markov chain with transition matrix P and stationary distribution w. Define the process {Yn} by Yn = (Xn−1, Xn). Show that {Yn} is a Markov
chain, and compute
limn→∞
P(Yn = (i, j)) (1)
Exercise 5 Consider the following transition probability matrix for a Markov chain on 5 states:
P =
0.5 0.3 0 0 0.2
0 0.5 0 0 0.5
0 0.4 0.4 0.2 0
0.3 0 0.2 0 0.5
0.5 0.2 0 0 0.3
c). Compute the expected number of steps needed to first return to state 1, conditioned on starting in
state 1.
d). Compute the expected number of steps needed to first reach any of the states {1, 2, 5}, conditioned on starting in state 3.
Exercise 7 [Snell and Grinstead] A city is divided into three areas 1, 2, 3. It is estimated that
amounts u1, u2, u3 of pollution are emitted each day from these three areas. A fraction qij of the
pollution from region i ends up the next day at region j. A fraction qi = 1 −
P
j
qij > 0 escapes
into the atmosphere. Let w
(n)
i
be the amount of pollution in area i after n days.
(a) Show that w
(n) = u + uQ + · · · + uQn−1
.
(b) Show that w
(n) → w.
(c) Show how to determine the levels of pollution u which would result in a prescribed level w.
Exercise 8 [The gambler’s ruin] At each play a gambler has probability p of winning one unit and
probability q = 1−p of losing one unit. Assuming that successive plays of the game are independent,
what is the probability that, starting with i units, the gambler’s fortune will reach N before reaching
0? [Hint: define Pi to be the probability that the gambler’s fortune reaches N before reaching 0
conditioned on starting in state i. By conditioning on the first step derive a recursion relation
between Pi
, Pi+1 and Pi−1.]
Page 422
18. Assume that a student going to certain four-year medical school in northern New England has, each year, a probability q of unking out, a probability r of having to repeat
the year, and a probability p of moving on to the next year (in the fourth year, moving
on means graduating).
a) Form a transition matrix for this process taking as states F, 1, 2, 3, 4 and G where F
stands for unking out and G for graduating, and the other states represent the year of
study.
b) For the case q = .1, r = .2 and p = .7 nd the time a beginning student can expect to
be in the second year. How long should this student expect to be in medical school?
c) Find the probability that this beginning student will graduate.
Page 442
26. Let P be the transition matrix of an r-state ergodic chain. Prove that, if the diagonal
entries pii are positive, then the chain is regular.
27. Prove that if P is the transition matrix of an ergodic chain, then (1/2)(I + P) is
the transition matrix of a regular chain.
Page 466
1. Consider the Markov chain with transition matrix
P =
1/2 1/2
1/4 3/4
Find the fundamental matrix z for this chain. Compute the mean rst passage matrix
using Z.
2. A study of the strengths of Ivy League football teams shows that if a school has
a strong team one year it is equally likely to have a strong team or average team next
year; if it has an average team, half the time it is average next year, and if it changes it is
just as likely to become strong as weak; if it is weak it has 2/3 probability or remaining
so and 1/3 of becoming average.
a) A school has a strong team. On the average, how long will it be before it has another
strong team?
b) A school has a weak team; how long (on the average) must the alumni wait for a strong
team?
16. Let P be the transition matrix of an ergodic Markov chain. Show that
(I + P + . . . + P
n−1
)(I − P + W) = I − P
n + nW,
and from this show that
I + P + . . . Pn−1
n
→ W,
as n → ∞

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.