Efficient importance sampling for binary contingency tables

importance sampling Markov processes approximate counting bipartite graphs Doob \(h\)-transform rare-event simulation binary tables changes-of-measure

Mathematics Subject Classification ID

Contingency tables (62H17)

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. 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 = s u m_{j} c_{j}

. Assuming that

m a x_{j} c_{j} = o (d^{1 / 2})

,

s u m 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} v a r e p s i l o n^{- 2} d e l t a^{- 1})

operations to produce an estimate that has

v a r e p s i l o n

-relative error with probability

1 - d e l t a

. In addition, if

m a x_{j} c_{j} = o (d^{1 / 4 - d e l t a_{0}})

for some

d e l t a_{0} > 0

, the same coverage can be guaranteed with

O (d^{3} v a r e p s i l o n^{- 2} l o g (d e l t a^{- 1}))

operations.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Efficient importance sampling for binary contingency tables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2389598)