Talk:Chernoff bound

From Wikipedia, the free encyclopedia

Mathematics Portal

This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.

Mathematics rating:

Start Class

Low Priority

Field: Probability and statistics

Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments.
Please add to or update the comments to suggest improvements to the article.
Please add useful comments here--Cronholm144 10:36, 23 May 2007 (UTC)

This article is within the scope of WikiProject Statistics, which collaborates to improve Wikipedia's coverage of statistics. If you would like to participate, please visit the project page.

[edit] Merge with Chernoff Bounds

The other page just presents a bit more technical stuff. Could probably be merged pretty easily. Thoughts?

I think Chernoff bound is just a special case of the Chernoff bounds. So, it should be presented appropriately. Definitely merged, in either case. Else, its too confusing. —Preceding unsigned comment added by 24.47.50.165 (talk) 15:46, 18 December 2007 (UTC)

Merge it. Having two articles is really confusing, and I don't see how they differ, or relate to each other. 71.163.207.130 19:43, 14 October 2007 (UTC)

[edit] Possibly old stuff

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.

[edit] Addition 13 June 2008

This seems to have left some problems:

What is a "Poisson trail": is this defined somewhere? (link?)
Appears to duplicate material later in article, under "Theorem (relative error)".
Incompleteness: eg $\Pr(X_i) = p_i$ possibly needs an "=1" in it, depending on what a "Poisson trail" is.