Problem 1.10

[dsevero]

a) Define a miss as h(x) \neq f(x) for some x, and a hit when h(x) = f(x).
By definition, f(x) = 1 for all x. Now, since h(x_k) \neq 1 for even k, we have that a miss when k is even. Hence E_{off}(h, f) = \frac{Number of **even** m between 1 and M}{M}, resulting in E_{off}(h, f) = 1/2.

I think you got it the other way around.

b) Isn't this the same idea as section 1.3.1? The idea is that you can vary all points outside the training set and still have f generate D. Since \mathcal{Y} = \{ -1, +1\}, each point x outside of the training set can have 2 possible f(x) = y. Therefore, it should be 2^M and not 2^N

[sharov-am]

@dsevero : Hi. I also got 2^M for b) and 1/2 for d). I saw few other solutions -- one on book site(forum), other is pdf on github where solutions are also 2^M. But does it really make sense? Because if correct answer for b) is 2^M and for d) (in my case) 1/2 then is learning feasible? No matter what we do we always have out-of-sample error about 1/2.

Also I think in solution for a) there is a typo: for even k we have 1/2, for odd -- 1/2 + 1/M

By the way, I would like to thank @ppaquay for this really great job of making solutions.

[KaixinHe]

@sharov-am Well, I feel in the case that M is odd, whether N is odd should also be considered, here is how we go(only considering the subscripts):
if M is odd, (M-1)/2 odd numbers and (M+1)/2 even numbers in the range of [1, M], but if N is odd, (M-1)/2 even and (M+1)/2 odd in [N+1,N+M] while N is even, (M-1)/2 odd and (M+1)/2 even
so we'll get different answers when changing the remainder of N divided by 2
also, what's your opinion towards 1.10 (e)?I can't figure out a way to prove it