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$

?

  • 0
    I changed \epsilon^{-1} log \delta^{-1} to \epsilon^{-1} \log \delta^{-1}. This does not only prevent "log" from being italicized, but it also results in proper spacing before and after it, and is standard $\TeX$ usage. I also changed $+-\epsilon$ to $\pm\epsilon$, coded as \pm\epsilon.2012-04-28
  • 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