Chapter 1 - Exercise 1.9

[goldsj3]

Based on the marbles example, I understand that u is the probability of choosing a red marble from the bin of marbles and v is the fraction of red marbles in the sample of chosen marbles. And I think that the LHS of the Hoeffding Inequality represents the probability of v deviating from u being greater than the error bar epsilon. Now, I am not sure how I should choose an epsilon to evaluate this probability and where I should begin. Can someone point me in the right direction?

[magdon]

If and , it implies that (any number slightly less than 0.8). By the implication bound,



By looking at the RHS, one can identify for applying the Hoeffding bound.

[eshmrt]

Since we're only looking at epsilon applied in one direction, meaning that we're only interested in nu being mu - 0.8 and not mu + 0.8, should we drop the leading 2 from the bound calculation? I'm not sure if I'm interpreting this bound correctly or simply overthinking things.

[magdon]

You are right. If al you want is the "one sided deviation", you could drop the factor of 2. However keeping the factor of 2 is a worse but still valid bound.

Originally Posted by eshmrt

Since we're only looking at epsilon applied in one direction, meaning that we're only interested in nu being mu - 0.8 and not mu + 0.8, should we drop the leading 2 from the bound calculation? I'm not sure if I'm interpreting this bound correctly or simply overthinking things.

[henry2015]

Originally Posted by magdon

If and , it implies that (any number slightly less than 0.8). By the implication bound,



By looking at the RHS, one can identify for applying the Hoeffding bound.

Hi, I am a bit confused.

I thought when it says , it means because smallest probably is 0; hence, ....I am sure I miss something.

Any pointer?

Thanks!

[mike7]

Originally Posted by magdon

If and , it implies that (any number slightly less than 0.8). By the implication bound,



By looking at the RHS, one can identify for applying the Hoeffding bound.

If I am understanding the implications of this correctly, is too large within the Hoeffding bound, correct? One would need to select some , perhaps arbitrarily?