guest5123 science forum beginner
Joined: 17 Apr 2006
Posts: 1
|
Posted: Mon Apr 17, 2006 10:53 pm Post subject:
Question about Chernoff bounds
|
|
|
Hi,
I need to use the Chernoff bound P(X<= gamma*n*p) for binomial
distribution
there seem to be several versions. One appears in books and etc. and it
says
P(X<= gamma*n*p)<=exp{-(1-gamma)^np/2}
and the other in Wikipedia and several sites that copied from it, and
it says
P(X> gamma*n*p)>exp{-n/(2(p-1/2)^2)}
These two versions seem very different. Is the wikipedia version
correct?
Can someone point me to a proof of it?
Thanks a lot |
|