Random sampling of contingency tables and partitions: Two practical examples of the Burnside process
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909764677533696 |
|---|---|
| author | Diaconis, Persi Howes, Michael |
| author_facet | Diaconis, Persi Howes, Michael |
| contents | This paper gives new, efficient algorithms for approximate uniform sampling of contingency tables and integer partitions. The algorithms use the Burnside process, a general algorithm for sampling a uniform orbit of a finite group acting on a finite set. We show that a technique called `lumping' can be used to derive efficient implementations of the Burnside process. For both contingency tables and partitions, the lumped processes have far lower per step complexity than the original Markov chains. We also define a second Markov chain for partitions called the reflected Burnside process. The reflected Burnside process maintains the computational advantages of the lumped process but empirically converges to the uniform distribution much more rapidly. By using the reflected Burnside process we can easily sample uniform partitions of size $10^{10}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_02818 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Random sampling of contingency tables and partitions: Two practical examples of the Burnside process Diaconis, Persi Howes, Michael Computation Combinatorics Probability 60-08 (Primary) 60-04, 62-08 (Secondary) This paper gives new, efficient algorithms for approximate uniform sampling of contingency tables and integer partitions. The algorithms use the Burnside process, a general algorithm for sampling a uniform orbit of a finite group acting on a finite set. We show that a technique called `lumping' can be used to derive efficient implementations of the Burnside process. For both contingency tables and partitions, the lumped processes have far lower per step complexity than the original Markov chains. We also define a second Markov chain for partitions called the reflected Burnside process. The reflected Burnside process maintains the computational advantages of the lumped process but empirically converges to the uniform distribution much more rapidly. By using the reflected Burnside process we can easily sample uniform partitions of size $10^{10}$. |
| title | Random sampling of contingency tables and partitions: Two practical examples of the Burnside process |
| topic | Computation Combinatorics Probability 60-08 (Primary) 60-04, 62-08 (Secondary) |
| url | https://arxiv.org/abs/2503.02818 |