Random walk, semi-direct products, and card shuffling

Abstract iv
Acknowledgements v
1 Introduction 1
1.1 Random walk examples . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Simple random walk on Z d . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Simple random walk on the hypercube . . . . . . . . . . . . . 8
1.1.3 Random walks on the lamplighter group . . . . . . . . . . . . 11
1.1.4 Random walk on direct products . . . . . . . . . . . . . . . . 13
1.1.5 Random transpositions . . . . . . . . . . . . . . . . . . . . . . 14
1.1.6 Riffle shuffles . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.1.7 Random to top shuffles . . . . . . . . . . . . . . . . . . . . . . 16
1.1.8 Borel’s shuffle . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.1.9 Random walks on hyperplane arrangements . . . . . . . . . . 19
1.1.10 BHR shuffles . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.2 Methods for bounding rates of convergence . . . . . . . . . . . . . . . 26
1.2.1 Fourier analysis on finite groups . . . . . . . . . . . . . . . . . 26
1.2.2 Geometric comparison . . . . . . . . . . . . . . . . . . . . . . 29
1.2.3 Strong uniform times . . . . . . . . . . . . . . . . . . . . . . . 31
1.2.4 Coupling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.2.5 Entropy lower bound . . . . . . . . . . . . . . . . . . . . . . . 34
1.3 What this thesis is about, and why . . . . . . . . . . . . . . . . . . . 35
2 Random Walk on semi-direct products 37
2.1 Methods for semi-direct products . . . . . . . . . . . . . . . . . . . . 37
2.1.1 Direct Products . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.1.2 Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.1.3 Observations on the main result . . . . . . . . . . . . . . . . . 44
2.2 Generalizing d-fold direct products . . . . . . . . . . . . . . . . . . . 48
2.2.1 Uniform second coordinate . . . . . . . . . . . . . . . . . . . . 49
2.2.2 Covering times . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.3 Base group Z d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.3.1 Interpreting the walk as card shuffling . . . . . . . . . . . . . 54
2.3.2 Systematic Randomization . . . . . . . . . . . . . . . . . . . . 54
2.3.3 General finite lamplighter walks . . . . . . . . . . . . . . . . . 56
2.4 Perfect shuffles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
2.4.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
2.4.2 The group ?I,O? . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.4.3 Perfect shuffles and the finite lamplighter group . . . . . . . . 68
2.4.4 Random perfect shuffles . . . . . . . . . . . . . . . . . . . . . 69
2.4.5 Symmetrized random perfect shuffles . . . . . . . . . . . . . . 71
2.5 The projection property . . . . . . . . . . . . . . . . . . . . . . . . . 73
2.5.1 Projections of random walk . . . . . . . . . . . . . . . . . . . 74
2.5.2 Random spatula walk . . . . . . . . . . . . . . . . . . . . . . . 77
2.5.3 Consecutive perfect shuffles . . . . . . . . . . . . . . . . . . . 79
2.5.4 Generalizations of perfect shuffles . . . . . . . . . . . . . . . . 81
2.6 Random walk on p-groups . . . . . . . . . . . . . . . . . . . . . . . . 82
2.6.1 More simple random walk on Z d . . . . . . . . . . . . . . . . . 83
2.6.2 Generalized lamplighter walk . . . . . . . . . . . . . . . . . . 83
3 Mixing Subsets of Cards 88
3.1 Projections of BHR random walks . . . . . . . . . . . . . . . . . . . . 89
3.1.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.1.2 Projections and card shuffling . . . . . . . . . . . . . . . . . . 90
3.1.3 Intersection posets and eigenvalues . . . . . . . . . . . . . . . 91
3.1.4 Upper bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.2 Probabilistic interpretation and examples . . . . . . . . . . . . . . . . 93
3.2.1 Inverse riffle shuffles . . . . . . . . . . . . . . . . . . . . . . . 94
3.2.2 Random to top shuffles . . . . . . . . . . . . . . . . . . . . . . 96
3.2.3 Inverse Borel shuffles . . . . . . . . . . . . . . . . . . . . . . . 98
4 BHR Shuffles 100
4.1 Gessel’s Bijection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.1.1 Lyndon words and necklaces . . . . . . . . . . . . . . . . . . . 102
4.1.2 Shuffles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.1.3 Cycle indices . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.2 Lie characters and plethyism . . . . . . . . . . . . . . . . . . . . . . . 107
4.2.1 Lie characters . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.2.2 Enumerating Lyndon words . . . . . . . . . . . . . . . . . . . 108
4.2.3 Plethyism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.2.4 Cycle indices and BHR shuffles . . . . . . . . . . . . . . . . . 113
4.3 Idempotents of BHR shuffles . . . . . . . . . . . . . . . . . . . . . . . 116
4.3.1 Idempotents of semigroup random walks . . . . . . . . . . . . 116
4.3.2 Characters, eigenvalues, and idempotents . . . . . . . . . . . . 121
4.4 Proof of main result . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
4.5 Examples and Special Cases . . . . . . . . . . . . . . . . . . . . . . . 125
4.5.1 Eigenvalue decomposition for S 4 . . . . . . . . . . . . . . . . . 125
4.5.2 Riffle shuffle eigenvalues . . . . . . . . . . . . . . . . . . . . . 127
4.5.3 Random to top and Borel’s shuffle eigenvalues . . . . . . . . . 127
4.5.4 Eigenvalues of special representations . . . . . . . . . . . . . . 128
5 Random to random shuffles 131
5.1 Convergence to uniformity . . . . . . . . . . . . . . . . . . . . . . . . 132
5.1.1 Upper bound . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
5.1.2 Longest increasing subsequence . . . . . . . . . . . . . . . . . 135
5.1.3 Coupon collector problem . . . . . . . . . . . . . . . . . . . . 136
5.1.4 Proof of lower bound . . . . . . . . . . . . . . . . . . . . . . . 137
5.2 Random to random eigenvalues . . . . . . . . . . . . . . . . . . . . . 139
5.2.1 Proof for the eigenvalues of ω n−1,1 . . . . . . . . . . . . . . . . 142
5.2.2 The eigenvalues of ω n−1,1 ⊗ ω 1
n
. . . . . . . . . . . . . . . . . 148
5.2.3 Miscellaneous observations . . . . . . . . . . . . . . . . . . . . 151
5.3 Table of eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
5.3.1 S 2 eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
5.3.2 S 3 eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
5.3.3 S 4 eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
5.3.4 S 5 eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
5.3.5 S 6 eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
5.4 Table of eigenvalues by representation . . . . . . . . . . . . . . . . . . 154
5.4.1 S 2 eigenvalues by representation . . . . . . . . . . . . . . . . . 154
5.4.2 S 3 eigenvalues by representation . . . . . . . . . . . . . . . . . 154
5.4.3 S 4 eigenvalues by representation . . . . . . . . . . . . . . . . . 154
5.4.4 S 5 eigenvalues by representation . . . . . . . . . . . . . . . . . 155
5.4.5 S 6 eigenvalues by representation . . . . . . . . . . . . . . . . . 155
Bibliography 156