Suggest the following approach to shuffling deck of n cards; for simplicity we set n = 3 and consider only this case. Starting with any initial ordering of cards, one of numbers 1, 2, 3 is randomly selected each with probability 1/3 . If number i is chosen, then we take the card that is in position i and put it on top of the deck, i.e., we move it to position 1. We then repeatedly perform the same operation.
(a) Set this up as a Markov chain, by specifying the state space and the transition matrix.
(b) Show that, in the limit of many shuffles, the deck is perfectly shuffled in the sense that any one of the possible orders is equally likely.