1. Define f (r) to be the smallest integer n such that for all regular Markov chains with r states, the nth power of the transition matrix has all entries positive. It has been shown,14 that f (r) =r2 - 2r + 2.
(a) Define the transition matrix of an r-state Markov chain as follows: For states si, with i = 1, 2, . . . , r-2,P(i, i+1) = 1, P(r-1, r) = P(r-1, 1) = 1/2, and P(r, 1) = 1. Show that this is a regular Markov chain.
(b) For r = 3, verify that the fifth power is the first power that has no zeros.
(c) Show that, for general r, the smallest n such that Pn has all entries positive is n = f (r).