## Markov chain with a finite state space.

1. (10 points) Answer True/False the following questions and provide a brief justification.
Each problem is worth 2pts.
(a) Consider a Markov chain Y1, Y2, · · · on the state space {0, 1, 2, · · · } and define the
process Xn = max{Y1, · · · , Yn} (running maximum) for n ≥ 1. Then, (Xn) is a
Markov process.
(b) If there are no transient states, then the chain is irreducible.
(c) Let (Xn) be a Markov chain with a finite state space. If number 1 is a simple
eigenvalue of the transition matrix P and all other eigenvalues lie strictly inside the
unit disk, then the chain is irreducible.
(d) Let (Xn) be an irreducible Markov chain with a countable state space. Define
Tx,y = min{n ≥ 0 : Xn = y, X0 = x} to be the minimal transition time from x to y.
If ETx,y < ∞ for any x 6= y, then the Markov chain is positive recurrent. (e) Consider the branching process (Xn) with offspring distribution p0, p1, · · · . If p0 >
1
2
,
then the population will extinct with probability 1.
2. (10 points) A pilot flies every day between New York city (NYC )and Los Angeles (LA).
He owns 4 suitcases and brings one suitcase on a flight with probability p, otherwise he
travels without a suitcase (leaving the suitcase in NYC or LA). It might be that all
suitcases are at one city, the pilot is in the other one, and he needs a suitcase, then he
gets upset. In a long run, what is the probability that the pilot is upset?
3. (10 points) A cat and a mouse are living in a four room house (see picture below with
indicated passages). The mouse starts in the lower left room and wanders around,
choosing a door at random (with equal probability). If it comes to the room with the
cat, it will be eaten (cat is not moving). What is the probability that the mouse escapes
the house?
Cat
Mouse Outside
4. (10 points) A professor has two light bulbs in his garage. When both are burned out,
they are replaced, and the next day starts with two working light bulbs. Suppose that
when both are working, one of the two will go out with probability .02 (each has probability .01 and we ignore the possibility of losing two on the same day). However, when
only one is there, it will burn out with probability .05. What is the expected time
between light bulb replacements?
5. (10 points) Six children (Dick, Helen, Joni, Mark, Sam, and Tony) play catch. If Dick
has the ball he is equally likely to throw it to Helen, Mark, Sam, and Tony. If Helen
has the ball she is equally likely to throw it to Dick, Joni, Sam, and Tony. If Sam has
the ball he is equally likely to throw it to Dick, Helen, Mark, and Tony. If either Joni
or Tony gets the ball, they keep throwing it to each other. If Mark gets the ball he runs
away with it.
6. Classify the states of the chain.
7. Suppose Dick has the ball at the beginning of the game. What is the probability
Mark will end up with it?
8. (10 points) Consider a random walk with absorbing boundaries on the state space {0, 1, 2, 3},
that is,
p(0, 0) = p(3, 3) = 1, p(x, x + 1) = p, p(x, x − 1) = 1 − p, for any x ∈ {1, 2}
and all other transition probabilities are zero. Find p if we know that a Markov chain
starting at 1 (meaning X0 = 1), is absorbed at 3 twice as likely as at 0, that is,
P(Xn = 3 for some n|X0 = 1) = 2P(Xn = 0 for some n|X0 = 1).
9. (10 points) Give an example of one Markov chain (either by a transition matrix or a
graph) which has two recurrent classes and two transient states and all of the following
properties:
10. There exists a state with period 2.
11. There exists a state with period 3.
12. A transition probability between any two transient states (possibly the same) is
positive.
13. No matter in which transient state we start, we end up in each recurrent class with
the same probability.
14. (10 points) Let (Xn) be a Markov chain defined on the state space {1, 2, · · · } such that
p(n, n + 1) = 1
3
n
, p(n, 1) = 2
3
n
, p(n, n) = 3
n − 3
3
n
.
Determine whether the chain is transient, positive recurrent, or null recurrent.
15. (10 points) A virus spreading in a community and one person (named A) infects k ≥ 0
other persons with probability p(1 − p)
k
for some given p ∈ (0, 1). Also, A is cured.
Assume that the population is large enough (say infinite). Compute the probability that
starting from one infected individual the virus disappears from the population (there are
zero infected individuals).
16. (10 points) Read and understand Section 4.1 in the textbook (in fact the most important
part is till equation (4.1), approximately 2 pages). Solve problem 4.2 on page 98 in the
textbook.