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

DOI10.1016/S0304-3975(99)00136-XzbMATH Open0949.68009WikidataQ126537172 ScholiaQ126537172MaRDI QIDQ1583095FDOQ1583095

Authors: M. Dyer, Catherine Greenhill 

Publication date: 26 October 2000

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The Analysis of Categorical Data From Complex Sample Surveys: Chi-Squared Tests for Goodness of Fit and Independence in Two-Way Tables
• Title not available (Why is that?)
• A more rapidly mixing Markov chain for graph colorings
• Testing for independence in a two-way table: New interpretations of the chi-square statistic
• Sampling contingency tables
• On sampling with Markov chains
• An application of Harnack inequalities to random walk on nilpotent quotients
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random generation of 2�n contingency tables
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (19)

• A faster FPTAS for counting two-rowed contingency tables
• On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \)
• Structure and eigenvalues of heat-bath Markov chains
• Markov chain Monte Carlo exact tests for incomplete two-way contingency tables
• Polynomial time perfect sampling algorithm for two-rowed contingency tables
• Linear-time uniform generation of random sparse contingency tables with specified marginals
• Random sampling of contingency tables via probabilistic divide-and-conquer
• Approximately counting integral flows and cell-bounded contingency tables
• The mixing time of switch Markov chains: a unified approach
• Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
• 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
• Polynomial time approximate or perfect samplers for discretized Dirichlet distribution
• Random generation of \(2 \times 2 \times\dots \times 2 \times J\) contingency tables
• Title not available (Why is that?)
• Randomized approximation scheme and perfect sampler for closed Jackson networks with multiple servers
• An approximation algorithm for counting contingency tables
• Title not available (Why is that?)
• Random walks on the vertices of transportation polytopes with constant number of sources

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)