The drift and minorization method for reversible Markov chains
Abstract/Contents
- Abstract
- This thesis proves upper bounds on the convergence time to stationarity for reversible discrete time Markov chains on general state spaces. The method of proof is the well-established drift and minorization approach, which imposes a regenerative structure on the Markov chain according to a particular recipe. The resulting bounds are computable in terms of the ingredients of the recipe. The convergence theorems in this thesis are developed using a new perspective on the interplay between regeneration and reversibility. They are more widely applicable than previous results and provide better numerical bounds on the time to stationarity in specific examples. Two Gibbs samplers from Bayesian statistics are treated in detail. When applied to these chains, the new bounds improve on earlier work but are still quite conservative compared with the true convergence rates. For certain classes of finite chains, the drift and minorization method can give precise bounds on the mixing time. A striking result of this type is a sharp upper bound on the cutoff window for birth and death chains. In addition, an inductive argument shows that the spectral gap of the random walk on the hypercube can be recovered using drift and minorization up to a constant factor of 2. The thesis also contains: (1) An exposition of the drift and minorization method, explaining both the renewal theory approach of Meyn and Tweedie and the coupling approach of Rosenthal, and showing how the bounds improve when the chain is reversible or stochastically monotone. (2) A development of the properties of different types of regeneration times for general state space Markov chains. Defining a randomized stopping time usually requires enlarging the sample space to incorporate independent randomness. In full generality, this operation raises subtle questions of measurability, which are resolved using a new "compatibility condition." (3) A brief consideration of quantile estimation in Markov chain Monte Carlo, focusing on concentration inequalities that provide finite-sample guarantees at specified confidence levels. The goal is to prove inequalities that rely as little as possible on theoretical convergence bounds (of the sort proved elsewhere in this thesis) and as much as possible on the empirical sample.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2016 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Jerison, Daniel |
|---|---|
| Associated with | Stanford University, Department of Mathematics. |
| Primary advisor | Diaconis, Persi |
| Thesis advisor | Diaconis, Persi |
| Thesis advisor | Chatterjee, Sourav |
| Thesis advisor | Zheng, Tianyi |
| Advisor | Chatterjee, Sourav |
| Advisor | Zheng, Tianyi |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Daniel Jerison. |
|---|---|
| Note | Submitted to the Department of Mathematics. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2016. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2016 by Daniel Charles Jerison
- 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...