LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 1 (http://book.caltech.edu/bookforum/forumdisplay.php?f=130)
-   -   Satisfying Hoeffding's inequality (http://book.caltech.edu/bookforum/showthread.php?t=4415)

 diado 09-13-2013 10:51 PM

Satisfying Hoeffding's inequality

I've read the thread here, but still being confused
After using the union bound, we get the sum of individual terms and apply Hoeffding's inequality to each of them. Why is it valid? Aren't they still the multiple bins cases? It seems to me that they transfrom from multiple bins to single bin after using the union bound, but I don't know why.

Thanks!

 yaser 09-14-2013 07:28 PM

Re: Satisfying Hoeffding's inequality

Quote:
 Originally Posted by diado (Post 11485) I've read the thread here, but still being confused After using the union bound, we get the sum of individual terms and apply Hoeffding's inequality to each of them. Why is it valid? Aren't they still the multiple bins cases? It seems to me that they transfrom from multiple bins to single bin after using the union bound, but I don't know why. Thanks!
Each term involves one fixed bin (hypothesis), so Hoeffding applies to it by itself, irrespective of what happens to the others. What the union bound does is to get the answer for the multiple bins if you know what happens to each bin by itself.

 All times are GMT -7. The time now is 08:09 AM.