Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows

Mary Cryan, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Russell Martin

Type: Article

Publication Date: 2003-06-26

Citations: 18

DOI: https://doi.org/10.1109/sfcs.2002.1181996

Similar Works

Action	Title	Year	Authors
+	Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows	2006	Mary Cryan Martin Dyer Leslie Ann Goldberg Mark Jerrum Russell Martin
+	Polynomial-time counting and sampling of two-rowed contingency tables	2000	Martin Dyer Catherine Greenhill
+ PDF Chat	On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded Entries	2009	Ivona Bezáková Nayantara Bhatnagar Dana Randall
+	A genuinely polynomial-time algorithm for sampling two-rowed contingency tables	1998	Martin Dyer Catherine Greenhill
+ PDF Chat	On the Diaconis-Gangolli Markov chain for sampling contingency tables with cell-bounded entries	2010	Ivona Bezáková Nayantara Bhatnagar Dana Randall
+	Random walks in convex sets	2000	Benjamin Morris Alistair Sinclair
+	Sampling contingency tables	2017	Koko K. Kayibi S. Pirzada T. A. Chishti
+	Polynomial Time Perfect Sampling Algorithm for Two-Rowed Contingency Tables	2004	Shuji Kijima Tomomi Matsui
+	Sampling contingency tables	1997	Martin Dyer Ravi Kannan John Mount
+	Faster markov chain monte carlo algorithms for the permanent and binary contingency tables	2006	Eric Vigoda Ivona Bezáková
+	Random generation of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mn>2</mml:mn><mml:mo>×</mml:mo><mml:mn>2</mml:mn><mml:mo>×</mml:mo><mml:mo>⋯</mml:mo><mml:mo>×</mml:mo><mml:mn>2</mml:mn><mml:mo>×</mml:mo><mml:mi>J</mml:mi></mml:math> contingency tables	2004	Tomomi Matsui Yasuko Matsui Yoko Ono
+	Improved Bounds for Sampling Contingency Tables	1999	Ben Morris
+	On sampling with Markov chains	1996	Fan Chung R. L. Graham Stephen Yau
+ PDF Chat	Linear-time uniform generation of random sparse contingency tables with specified marginals	2024	Andrii Arman Pu Gao Nicholas Wormald
+	Linear-time uniform generation of random sparse contingency tables with specified marginals	2021	Andrii Arman Pu Gao Nicholas Wormald
+	Sampling binary contingency tables with a greedy start	2006	Ivona Bezáková Nayantara Bhatnagar Eric Vigoda
+ PDF Chat	Sampling binary contingency tables with a greedy start	2006	Ivona Bezáková Nayantara Bhatnagar Eric Vigoda
+	On sampling with Markov chains	1996	Fan Chung Ron Graham Shing‐Tung Yau
+	Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs	2010	Parikshit Gopalan Adam R. Klivans Raghu Meka
+	Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs	2010	Parikshit Gopalan Adam R. Klivans Raghu Meka

Works That Cite This (17)

Action	Title	Year	Authors
+ PDF Chat	A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant	2003	Mary Cryan Martin Dyer
+ PDF Chat	On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded Entries	2009	Ivona Bezáková Nayantara Bhatnagar Dana Randall
+	Random generation of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mn>2</mml:mn><mml:mo>×</mml:mo><mml:mn>2</mml:mn><mml:mo>×</mml:mo><mml:mo>⋯</mml:mo><mml:mo>×</mml:mo><mml:mn>2</mml:mn><mml:mo>×</mml:mo><mml:mi>J</mml:mi></mml:math> contingency tables	2004	Tomomi Matsui Yasuko Matsui Yoko Ono
+	Markov bases of three-way tables are arbitrarily complicated	2005	Jesús A. De Loera Shmuel Onn
+ PDF Chat	A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant	2002	Mary Cryan Martin Dyer
+	Polynomial time perfect sampling algorithm for two‐rowed contingency tables	2005	Shuji Kijima Tomomi Matsui
+ PDF Chat	Analysis of Markov chain algorithms on spanning trees, rooted forests, and connected subgraphs	2005	Johannes Fehrenbach Ludger Rüschendorf
+	Perfect sampling algorithm for small m×n contingency tables	2009	Nicolas Wicker
+ PDF Chat	Markov chain comparison	2006	Martin Dyer Leslie Ann Goldberg Mark Jerrum Russell Martin
+	Approximately counting integral flows and cell-bounded contingency tables	2005	Mary Cryan Martin Dyer Dana Randall

Works Cited by This (24)

Action	Title	Year	Authors
+	Rectangular Arrays with Fixed Margins	1995	Persi Diaconis Anil Gangolli
+	Random walks in convex sets	2000	Benjamin Morris Alistair Sinclair
+	The Markov chain Monte Carlo method: an approach to approximate counting and integration	1996	Mark Jerrum Alistair Sinclair
+	Sampling contingency tables	1997	Martin Dyer Ravi Kannan John Mount
+ PDF Chat	Comparison Theorems for Reversible Markov Chains	1993	Persi Diaconis Laurent Saloff‐Coste
+	Improved bounds for sampling colorings	2000	Eric Vigoda
+	Probability and Random Processes	2004	Geoffrey Grimmett David Stirzaker
+ PDF Chat	A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant	2002	Mary Cryan Martin Dyer
+	Analyzing Glauber dynamics by comparison of Markov chains	2000	Dana Randall Prasad Tetali
+	Approximate counting by dynamic programming	2003	Martin Dyer