Retour à la liste de tous les séminaires

Partial mixing of semi-random transposition shuffles

Le : 10/09/2012 11h00
Par : Richard Pymar
Lieu : I 103
Lien web :
Résumé : We consider semi-random transposition shuffles on n cards and give an upper bound of n log k for the mixing time of any k cards, provided k=o((n/log n)^0.5), for any such shuffle. We discuss improvements to this bound for specific shuffles, namely the random-to-random shuffle and cyclic-to-random shuffle. We make extensive use of the relationship between total variation distance and coupling to prove our results.