Thread: Multiple bins
View Single Post
Old 05-09-2012, 11:20 PM
markland markland is offline
Join Date: Apr 2012
Posts: 30
Default Re: Multiple bins

Interesting question. I think what's wrong with #2 is the order of events. Hoeffding applies when you pick your h(i) or H first and then get the data. If you or the magician has used the data to pick h(i) then it doesn't apply. But if you took the magician's h(i) and then sampled new data points, that even the magician hadn't seen yet, then one-bin Hoeffding would apply again, though of course in might turn out that Ein is no longer small on the new data sample.
Reply With Quote