Example from class on 11/7/08
X is a bernoulli RV with Pr[x=1]=p (unknown)
N samples xi...xn
$ p_{ML} = \frac{\sum_i xi}{n} $
$ E[p_{ML}]=p $
$ Var(p_{ML})=\frac{Var(X)}{n}=\frac{p(1-p)}{n} $
$ Pr[|p_{ML}-p|<=\epsilon] = Pr[|p_{ML}-E[p_{ML}]|<=\epsilon] = 1- Pr[|p_{ML}-E[p_{ML}]|>\epsilon] $
now,
$ Pr[|p_{ML}-E[p_{ML}]|>\epsilon]<=\frac{Var(p_{ML})}{\epsilon^2} $ CHEBYSHEV INEQUALITY
So
$ Pr[|p_{ML}-p|<=\epsilon]>= 1 - \frac{Var(p_{ML})}{\epsilon^2} = \frac{1-p(1-p)}{n\epsilon^2} >= 1 - \frac{1}{4n\epsilon^2} $
So now,
$ p(1-p)<=\frac{1}{4} $
And finally,
$ Pr[|p_{ML}-p|<=\epsilon]>=1 - \frac{1}{4n\epsilon^2} $
