Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

The original false negative rate approximation can be proved (correctly) using Martingale arguments as done by Mitzenmacher and Upfal in 2005. The Wikipedia page also shows this version.


Ah, that's a new change on the wikipedia page, when I started work on this proof back in December, the Wikipedia page actually had the incorrect derivation.

Additionally, Bloom's original bound is given (and typically quoted) as an exact expression for the false positive rate, so while it may be correct as an approximation, I'd say its fair to say that the original bound is wrong.


Yeah, it's only right asymptotically. It's nice work testing some of those things in coq.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: