1. A flea is initially located on the top face of a cube that has six faces, top and bottom, left and right, and front and back. Every minute it moves from its current location to one of the other five faces, chosen at random.
(a) Find the probability that after four moves it is back to the top face.
(b) Find the probability that after n moves it is on the top face; repeat for the bottom face.
(c) * Find the probability that the next five moves are distinct. This is the same as the probability that the first six locations of the flea are the six faces of the cube, each location being chosen exactly once.
2. (Subsequences of Markov Chains). Suppose fXng is a stationary Markov chain. Let Yn D X2n. Prove or disprove that fYng is a stationary Markov chain. How about fX3ng? fXkng for a general k?