Polynomial-time counting and sampling of two-rowed contingency tables

DOI10.1016/S0304-3975(99)00136-XzbMath0949.68009WikidataQ126537172 ScholiaQ126537172MaRDI QIDQ1583095

M. Dyer, Catherine Greenhill

Publication date: 26 October 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

complexityMarkov chainsrandomized algorithmscontingency tablespath coupling

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (12)

On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \) ⋮ Polynomial time approximate or perfect samplers for discretized Dirichlet distribution ⋮ Structure and eigenvalues of heat-bath Markov chains ⋮ Randomized approximation scheme and perfect sampler for closed Jackson networks with multiple servers ⋮ A faster FPTAS for counting two-rowed contingency tables ⋮ The mixing time of switch Markov chains: a unified approach ⋮ Markov chain Monte Carlo exact tests for incomplete two-way contingency tables ⋮ Random generation of \(2 \times 2 \times\dots \times 2 \times J\) contingency tables ⋮ Random walks on the vertices of transportation polytopes with constant number of sources ⋮ A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant ⋮ Minimal invariant Markov basis for sampling contingency tables with fixed marginals ⋮ Random sampling of contingency tables via probabilistic divide-and-conquer

Cites Work

• Testing for independence in a two-way table: New interpretations of the chi-square statistic
• An application of Harnack inequalities to random walk on nilpotent quotients
• The Analysis of Categorical Data From Complex Sample Surveys: Chi-Squared Tests for Goodness of Fit and Independence in Two-Way Tables
• Sampling contingency tables
• [https://portal.mardi4nfdi.de/wiki/Publication:4705324 Random generation of 2�n contingency tables]
• A more rapidly mixing Markov chain for graph colorings
• On sampling with Markov chains
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Polynomial-time counting and sampling of two-rowed contingency tables