4 ms·
The original false negative rate approximation can be proved (correctly) using Martingale arguments as done by Mitzenmacher and Upfal in 2005. The Wikipedia pag
by thomasahle 6y ago
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.
- gopiandcode 6y agoAh, 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.
- thomasahle 6y agoYeah, it's only right asymptotically. It's nice work testing some of those things in coq.