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

\Pr(S - \mathrm{E}[S] \geq nt). \qquad\textbf{correct}

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

\Pr(S/n - \mathrm{E}[S/n] \geq t), \qquad\textbf{correct}

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

\Pr(S - \mathrm{E}[S] \geq t), \qquad\textbf{wrong}

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.

[edit] Special case of Bernstein's inequality

Can someone point out which Bernstein inequality Hoeffding's inequality is a special case of?--Steve Kroon 14:10, 22 May 2007 (UTC)