  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.
