A computationally motivated definition of parametric estimation and its applications to the Gaussian distribution (Q2568500)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A computationally motivated definition of parametric estimation and its applications to the Gaussian distribution |
scientific article |
Statements
A computationally motivated definition of parametric estimation and its applications to the Gaussian distribution (English)
0 references
27 June 2006
0 references
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.
0 references
theory of parametric estimation
0 references
estimator optimality in variance
0 references
estimator optimality in probability
0 references
general penalty functions
0 references
multidimensional spherically symmetric Gaussians
0 references
average matching size in a given graph
0 references
estimating algorithms
0 references
fully polynomial randomized approximation scheme
0 references