Talk:Chernoff bound

From Wikipedia, the free encyclopedia

i dont understand how to apply the chernoff theorem please discuss some views on it thank you bbye

There's a mistake! The bound P(sum_i X_i>n/2)=1-epsilon>1-exp(-...) (where X_i=1 if the event E_i happened and X_i=0 otherwise) gives an UPPER bound on n, NOT a lower bound as is given in the second formula in the page! The interpretation is wrong too: it takes no more than 150 coin flips to guess the side of the biased coin with 95% accuracy. This error is also evident from the first graph (it isn't too clear what it represents, but it obviously tells us that the Chernoff bound is an upper bound to n with respect to other strategies)

I suggest the formula P(sum_i X_i>n/2)=1-epsilon>1-exp(-2n(p-1/2)^2) (where X_i=1 if the event E_i happened and X_i=0 otherwise) is added to make the bound more obvious.