Random walk, semi-direct products, and card shuffling

This thesis studies random walk on various finite groups and presents new techniques for bounding the mixing times of those walks. It also studies how the eigenvalues of some of those walks split among the irreducible representations of the relevant group.; Diaconis and Saloff-Coste [26] developed a general theory for bounding the mixing rates of a family of random walks on direct product groups of the form Gd0 . This thesis uses strong uniform times to produce bounds for a related family of random walks on semi-direct product groups of the form Gd0⋊G2 where G2 = d.; Bidigare, Hanlon, and Rockmore (BHR) [12] studied random walks on hyperplane arrangements in Rn . Examples of these walks include (symmetrized) BHR shuffles, a family of random walks on Sn that contains riffle shuffles and random to top shuffles. This thesis refines the methods of BHR and of Brown and Diaconis [17] to bound the mixing rates of subsets of cards. It also determines how the eigenvalues of BHR shuffles split among the irreducible representations of Sn.; The random to random shuffle is the multiplicative symmetrization of the random to top shuffle. This thesis proves that O( n log n) random to random shuffles are necessary and sufficient to mix n cards. It also gives partial results on the decomposition of the eigenvalues of random to random shuffles among the irreducible representations of Sn.