Problem 2.10

[wolszhang]

I understand that for the case m(N) = 2^N, we can show that this is true. But how do we prove it when m(N) < 2^N? It seems like every single theorem is giving me an upper bound. Any hints would be super appreciated.

[magdon]

Hint: Any dichotomy 2N points can be viewed as a dichotomy on the first N points plus a dichotomy on the second N points.

Originally Posted by wolszhang

I understand that for the case m(N) = 2^N, we can show that this is true. But how do we prove it when m(N) < 2^N? It seems like every single theorem is giving me an upper bound. Any hints would be super appreciated.

[EliLee]

I am still not quite clear about this problem. To prove this problem is true for all N values, I think we should discuss different relationship between break point k, N and 2N. I can prove that when N < 2N < k or k is infinite, the inequality holds. Also when N < k < 2N, the in equality also holds. When k < N < 2N, do you mean mH(2N) = 2mH(N)? However I did not figure it out.

[pdsubraa]

@Magdon - Can you explain us in detail.

That would help!

Thanks for your time!

[magdon]

For example, if you have 10 ways to dichotomize 4 points and 8 ways to dichotomize another 4 points , for each of the 10 ways for the first 4 points there are at most 8 ways to dichotomize the second 4 points (why?). Therefore, there are at most ways to dichotomize all 8 points.

Originally Posted by pdsubraa

@Magdon - Can you explain us in detail.

That would help!

Thanks for your time!