LFD Book Forum - View Single Post

jsarrett · #7 04-14-2012, 12:00 AM

Hoeffding's inequality has a free parameter in your question, namely $\epsilon$ . It lest you say that since you have 10 samples, if you want to be 80% sure of the distribution of marbles in the jar ( $\epsilon = 0.2$ ), then the jar is at most $E_{out}$ percent different from the sample.

where
$P(|E_{in}-E_{out}| < \epsilon) \le 2e^{-2\epsilon^2N}$

substituting from your example:
$P(|0-E_{out}| < 0.2) \le 2e^{-2(0.2^2)10}$

simplifying:
$P(|0-E_{out}| < 0.2) \le 0.898657928234443$
so we think that with 80% confidence, the jar is at least 10.2% green.

We probably need a bigger N!