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}](../../../math/7/d/7/7d7c6e6610ea6ed8d46bd55acfeb2a20.png)
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}](../../../math/8/4/6/846f9e44751516b5e921e22fe67f8956.png)
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}](../../../math/a/8/2/a826db5ab5293bdfa90f5a55e3c6b49d.png)
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.
