Markov Chains Mixing Times

Exercises - Part 1

Ori Gurel-Gurevich  Ariel Yadin

December 16, 2007

Please take some time to go over the last lesson and think about the exercises. Some of the exercises may require knowledge outside the scope of this course. Exercises marked with an asterisk are harder.

Exercise 1. What happens in a perfect riffle shuffle? i.e. when the deck is split into the upper and lower halves and these 2 halves are intertwined perfectly?

Exercise 2. Prove that it is possible to get to any permutation using top-to-somewhere actions.

Exercise 3. Give some (non-rigorous) estimate to the number of arrangements of a standard deck of cards (4 suits of 13 cards each) such that there are no two adjacent cards of the same suit.

Exercise 4 (*). Give some rigorous bounds for this number.

Exercise 5. Guess how many shuffles are needed to mix a deck in the case of riffle shuffle and in the case of top-to-random.

Exercise 6. Prove that if P and Q are stochastic matrices then so is P Q.