# Combinatorial methods in Markov chain mixing [electronic resource]

- Responsibility
- Graham Robert White.
- Imprint
- 2017.
- Physical description
- 1 online resource.

## Digital content

## At the library

### Special Collections

#### On-site access

Collections are moving, which may affect access. Request materials as early as possible. Maximum 5 items per day. Contact specialcollections@stanford.edu for information about access.

**University Archives**Request via Aeon (opens in new tab)

Call number | Note | Status |
---|---|---|

3781 2017 W | In-library use |

### More options

## Description

### Creators/Contributors

- Author/Creator
- White, Graham Robert.
- Contributor
- Diaconis, Persi primary advisor. Thesis advisor
- Fox, Jacob, 1984- advisor. Thesis advisor
- Soundararajan, Kannan, 1973- advisor. Thesis advisor
- Stanford University. Department of Mathematics.

### Contents/Summary

- Summary
- 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.

### Bibliographic information

- Publication date
- 2017
- Note
- Submitted to the Department of Mathematics.
- Note
- Thesis (Ph.D.)--Stanford University, 2017.