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

DOI10.1016/S0304-3975(99)00136-XMaRDI QIDQ1583095zbMATHWikidataFDO

Authors M. Dyer, Catherine Greenhill

Publication date 26 October 2000

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

zbMATH Keywords

contingency tablescomplexityrandomized algorithmsMarkov chainspath coupling

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1223716
• Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
• Improved bounds for sampling contingency tables
• scientific article; zbMATH DE number 2127729
• Random generation of \(2 \times 2 \times\dots \times 2 \times J\) contingency tables

Cites work

• scientific article; zbMATH DE number 3835159 (Why is no real title available?)
• scientific article; zbMATH DE number 3812655 (Why is no real title available?)
• scientific article; zbMATH DE number 18983 (Why is no real title available?)
• scientific article; zbMATH DE number 1223716 (Why is no real title available?)
• scientific article; zbMATH DE number 1303576 (Why is no real title available?)
• scientific article; zbMATH DE number 194747 (Why is no real title available?)
• scientific article; zbMATH DE number 795108 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 6472593 (Why is no real title available?)
• A more rapidly mixing Markov chain for graph colorings
• An application of Harnack inequalities to random walk on nilpotent quotients
• On sampling with Markov chains
• Random generation of 2�n contingency tables
• Sampling contingency tables
• Testing for independence in a two-way table: New interpretations of the chi-square statistic
• The Analysis of Categorical Data From Complex Sample Surveys: Chi-Squared Tests for Goodness of Fit and Independence in Two-Way Tables

Cited in

(19)

• Linear-time uniform generation of random sparse contingency tables with specified marginals
• On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \)
• scientific article; zbMATH DE number 5280093 (Why is no real title available?)
• Structure and eigenvalues of heat-bath Markov chains
• A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant
• Randomized approximation scheme and perfect sampler for closed Jackson networks with multiple servers
• Polynomial time approximate or perfect samplers for discretized Dirichlet distribution
• A faster FPTAS for counting two-rowed contingency tables
• Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
• Random walks on the vertices of transportation polytopes with constant number of sources
• Minimal invariant Markov basis for sampling contingency tables with fixed marginals
• Approximately counting integral flows and cell-bounded contingency tables
• An approximation algorithm for counting contingency tables
• scientific article; zbMATH DE number 2127729 (Why is no real title available?)
• The mixing time of switch Markov chains: a unified approach
• Random generation of \(2 \times 2 \times\dots \times 2 \times J\) contingency tables
• Random sampling of contingency tables via probabilistic divide-and-conquer
• Markov chain Monte Carlo exact tests for incomplete two-way contingency tables
• Polynomial time perfect sampling algorithm for two-rowed contingency tables

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1583095)