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: 2006-01-01

Citations: 38

DOI: https://doi.org/10.1137/s0097539703434243

View Publication

Locations

SIAM Journal on Computing - View

Similar Works

Action	Title	Year	Authors
+	Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows	2003	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
+ PDF Chat	On the Diaconis-Gangolli Markov chain for sampling contingency tables with cell-bounded entries	2010	Ivona Bezáková Nayantara Bhatnagar Dana Randall
+	A genuinely polynomial-time algorithm for sampling two-rowed contingency tables	1998	Martin Dyer Catherine Greenhill
+	Sampling contingency tables	2017	Koko K. Kayibi S. Pirzada T. A. Chishti
+	Random walks in convex sets	2000	Benjamin Morris Alistair Sinclair
+	Sampling contingency tables	1997	Martin Dyer Ravi Kannan John Mount
+	On sampling with Markov chains	1996	Fan Chung R. L. Graham Stephen Yau
+	Faster markov chain monte carlo algorithms for the permanent and binary contingency tables	2006	Eric Vigoda Ivona Bezáková
+	On sampling with Markov chains	1996	Fan Chung Ron Graham Shing‐Tung Yau
+	Annealing and tempering for sampling and counting	2007	Dana Randall Eric Vigoda Nayantara Bhatnagar
+	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
+	Linear-time uniform generation of random sparse contingency tables with specified marginals	2021	Andrii Arman Pu Gao Nicholas Wormald
+ PDF Chat	Linear-time uniform generation of random sparse contingency tables with specified marginals	2024	Andrii Arman Pu Gao Nicholas Wormald
+	Polynomial Time Perfect Sampling Algorithm for Two-Rowed Contingency Tables	2004	Shuji Kijima Tomomi Matsui
+	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
+	Improved bounds for sampling contingency tables	2002	Ben Morris

Works That Cite This (33)

Action	Title	Year	Authors
+	Annealing and tempering for sampling and counting	2007	Dana Randall Eric Vigoda Nayantara Bhatnagar
+ PDF Chat	New Classes of Degree Sequences with Fast Mixing Swap Markov Chain Sampling	2017	Péter L. Erdős István Miklós Zoltán Toroczkai
+ PDF Chat	A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix	2015	Péter L. Erdős István Miklós Zoltán Toroczkai
+	An approximation algorithm for counting contingency tables	2008	Alexander Barvinok Zur Luria Alex Samorodnitsky Alexander Yong
+	What does a random contingency table look like?	2008	Alexander Barvinok
+	Random sampling of Latin squares via binary contingency tables and probabilistic divide-and-conquer	2017	Stephen DeSalvo
+	Heat-bath Markov chains have no negative eigenvalues	2013	Catherine Greenhill Mario Ullrich
+ PDF Chat	Heat-bath random walks with Markov bases	2017	Caprice Stanley Tobias Windisch
+ PDF Chat	Random sampling of contingency tables via probabilistic divide-and-conquer	2019	Stephen DeSalvo James Zhao
+ PDF Chat	An approximation algorithm for counting contingency tables	2010	Alexander Barvinok Zur Luria Alex Samorodnitsky Alexander Yong

Works Cited by This (20)

Action	Title	Year	Authors
+	Random walks in convex sets	2000	Benjamin Morris 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
+	Analyzing Glauber dynamics by comparison of Markov chains	2000	Dana Randall Prasad Tetali
+	Approximate counting by dynamic programming	2003	Martin Dyer
+	Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions	2004	Ben Morris Alistair Sinclair
+	Value of the Steinitz constant	1980	Victor S. Grinberg Sergey Sevastyanov
+	Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow	1992	Alistair Sinclair
+	On sampling with Markov chains	1996	Fan Chung Ron Graham Shing‐Tung Yau