Problem 5.1b

[Sandes]

I get as far as this
P ≥ 1 - 4mH(N)^2/e^(N/32)

but I'm not certain how to go about showing that P ≥ 1 - mH(N)/2^N

Maybe I have totally the wrong approach:
I started with
Eout(h) ≤ Ein(h) + sqr (8/N ln(4mH(N)^2/δ)) with P ≥ 1-δ
So perhaps there's another formula that would work better. I feel like I'm making a silly mistake somewhere but I'm not sure what it could be.

[magdon]

If the data is generated from a random (arbitrary) target function, then every dichotomy is equally likely. Since you can implement at most m(N) of these dichotomies, the number of dichotomies you cannot implement is at least 2^N-m(N). Each of these dichotomies you cannot implement has probability 1/2^N

Originally Posted by Sandes

I get as far as this
P ≥ 1 - 4mH(N)^2/e^(N/32)

but I'm not certain how to go about showing that P ≥ 1 - mH(N)/2^N

Maybe I have totally the wrong approach:
I started with
Eout(h) ≤ Ein(h) + sqr (8/N ln(4mH(N)^2/δ)) with P ≥ 1-δ
So perhaps there's another formula that would work better. I feel like I'm making a silly mistake somewhere but I'm not sure what it could be.

[samarhabibi]

I just want to say thank you, my problem is solved