Majorizing estimators and the approximation of #P-complete problems
Leonard J. Schulman, Vijay V. Vazirani · 1999
A key step in counting via sampling is constructing an onbiased estimator, X, for the parameter .9 in question, and proving a bound on its second moment, E(X').A key applacation of this method is to obtaining a FPRAS for a #Pcomplete problem; a FPRAS results if the ratio r = m EIW is polynamially bounded in the size of the input.We show that if no additional information is available about the dis tribution of X, then this condition is also necessary.The proof involves establishing a new optimality result in parametric statistics.We introduce the notion of a majorizing estimator, a very strict optimality requirement that we need for making wont-case (over inputs) and in-probability (of falling in the desired accuracy range of the parameter 8) statements.We show that for the problem of estimating the mean of a Gaussian distribution (from the variable-location, fixed-scale family {GB}), the sample mean is a majorizing estimator.An extension of this argument shows that the sample mean is an optimal estimator in every central moment among all estimators.To compare, the celebrated Cramer-Rae lower bound, applied to the family {CS}, establishes that the sample mean is the optimal estimator in mean square error among alI unbiased estimators.We fixther show that the mean estimator is the unique majorizing estimator for {Ge}.