Mallows permutation model : sampling algorithms and probabilistic properties
Abstract/Contents
- Abstract
- Introduced by Mallows in statistical ranking theory, Mallows permutation model is a class of non-uniform probability measures on permutations. The general model depends on a distance metric that can be chosen from a host of metrics on permutations. This thesis studies Mallows permutation models with L1 and L2 distances, respectively known as Spearman's footrule and Spearman's rank correlation in the statistics literature. We focus on two aspects of these Mallows models--sampling algorithms and probabilistic properties. For sampling algorithms, we investigate hit and run algorithms for sampling from the two Mallows models. Hit and run algorithms are a broad class of Markov chain Monte Carlo algorithms that includes the celebrated Swendsen-Wang algorithm for sampling from the Ising model. These algorithms are usually non-local and fast mixing in practice. In this thesis, we show that the hit and run algorithms for sampling from Mallows permutation models with L1 and L2 distances mix extremely fast. For probabilistic properties, we consider the following question: Picking a random permutation from either of the two Mallows models, what does it "look like"? This may involve various features of the permutation. In this thesis, we focus on the distribution of the points in the graphical representation of the permutation. We show that most of these points are concentrated in a band around the diagonal of the plane with high probability, and obtain precise limit theorems regarding the distribution of the points and their band structure. The proofs of these results are based on multi-scale analysis and the use of the hit and run algorithm as a proof technique.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2022; ©2022 |
| Publication date | 2022; 2022 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Zhong, Chenyang |
|---|---|
| Degree supervisor | Diaconis, Persi |
| Thesis advisor | Diaconis, Persi |
| Thesis advisor | Dembo, Amir |
| Thesis advisor | Siegmund, David, 1941- |
| Degree committee member | Dembo, Amir |
| Degree committee member | Siegmund, David, 1941- |
| Associated with | Stanford University, Department of Statistics |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Chenyang Zhong. |
|---|---|
| Note | Submitted to the Department of Statistics. |
| Thesis | Thesis Ph.D. Stanford University 2022. |
| Location | https://purl.stanford.edu/zw519wz1063 |
Access conditions
- Copyright
- © 2022 by Chenyang Zhong
Also listed in
Loading usage metrics...