View Single Post
Old 09-14-2013, 07:28 PM
yaser's Avatar
yaser yaser is offline
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,478
Default Re: Satisfying Hoeffding's inequality

Originally Posted by diado View Post
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.

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.
Where everyone thinks alike, no one thinks very much
Reply With Quote