Blanchet, J. (2006). Importance sampling and efficient counting of 0-1 contingency tables. In Proceedings of the 1st international conference on Performance evaluation methodolgies and tools.
Abstract
Importance sampling has been reported to produce algorithms with excellent empirical performance in counting problems. However, the theoretical support for its efficiency in these applications has been very limited. In this paper, we propose a methodology that can be used to design efficient importance sampling algorithms for counting and test their efficiency rigorously. Our techniques for complexity analysis are based on Lyapunov-type bounds for Markov chains and are specially well-suited for the analysis of state-dependent importance sampling algorithms. These techniques are applied after transforming the problem into a rare-event simulation problem–thereby connecting complexity analysis of counting problems with efficiency in the context of rare-event simulation. As an illustration of our approach, we consider the problem of counting the number of binary contingency tables with fixed column and row …
Authors
Jose Blanchet
Publication date
2006
Journal
Proceedings of the 1st international conference on Performance evaluation methodolgies and tools
