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} $


Back to ECE302 Fall 2008 Prof. Sanghavi

Alumni Liaison

Ph.D. 2007, working on developing cool imaging technologies for digital cameras, camera phones, and video surveillance cameras.

Buyue Zhang