1
$\begingroup$

What is the name of the Theorem that ensures that it is enough to sample

$O(\epsilon^{-2} \log \delta^{-1})$ if one wants with probability $1-\delta$ an estimate that is correct within $\pm \epsilon$

?

  • 1
    It's called "the sampling theorem" here http://www.cs.princeton.edu/courses/archive/fall09/cos521/Handouts/probabilityandcomputing.pdf- but I confess I didn't know about it, even though I sensed the Chernoff bound smell... Perhaps this question should be migrated to stats.stackexchange.com?2012-04-28

0 Answers 0