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).