ECCC-Report TR05-001https://eccc.weizmann.ac.il/report/2005/001Comments and Revisions published for TR05-001en-usMon, 03 Jan 2005 10:44:49 +0200
Paper TR05-001
| Near optimality of the priority sampling procedure |
Mario Szegedy
https://eccc.weizmann.ac.il/report/2005/001Based on experimental results N. Duffield, C. Lund and M. Thorup \cite{dlt2} conjectured
that the variance of their highly successful priority sampling procedure
is not larger than the variance of the threshold sampling procedure with sample size one smaller.
The conjecture's significance is that the latter procedure is provably optimal among all
{\em off-line} sampling procedures.
Here we prove this conjecture. In particular, our result gives an affirmative answer to the conjecture of
N. Alon, N. Duffield, C. Lund and M. Thorup \cite{adlt}, which states that the standard deviation for
the subset sum estimator obtained from $k$ priority samples is upper bounded by $W/\sqrt{k-1}$.
($W$ is the actual subset sum.)
Mon, 03 Jan 2005 10:44:49 +0200https://eccc.weizmann.ac.il/report/2005/001