Efficient Importance Sampling for Binary Contingency Tables

Summary:

Diaconis, Holmes, Liu and Chen (2005) JASA, developed a sequential importance sampling algorithm for counting binary contingency tables given row and column sums. I took Jun Liu’s lecture and he mentioned that the performance of the algorithm was truly outstanding in practice. Around that time I. Bezakova, A. Sinclair, D. Stefankovic, and E. Vigoda (2006) ESA, proved that the algorithm of Diaconis et al. had exponential complexity in the worst case. Nevertheless, using Lyapunov bounds and casting the algorithm of Diaconis et al. as an importance sampling algorithm for a first-passage time computation of a random walk, it turns out that one can prove that the sequential importance sampling procedure is strongly optimal for suitably sparse tables.

Bibtex:

@Article{Blanchet07,

author = {Blanchet, J.},

title = {Efficient importance sampling for binary contingency tables},

journal = {Annals of Applied Probability},

year = {2009},

volume = {19},

pages = {949-982}

}