R186  
Samplingbased Lower Bounds for Counting Queries
Vibhav Gogate and Rina Dechter

Abstract
It is well known that computing relative approximations of weighted counting queries such as the probability of evidence in a Bayesian network, the partition function of a Markov network, and the number of solutions of a constraint satisfaction problem is NPhard. In this paper, we settle therefore on an easier problem of computing highconfidence lower bounds and propose an algorithm based on importance sampling and Markov inequality for it. However, a straightforward application of Markov inequality often yields poor lower bounds because it uses only one sample. We therefore propose several new schemes that extend it to multiple samples. Empirically, we show that our new schemes are quite powerful, often yielding substantially higher (better) lower bounds than stateoftheart schemes.
[pdf] 