Homework 10

The homework is due by class on Wednesday, December 3.
(You can turn it in earlier if you like.)

These 2 problems study the top-to-random shuffle which is
the following Markov chain. There is a deck of n distinct
cards. A state is a permutation or ordering of the n cards.
At each time, take the top-most card and randomly choose one of
the n possible positions for the card.

For example, suppose we have n=8 cards and they are labeled 1,2,...,8.
Say at time t=3 we are at the ordering 3,4,1,8,6,7,5,2.
The top card is card 2. There are 8 possible locations for it:
      before 3, between 3 and 4, between 4 and 1, ..., between 7 and 5, and after 5.
Choose randomly from these 8 possibilities. Say we chose to place it between 4 and 1.
Then our new state at time t=4 is the ordering 3,4,2,1,8,6,7,5.
And we repeat the process with card 5 now being the top-card.
  1. Prove whether or not this Markov chain is ergodic.
  2. Prove that the uniform distribution over all n! orderings is
    a stationary distribution.