Mathematics – Probability
Scientific paper
2009-08-07
Annals of Applied Probability 2009, Vol. 19, No. 3, 949-982
Mathematics
Probability
Published in at http://dx.doi.org/10.1214/08-AAP558 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Inst
Scientific paper
10.1214/08-AAP558
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=\sum_jc_j$. Assuming that $\max_jc_j=o(d^{1/2})$, $\sum 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\varepsilon^{-2}\delta^{-1})$ operations to produce an estimate that has $\varepsilon$-relative error with probability $1-\delta$. In addition, if $\max_jc_j=o(d^{1/4-\delta_0})$ for some $\delta_0>0$, the same coverage can be guaranteed with $O(d^3\varepsilon^{-2}\log(\delta^{-1}))$ operations.
No associations
LandOfFree
Efficient importance sampling for binary contingency tables does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Efficient importance sampling for binary contingency tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient importance sampling for binary contingency tables will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-152968