Combinatorial methods in Markov chain mixing
Abstract/Contents
- Abstract
- This thesis is concerned with various aspects of Markov chain mixing. The general problem is to examine the number of steps of a Markov chain required for the chain to be close to its stationary distribution. Chapter 2 discusses the problem of shuffling a large deck of cards, describing how to implement riffle shuffles using only operations which affect fewer cards at a time. It also gives upper bounds on the mixing times of several related shuffling schemes. Riffle shuffles are usually modelled by the GSR shuffle. Chapter 3 presents the results of several hundred physical riffle shuffles, and compares this data to the predictions of the GSR model. Similar analysis is done for mash shuffles. Chapter 4 describes how the convergence of a Markov chain may be affected by interweaving other operations. It gives examples where these modifications can drastically slow down or speed up convergence, and a conjecture regarding the efficient generation of random partitions. The random transposition walk on the symmetric group is well-understood. Chapter 5 extends the known strong stationary time results regarding this walk to a more general walk where at each step, a larger number of cards are chosen at random and shuffled amongst themselves. Chapter 6 introduces mutation times, a new combinatorial technique similar to the method of strong stationary times. Mutation times can give upper bounds on the mixing times of some Markov chains where strong stationary times may be difficult to construct. This chapter uses mutation times to analyse several models of wash shuffles, as well as some classical random walks on the symmetric group. Chapters 7 and 8 examine the convergence of statistics on Markov chains, rather than the convergence of the chains themselves. Chapter 7 describes how coupling may be used to obtain results about the convergence of statistics, and Chapter 8 uses strong stationary times. Both chapters contain a large number of examples. Finally, Chapter 9 presents a likelihood order for simple random walks on Coxeter groups, showing that the weak Bruhat order describes which elements are more or less likely than others after any number of steps.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2017 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | White, Graham Robert |
|---|---|
| Associated with | Stanford University, Department of Mathematics. |
| Primary advisor | Diaconis, Persi |
| Thesis advisor | Diaconis, Persi |
| Thesis advisor | Fox, Jacob, 1984- |
| Thesis advisor | Soundararajan, Kannan, 1973- |
| Advisor | Fox, Jacob, 1984- |
| Advisor | Soundararajan, Kannan, 1973- |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Graham Robert White. |
|---|---|
| Note | Submitted to the Department of Mathematics. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2017. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2017 by Graham Robert White
- 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...