Negative examples for sequential importance sampling of binary contingency tables

DOI10.1007/s00453-011-9569-3zbMath1264.68210arXivmath/0606650OpenAlexW2062258188MaRDI QIDQ1945173

Ivona Bezáková, Eric Vigoda, Alistair Sinclair, Daniel Štefanković

Publication date: 3 April 2013

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0606650

zbMATH Keywords

Markov chain Monte Carlosequential Monte Carlographs with prescribed degree sequencezero-one table

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Sampling theory, sample surveys (62D05) Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Contingency tables (62H17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Monte Carlo algorithms for computing \(\alpha \)-permanents, Stratified sampling for the Ising model: A graph-theoretic approach, State-Dependent Kernel Selection for Conditional Sampling of Graphs, Efficient importance sampling for binary contingency tables, A sequential algorithm for generating random graphs, On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \), Stochastic approximation Monte Carlo importance sampling for approximating exact conditional probabilities, Uniformly Generating Origin Destination Tables, Counting subsets of contingency tables, Randomization methods for assessing data analysis results on real‐valued matrices, Random sampling of contingency tables via probabilistic divide-and-conquer, A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix

Cites Work

• A sequential algorithm for generating random graphs
• Efficient importance sampling for binary contingency tables
• Sequential importance sampling for multiway tables
• Stepwise mutation likelihood computation by sequential importance sampling in subdivided population models
• A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Sequential Monte Carlo Methods for Statistical Analysis of Tables
• A Short Proof of the Factor Theorem for Finite Graphs
• Concentration of Measure for the Analysis of Randomized Algorithms
• Sampling binary contingency tables with a greedy start