2. "Move to Front" Permutations

Consider an alphabet of length N. A move-to-front permutation of the N letters consists of picking one of the letters (randomly or otherwise) and moving it to

the front of the list.

For example, if the alphabet consists of the three letters A, B, and C, and you start with the permutation ABC, then CAB is the result of one move-to-front (the

chosen letter is C), as is ABC (the chosen letter is A), but not CBA.

a) As a preliminary, recall that all transition matrices are stochastic; that is, each row sums to 1. Suppose the transition matrix of a finite-state, irreducible,

aperiodic chain is doubly stochastic; that is, each of its columns also sums to 1. Explain why the stationary distribution must be uniform.

b) A standard deck consists of 52 cards. A "random to front" shuffle is defined as follows: Pick one of the 52 cards uniformly at random and move it to the

front of the deck (which you are welcome to think of as the top of the deck, if you prefer). Explain why if you perform this move over and over again, in the long

run the deck will become well shuffled; that is, all permutations will be equally likely. [Hint: Set up an appropriate chain and use Part a. You might want to try it

out first with an alphabet of just the letters A, B, and C.]