A Caltech Library Service

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

Schulman, Leonard J. and Vazirani, Vijay V. (2005) A Computationally Motivated Definition Of Parametric Estimation And Its Applications To The Gaussian Distribution. Combinatorica, 25 (4). pp. 465-486. ISSN 0209-9683. doi:10.1007/s00493-005-0028-4.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription ReadCube access
Schulman, Leonard J.0000-0001-9901-2797
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.
Issue or Number:4
Classification Code:Mathematics Subject Classification (2000): 68Q15; 68Q25; 68W20; 68W25; 62F25
Record Number:CaltechAUTHORS:20190820-150854373
Persistent URL:
Official Citation:Schulman, L.J. & Vazirani, V.V. Combinatorica (2005) 25: 465.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98047
Deposited By: Tony Diaz
Deposited On:20 Aug 2019 23:08
Last Modified:16 Nov 2021 17:36

Repository Staff Only: item control page