ENGLISH

Random walk, semi-direct products, and card shuffling

By Jay-Calvin Uyemura Reyes

Book information

Year
2002
Language
english
Format
PDF
Filesize
1024 kB (1048423 bytes)
Series
PhD thesis at Stanford University
Pages
\173
Topic
Mathematics Algebra
Time added
2021-12-22 08:23:15

Description

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

Similar books

Session C11: Ancient Cultural Landscapes in South Europe – their Ecological Setting and Evolution, Session C22: Gardeners from South America, Session S04: Agro-Pastoralism and Early Metallurgy Sessions, Session WS29: The Idea of Enclosure in Recent Iberian Prehistory, Session C88: Rhytmes et causalites des dynamiques de l'anthropisation en Europe entre 6500 ET 500 BC: Hypotheses socio-culturelles et/ou climatiques: Proceedings of the XV UISPP World Congress (Lisbon 4-9 September 2006) / Actes du XV Congrès Mondial (Lisbonne 4-9 Septembre 2006) Vol.36

2010 · PDF

THE BRITISH ARMY IN INDIA: ITS PRESERVATION BY AN APPROPRIATE CLOTHING, HOUSING, LOCATING, RECREATIVE EMPLOYMENT, AND HOPEFUL ENCOURAGEMENT OF THE TROOPS. with AN APPENDIX ON INDIA : THE CLIMATE OP ITS HILLS ; THE DEVELOPMENT OF ITS RESODRCBS, INDUSTRY, AND ARTS ; THE ADMINISTRATION OF JUSTICE ; THE BLACK ACT ; THE PROGRESS OF CHRISTIANITY ; THE TRAFFIC IN OPIUM ; THE VALUE OF INDIA ; PERMANENT CAUSES OF DISAFFECTION, AND OF THE RECENT REBELLION ; THE TRADITIONARY POLICY; MISGOVERNMENT BY NATIVE RULERS ; ANNEXATIONS OF THEIR TERRITORY, ETC.

1858 · PDF

Idries Shah 27 Books Collection : A Perfumed Scorpion, A Veiled Gazelle, Caravan of Dreams, Darkest England, Destination Mecca, Evenings with Idries Shah, Knowing How to Know, Learning How to Learn, Letters and Lectures of Idries Shah, Neglected aspects of Sufi study, Observations, Oriental Magic, Reflections, Seeker after Truth, Special Illumination, Special Problems in the study of Sufi ideas, Sufi thought and action, Tales of the Dervishes, The Dermis Probe, The Elephant in the Dark, The Englishman Handbook, Idries Shah Antology, The Magic Monastery, The natives are restless, wisdom of the Idiots PDF.

2022 · PDF

The travels of Capts. Lewis and Clarke from St. Louis, by way of the Missouri and Columbia rivers, to the Pacific ocean; performed in the years 1804, 1805 & 1806, by order of the government of the United States. Containing delineations of the manners, customs, religion, &c. of the Indians, comp. from various authentic sources, and original documents, and a summary of the Statistical view of the Indian nations, from the official communication of Meriwether Lewis. Illustrated with a map of the country, inhabited by the western tribes of Indians

1809 · PDF

Professional Linux kernel architecture ''Wrox programmer to programmer''--Cover. - ''What you are reading right now is the result of an evolution over more than seven years: After two years of writing, the first edition was published in German by Carl Hanser Verlag in 2003. It then described kernel 2.6.0. The test was used as a basis for the low-level design documentation for the EAL4+ security evaluation of Red Hat Enterprise Linux 5, requiring to update it to kernel 2.6.18 (if the EAL acronym does not mean anything to you, then Wikipedia is once more your friend). Hewlett-Packard sponsored the translation into English and has, thankfully, granted the rights to publish the result. Updates to kernel 2.6.24 were then performed specifically for this book''--P. ix

2008 · PDF