Sampling methodology for intractable counting problems
Abstract/Contents
- Abstract
- Many problems in statistics involve distributions which are difficult to sample from, or combinatorial objects which are difficult to enumerate. These challenges are typically resolved through approximate sampling or counting algorithms. However, the focus of the literature thus far on approximation algorithms has been on general results. This thesis examines situations for which these general bounds are extremely loose. First, the problem of sampling perfect matchings of bipartite graphs is considered. While Markov chains on the space of perfect matchings have been shown to mix in polynomial time, restricting to certain subclasses of bipartite graphs allows for massive improvements to the runtime bounds. Furthermore, a sequential importance sampling algorithm, which has an asymptotically exponential runtime, is shown to outperform MCMC algorithms for a large range of graph sizes. The second part of this thesis concerns the problem of independence testing against a uniform alternative in a two-way table. A novel algorithm for carrying out the conditional volume test is proposed and is shown to be consistent and computationally more efficient than existing estimators
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 | 2020; ©2020 |
| Publication date | 2020; 2020 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Tsao, Andrew | |
|---|---|---|
| Degree supervisor | Diaconis, Persi | |
| Thesis advisor | Diaconis, Persi | |
| Thesis advisor | Charikar, Moses | |
| Thesis advisor | Chatterjee, Sourav | |
| Degree committee member | Charikar, Moses | |
| Degree committee member | Chatterjee, Sourav | |
| Associated with | Stanford University, Department of Statistics |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Andrew Tsao |
|---|---|
| Note | Submitted to the Department of Statistics |
| Thesis | Thesis Ph.D. Stanford University 2020 |
| Location | electronic resource |
Access conditions
- Copyright
- © 2020 by Andrew Tsao
Also listed in
Loading usage metrics...