What does it mean to "satisfy" Hoeffding's Inequality?

gordonbr · #1 04-16-2012, 08:20 AM

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?

yaser · #2 04-16-2012, 11:10 AM

Quote:

Originally Posted by gordonbr

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.

gordonbr · #3 04-16-2012, 12:39 PM

Thanks, professor! That clears it up.

ripande · #4 01-14-2013, 11:26 AM

Is Hoeffding's Inequality true for every experiment and hypothesis ? Is it possible that P[Ein -Eout] for some hypothesis is not bounded by 2exp( -2e2N) ?

yaser · #5 01-14-2013, 11:37 AM

Quote:

Originally Posted by ripande

Is Hoeffding's Inequality true for every experiment and hypothesis ? Is it possible that P[Ein -Eout] for some hypothesis is not bounded by 2exp( -2e2N) ?

If you fix any hypothesis then run the experiment, the probability will always be bounded by that term.

ripande · #6 01-15-2013, 12:37 PM

I am sorry, but I still dont get it. Let us say one person is tossing a fair coin 10 times and got all heads. Here one coin refers to one hypothesis correct ?, so that is fixed. N is also fixed to 10. Does this mean that this experiment would satisfy hoefding's inequality ?

I am confused by the statement that hoeffding's inequlity is universally true for fixed hypothesis and experiment.

Thread Tools
Show Printable Version Email this Page
Display Modes
Switch to Linear Mode Hybrid Mode Switch to Threaded Mode