4 ms·
Fun fact that I had to prove for my master's thesis: if you have a procedure that (independent from other estimates) estimates a mean with absolute or relative
by nightcracker 5y ago
Fun fact that I had to prove for my master's thesis: if you have a procedure that (independent from other estimates) estimates a mean with absolute or relative error eps with probability 1/2 + g, then you can boost that to an arbitrary probability 1 - d using the median of O(log(1/d) / g^2) estimates. So repeated often enough, "probably approximately correct" can become "almost surely approximately correct", with an overhead factor linear in the number of zeroes you want in the failure probability.
- howlin 5y ago> (independent from other estimates) That little phrase is doing a lot of work in your theorem :)
- nightcracker 5y agoWhen working with real-world statistics? Absolutely, there is no reason to believe that this assumption holds. But the context is randomized (quantum) algorithms, where this is trivial to guarantee.