Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 2005 | public
Journal Article

A Computationally Motivated Definition Of Parametric Estimation And Its Applications To The Gaussian Distribution


We introduce a treatment of parametric estimation in which optimality of an estimator is measured in probability rather than in variance (the measure for which the strongest general results are known in statistics). Our motivation is that the quality of an approximation algorithm is measured by the probability that it fails to approximate the desired quantity within a set tolerance. We concentrate on the Gaussian distribution and show that the sample mean is the unique "best" estimator, in probability, for the mean of a Gaussian distribution. We also extend this method to general penalty functions and to multidimensional spherically symmetric Gaussians. The algorithmic significance of studying the Gaussian distribution is established by showing that determining the average matching size in a graph is #P-hard, and moreover approximating it reduces to estimating the mean of a random variable that (under some mild conditions) has a distribution closely approximating a Gaussian. This random variable is (essentially) polynomial time samplable, thereby yielding an FPRAS for the problem.

Additional Information

© 2005 János Bolyai Mathematical Society. Received December 20, 2001. We wish to thank Prof. D. Blackwell and Prof. C. R. Rao for helping us confirm the status of Theorem 2.

Additional details

August 19, 2023
October 18, 2023