3.Consider the shuffling of a deck of 3 cards as follows:

(a) move the top card to the bottom, with probabilityp;

(b) interchange the top and the middle cards, with probability 1p.

That is, each shuffle independently does either (a) or (b), with probabilitypand 1p, respectively. The question is, after many such operations, whether the deck will be thoroughly shuffled, i.e., any order of the three cards will be equally likely. To answer this question, construct a Markov chain with the state space being the 3!=6 different orderings of the cards.

(i) Write down the probability transition matrix, derive the limiting probabilities, and supply an answer to the above question.

(ii) Is there any restriction that we need to impose onp? For instance, do we needp= 0.5? Do we needp= 0 and/orp= 1? Consider in particular: (a) whenp= 0, is the Markov chain irreducible, and if not, what are the communicating classes; (b) repeat (a) forp= 1.