Birthday problems and rates of convergence for Gibbs sampling
Abstract/Contents
- Abstract
- This thesis is concerned with classical topics in probability theory: the birthday problem and mixing time for Markov chains. Some of this work is contained in \cite{Ottolini2020, Gerencsr2019}. \\ \\ The first two chapters deal with variations of the classical birthday problem: what does the maximum of $n$ discrete random variables with a given sum $k$ look like as $n$ and $k$ are large? The classical birthday problem is concerned with the maximum box count when $k=O(\sqrt n)$ balls are dropped into $n$ boxes. In the first chapter, variations of this problem are studied for a large class of allocation models when $n$ and $k$ are of the same order, using the tools of conditional limit theory. In the second chapter, this is done when the random variables follow an hyper-geometric distribution, and the result is used to give sharp estimates on the expected number of correct guesses in certain card-guessing games with feedback.\\ \\ The last two chapters are concerned with the Gibbs sampler, a Markov chain used to sample from intractable measures on product spaces. The third chapter analyzes the evolution of Hamming distance between a Gibbs sampler and its stationary distribution, in the case the latter is close to a product measure. This situation covers many statistical mechanical models at sufficiently high temperature, and we investigate this in details for the Curie-Weiss model. The fourth chapter analyses the performance of a Gibbs sampler used to sample from a class of measures introduced by de Finetti in the analysis of partially exchangeable binary data. \\ \\.
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 | 2021; ©2021 |
| Publication date | 2021; 2021 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Ottolini, Andrea |
|---|---|
| Degree supervisor | Diaconis, Persi |
| Thesis advisor | Diaconis, Persi |
| Thesis advisor | Chatterjee, Sourav |
| Thesis advisor | Dembo, Amir |
| Degree committee member | Chatterjee, Sourav |
| Degree committee member | Dembo, Amir |
| Associated with | Stanford University, Department of Mathematics |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Andrea Ottolini. |
|---|---|
| Note | Submitted to the Department of Mathematics. |
| Thesis | Thesis Ph.D. Stanford University 2021. |
| Location | https://purl.stanford.edu/fk362bt5878 |
Access conditions
- Copyright
- © 2021 by Andrea Ottolini
- 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...