Permutations with interval restrictions
Abstract/Contents
- Abstract
- This thesis studies the problem of the random transposition walk on permutations with interval restrictions. The mixing time of this Markov chain is explored, and a number of different cases are considered. For the case of bounded interval restrictions, a polynomial bound for the mixing time is achieved. For a specific example of bounded interval restrictions called Fibonacci permutations, the correct order of the mixing time is derived. An example of a family of interval restriction matrices for which the random walk mixes in exponential time is provided, showing that the walk in general does not mix in polynomial time. The case of one-sided interval restrictions is also studied, and cut-off is shown for a large class of one-sided interval restriction matrices. Furthermore, examples are provided in which chi-squared cut-off occurs, while total variation mixing occurs significantly earlier without cut-off. Finally, a coupling argument showing the correct order mixing time for the random transposition walk on the whole symmetric group is presented. This is achieved via projection to conjugacy classes and then a path coupling argument.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2011 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Bormashenko, Olena |
|---|---|
| Associated with | Stanford University, Department of Mathematics |
| Primary advisor | Diaconis, Persi |
| Thesis advisor | Diaconis, Persi |
| Thesis advisor | Dembo, Amir |
| Thesis advisor | Wood, Philip Matchett |
| Advisor | Dembo, Amir |
| Advisor | Wood, Philip Matchett |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Olena Bormashenko. |
|---|---|
| Note | Submitted to the Department of Mathematics. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2011. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2011 by Olena Bormashenko
- 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...