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.