A computationally motivated definition of parametric estimation and its applications to the Gaussian distribution (Q2568500)

The aim of the present paper is to initiate a theory of parametric estimation in which optimality of an estimator is measured in probability rather then in variance, in the worst case over the possible values of the parameter. The reason of the considered approach is that the quality of an approximation algorithm is measured by the possibility that it fails to approximate the desired quantity within a set tolerance. The main results of the paper refer to the Gaussian distribution, since it lends itself to a very precise analysis and it arises naturally in several computational situations. The authors prove that the sample mean is the unique ``best'' estimator, in probability, for the mean of a Gaussian distribution. The method is extended to general penalty functions and to multidimensional spherically symmetric Gaussians. The algorithmic significance of studying the Gaussian distribution is established on the problem of computing the average matching size in a given graph. The exact computation of this parameter is shown to be a \(\#\)P-hard (n.b. similar notation, NP-hard), while approximating this parameter reduces to estimating the mean of a random variable that, under some mild condition, has a distribution closely approximating a Gaussian. Furthermore, the average matching size in a graph is proved to represent a variable whose estimating algorithm is shown to be yielded as a fully polynomial randomized approximation scheme.