EFFICIENT IMPORTANCE SAMPLING FOR BINARY CONTINGENCY TABLES
成果类型：
Article
署名作者：
Blanchet, Jose H.
署名单位：
Columbia University
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
DOI：
10.1214/08-AAP558
发表日期：
2009
页码：
949-982
关键词：
摘要：
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. We apply our techniques 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 tables with fixed column and row sums, c(j)'s and r(i)'s, respectively, and total marginal sums d=Sigma(j)c(j). Assuming that max(j) c(j)=o(d(1/2)), Sigma c(j)(2)=O(d) and the r(j)'s are bounded, we show that a suitable importance sampling algorithm, proposed by Chen et al. [J. Amer Statist. Assoc. 100 (2005) 109-120], requires O(d(3)epsilon(-2)delta(-1)) operations to produce an estimate that has epsilon-relative error with probability 1-delta. In addition, if max(j) c(j) = o(d(1/4-delta 0)) for some delta(0)>0, the same coverage can be guaranteed with O(d(3)epsilon(-2) log(delta(-1))) operations.
来源URL：