Description

CS 70 Discrete Mathematics and Probability Theory

1 Markov Chains: Prove/Disprove
Prove or disprove the following statements, using the definitions from the previous question.
(a) There exists an irreducible, finite Markov chain for which there exist initial distributions that converge to different distributions.
(b) There exists an irreducible, aperiodic, finite Markov chain for which P(Xn+1 = j | Xn = i)= 1 or 0 for all i, j.
(c) There exists an irreducible, non-aperiodic Markov chain for which P(Xn+1 = j | Xn = i) 6= 1
for all i, j.
(d) For an irreducible, non-aperiodic Markov chain, any initial distribution not equal to the invariant distribution does not converge to any distribution.
2 Can it be a Markov Chain?
(a) A fly flies in a straight line in unit-length increments. Each second it moves to the left with probability 0.3, right with probability 0.3, and stays put with probability 0.4. There are two spiders at positions 1 and m and if the fly lands in either of those positions it is captured. Given that hte fly starts between positions 1 and m, model this process as a Markov Chain.
(b) Take the same scenario as in the previous part with m = 4. Let Yn = 0 if at time n the fly is in position 1 or 2 and letYn= 1 if at time n the fly is in position 3 or 4. Is the processYn a Markov chain?
3 Allen’s Umbrella Setup
Every morning, Allen walks from his home to Soda, and every evening, Allen walks from Soda to his home. Suppose that Allen has two umbrellas in his possession, but he sometimes leaves his
umbrellas behind. Specifically, before leaving from his home or Soda, he checks the weather. If it is raining outside, he will bring his umbrella (that is, if there is an umbrella where he currently is). If it is not raining outside, he will forget to bring his umbrella. Assume that the probability of rain is p.
(a) Model this as a Markov chain. What is X ? Write down the transition matrix.
(b) What is the transition matrix after 2 trips? n trips? Determine if the distribution of Xn converges to the invariant distribution, and compute the invariant distribution. Determine the long-term fraction of time that Allen will walk through rain with no umbrella.
4 Three Tails
You flip a fair coin until you see three tails in a row. What is the average number of heads that you’ll see until getting TTT?
Hint: How is this different than the number of coins flipped until getting TTT?