Negative examples for sequential importance sampling of binary contingency tables

DOI10.1007/s00453-011-9569-3zbMath1264.68210arXivmath/0606650MaRDI 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 Carlo; sequential Monte Carlo; graphs with prescribed degree sequence; zero-one table

Mathematics Subject Classification ID

68W40: Analysis of algorithms

62D05: Sampling theory, sample surveys

68W05: Nonnumerical algorithms

68R05: Combinatorics in computer science

62H17: Contingency tables

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

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

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