Talk:Hoeffding's inequality

Jump to: navigation, search
WikiProject Statistics (Rated Start-class, Low-importance)

This article is within the scope of the WikiProject Statistics, a collaborative effort to improve the coverage of statistics on Wikipedia. If you would like to participate, please visit the project page or join the discussion.

Start  This article has been rated as Start-Class on the quality scale.
Low  This article has been rated as Low-importance on the importance scale.
WikiProject Mathematics (Rated Start-class, Low-importance)
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
 Start Class
 Low Importance
Field:  Probability and statistics

[no title]

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 ${\displaystyle t>0}$, which is indeed required. Is there another condition we're missing? --MarkSweep 21:17, 21 August 2005 (UTC)
I suggest that ${\displaystyle X_{i}\in [0,1]}$194.25.15.170 (talk) 13:45, 16 March 2015 (UTC)

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

${\displaystyle \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

${\displaystyle \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

${\displaystyle \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.

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)

The "which inequality is a special case of the other" is inconsistent in wikipeida: the article on Hoeffding ineq. says it's more general than Bernstein ineq. While the article on Bernstein ineq. says "special cases of Bernstein ineq. is ... Hoeffding ineq". Someone, please, fix this? -- 194.126.99.204 (talk) 13:11, 14 June 2012 (UTC)

Hoeffding's Inequality

Existing version is unreadable, Article ignores dependence of results on Bennett's Inequality —Preceding unsigned comment added by 122.106.62.116 (talk) 06:13, 27 February 2009 (UTC)

Variable Bounds

The bounds for variables X_i seem misleading

${\displaystyle \Pr(X_{i}-\mathrm {E} [X_{i}]\in [a_{i},b_{i}])=1.\!}$

Older revisions of this article (pre 2009), as well as the original paper state the bounds as

${\displaystyle a_{i}\leq X_{i}\leq b_{i}.\!}$

or

${\displaystyle \Pr(X_{i}\in [a_{i},b_{i}])=1.\!}$

--18.111.112.208 (talk) 18:00, 11 December 2010 (UTC)

It does not make any difference (I mean the first and the third version above, the second one is marginally stronger). What is misleading about it?—Emil J. 13:52, 13 December 2010 (UTC)
I think that the third version deals with centered versions of variable? 194.25.15.170 (talk) 13:43, 16 March 2015 (UTC) Sergey

Problem with bounds

To apply Hoeffding Lemma to the zero-mean variables ${\displaystyle Y_{i}=X_{i}-\mathrm {E} [X_{i}]}$ ,we must have ${\displaystyle Y_{i}\in [a_{i},b_{i}]}$ almost surely.

But, ${\displaystyle Pr(X_{i}-\mathrm {E} [X_{i}]\in [a_{i},b_{i}])=1}$ and ${\displaystyle Pr(X_{i}\in [a_{i},b_{i}])=1}$ are not equivalent.

Central limit theorem

Can someone elaborate on the relationship to the CLT? As I understand this, these two theorems are closely related. Thanks. --138.246.2.177 (talk) 10:04, 3 December 2012 (UTC)