A plot of Hoeffding’s inequality

The Hoeffding's inequality is a very tight bound on the concentration of the average around the mean (see second image). Here delta is this upper bound (the confidence), whereas epsilon is the precision. This plot essentially shows that "confidence is cheap but precision is expensive" Barely any more samples are needed to get a much [...]