2006/06/26 by Ivona Bezakova, Ivona Bezáková, Alistair Sinclair +7
Computer Science · Mathematics · #62L99 #65C05 #68W20 #Bayesian Modeling and Causal Inference #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Statistical Methods and Inference #Statistics Theory (math.ST) #math.CO #math.ST #msc:62L99 #msc:65C05 #msc:68W20 #stat.TH
paper · pdf · doi:10.48550/arxiv.math/0606650
openalex publication_date 2006/06/26 · arxiv created 2011/06/28 · arxiv updated 2011/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The sequential importance sampling (SIS) algorithm has gained considerable popularity for its empirical success. One of its noted applications is to the binary contingency tables problem, an important problem in statistics, where the goal is to estimate the number of 0/1 matrices with prescribed row and column sums. We give a family of examples in which the SIS procedure, if run for any subexponential number of trials, will underestimate the number of tables by an exponential factor. This result holds for any of the usual design choices in the SIS algorithm, namely the ordering of the columns and rows. These are apparently the first theoretical results on the efficiency of the SIS algorithm for binary contingency tables. Finally, we present experimental evidence that the SIS algorithm is efficient for row and column sums that are regular. Our work is a first step in determining the class of inputs for which SIS is effective.