From Samples to Probabilities

(7th-September-2020)

• Probabilities can be estimated from a set of examples using the sample average. The sample average of a proposition α is the number of samples where α is true divided by the total number of samples. The sample average approaches the true probability as the number of samples approaches infinity by the law of large numbers.

• Hoeffding's inequality provides an estimate of the error of an unconditional probability given n samples:

• Proposition. [Hoeffding] Suppose p is the true probability, and s is the sample average from n independent samples; then

• P(|s-p|>ε) ≤ 2e-2nε2.

• This theorem can be used to determine how many samples are required to guarantee a probably approximately correct estimate of the probability. To guarantee that the error is less than some ε<0.5, infinitely many samples are required. However, if you are willing to have an error greater than ε in δ of the cases, you can solve 2e-2nε2<δ for n, which gives

• n>-ln(δ/2)/(2ε2).