Talk:Hoeffding's inequality

From Wikipedia, the free encyclopedia

As stated, the inequality is not true (this is easy to see for n=1). There must be some other condition. coco

I noticed that you added the condition t > 0, which is indeed required. Is there another condition we're missing? --MarkSweep 21:17, 21 August 2005 (UTC)

[edit] Hoeffding's theorem 2

I just reverted an edit which (re)introduced a mistake in the presentation of the inequality. As stated here, the inequality involves the probability

Note that S is the sum of n independent random variables. This probability could also be written as

which is how it appears in Hoeffding's paper (Theorem 2, p. 16, using slightly different notation). In other words, Hoeffding's formulation is in terms of the mean of n independent RVs, whereas the formulation used here is in terms of their sum. A recent edit changed this to

which is incorrect. --MarkSweep (call me collect) 18:50, 24 November 2005 (UTC)

Why do we need that X_i's have finite first and second moments? It is not stated in the Hoefdding paper and after all, I think it follows from that X_i lies in [a_i, b_i] i.e. bounded interval.

The article has no mistakes - the condition t>0 is not nessecary and the last comment is obvious. Nevertheless, by a Hoeffding type inequality is meant an inequality, which uses the transform f(t)=exp(h(t-x)) to derive bounds for tail probabilities for sums of independent r.v. and martingales. Therefore, the written inequality is only one of the inequalities Hoeffding introduced, but, regarding it from a statistical point of view, that is not the most important result as it doesn't control the variance of the variables. I would suggest to add the other inequality and explain what is meant by saying "Hoeffding inequality", as it is not one thing.