Thread: Question 2
View Single Post
Old 04-13-2013, 01:23 AM
yaser's Avatar
yaser yaser is offline
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,478
Default Re: Question 2

Originally Posted by Ziad Hatahet View Post
But given the quote in my first post, doesn't it mean that the bin chosen by this procedure is not bound by 2e^{-2\epsilon^2N}?
This is discussed here:

The main point is that once you consider the sample, the probability becomes conditional on how this sample came out, and that could violate the 2e^{-2\epsilon^2N} bound, whereas the probability before a sample was drawn always obeys the bound.
Where everyone thinks alike, no one thinks very much
Reply With Quote