__
TR05-001 | 1st January 2005 00:00
__

#### Near optimality of the priority sampling procedure

**Abstract:**
Based 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.)