(New page: Example from class on 11/7/08 X is a bernoulli RV with Pr[x=1]=p (unknown) N samples xi...xn <math> p_{ML} = \frac{\sum_i xi}{n} </math> <math> E[p_{ML}]=p </math> <math> Var(p_{ML})=...) |
|||
| Line 1: | Line 1: | ||
| + | |||
| + | [[Category:ECE302Fall2008_ProfSanghavi]] | ||
| + | [[Category:probabilities]] | ||
| + | [[Category:ECE302]] | ||
| + | [[Category:problem solving]] | ||
| + | |||
Example from class on 11/7/08 | Example from class on 11/7/08 | ||
| Line 32: | Line 38: | ||
<math>Pr[|p_{ML}-p|<=\epsilon]>=1 - \frac{1}{4n\epsilon^2}</math> | <math>Pr[|p_{ML}-p|<=\epsilon]>=1 - \frac{1}{4n\epsilon^2}</math> | ||
| + | ---- | ||
| + | [[Main_Page_ECE302Fall2008sanghavi|Back to ECE302 Fall 2008 Prof. Sanghavi]] | ||
Latest revision as of 12:39, 22 November 2011
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} $
