Random walks on the symmetric group, likelihood orders, and involutions
Abstract/Contents
- Abstract
- This thesis delves into a largely unexplored concept in Markov chain analysis called a likelihood order. A likelihood order for time t of a Markov chain, as defined in this thesis, is an extension of the partial order from most likely to least likely at time t on the states to a total order. Random walks on finite groups are a subset of Markov chains. Aperiodic, irreducible random walks on finite groups converge to uniform over the group. The likelihood order captures internal structure of the walk that is resisting mixing. Understanding the most likely element, least likely element, and other parts of the likelihood order can aid in calculating the total variation distance, separation distance, and l infinity distance of the walk. After sufficient time, the likelihood order for time t will often converge to a fixed likelihood order. For random walks on groups the likelihood order for time t can be proved in some cases with induction and for conjugacy class walks using the discrete Fourier transform and the representation theory of the group. The thesis starts by examining the likelihood orders for simple random walk on cycles, products of cycles, and the dihedral group using both techniques whenever possible. The likelihood orders after sufficient time are identified for a number of random walks on the symmetric group. These walks can all be realized as shuffles of n cards on a table. The likelihood orders that appear are all variants of the cycle lexicographic order on the conjugacy classes of the symmetric group. The transposition walk on the symmetric group is proven to have likelihood order the cycle lexicographic order after order n squared steps. If the walk is made lazy, the likelihood order is shown to vary considerably based on the degree of laziness. The 3-cycle walk on the symmetric group is shown to have an alternating cycle lexicographic order after order n cubed steps. The n-cycle walk for time order n log(n) has an alternating cycle lexicographic order at even times and the reverse of the cycle lexicographic order at odd times. The most and least likely elements of the walk are fixed by 8 steps as the first and last elements of these orders. For p greater than or equal to 4 fixed, n sufficiently large, the likelihood order after sufficient time is found to be a piecewise combination of the cycle lexicographic order and alternating cycle lexicographic order. The likelihood order after sufficient time is also found for the following much more complicated walk. Consider n cards on a table. Pick a random perfect matching of the cards into pairs. Ignore each pair with probability p. For each remaining pair, transpose the cards positions on the table. This makes one step of the involution walk. This walk also has the cycle lexicographic order as its likelihood order after sufficient time. The involution walk is generated by involutions of the symmetric group with binomially distributed 2-cycles. It was introduced to study a conjecture about a random walk on the unitary group from the information theory of back holes. The question of interest is if you take a specific random walk with mixing time n log(n), and then modify it by at each time choosing n/2 commuting generators, how does the mixing time change. The involution walk is shown in this thesis to mix for p at least one half fixed, n sufficiently large in between log based 1/p of n steps and log base 2/(1+p) of n steps. This is a toy model for the unitary group problem, since it selects n/2 commuting generators from the half lazy transposition walk. The observed speed up is O(n) as predicted. The thesis introduces a new technique for finding eigenvalues of random walks generated by many conjugacy classes using the character polynomial for the characters of the representations of the symmetric group. This is especially efficient at calculating the large eigenvalues. The smaller eigenvalues are handled by developing monotonicity relations that also give the likelihood order after sufficient time for the walk.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2015 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Bernstein, Megan Marla | |
|---|---|---|
| Associated with | Stanford University, Department of Mathematics. | |
| Primary advisor | Diaconis, Persi | |
| Thesis advisor | Diaconis, Persi | |
| Thesis advisor | Church, Thomas (Thomas Franklin) | |
| Thesis advisor | Soundararajan, Kannan, 1973- | |
| Advisor | Church, Thomas (Thomas Franklin) | |
| Advisor | Soundararajan, Kannan, 1973- |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Megan Marla Bernstein. |
|---|---|
| Note | Submitted to the Department of Mathematics. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2015. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2015 by Megan Marla Bernstein
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...