View Single Post
Old 04-16-2012, 10:10 AM
yaser's Avatar
yaser yaser is offline
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,478
Default Re: What does it mean to "satisfy" Hoeffding's Inequality?

Originally Posted by gordonbr View Post
I'm confused about the process of determining whether a particular random sample "satisfies" Hoeffding's inequality.

In particular, when we run some experiments and determine the average proportion of green marbles, we generate some averages for several E_{in} values. Can't we say that all of these E_{in} values satisfy Hoeffding's Inequality, since Hoeffding's Inequality only says that the probability of something bad happening (i.e., E_{in} not tracking E_{out}) for a random sample is small? I would think that any E_{in} satisfies this condition, regardless of how we determined the sample.

I suppose my question is: how does a particular E_{in} value fail to satisfy an inequality that seems to be a blanket statement for all possible E_{in} values?
If the expression "satisfies Hoeffding's inequality" is used for a particular E_{\rm in}, it is informal or figurative. It just says that this particular E_{\rm in} is within \epsilon of E_{\rm out}. Hoeffding asserts that this is likely to be the case, hence the word "satisfies."

The formal statement would not involve an individual E_{in}, but rather a full experiment, and it would be a statement that Hoeffding's inequalty holds under the conditions of such experiment. For instance, the multiple-bin experiment does not satisfy the basic Hoeffding inequality.
Where everyone thinks alike, no one thinks very much
Reply With Quote