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 >
    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?
    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
  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
  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
    , p(n, 1) = 2
    , p(n, n) = 3
    n − 3
    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)
    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
find the cost of your paper