Exercise 2.2

Answers

(a)

(i): $k = 2$ , $RHS = \sum_{i = 0}^{1} (\binom{N}{i}) = N + 1$ , while $m_{H} (N) = N + 1$ , so $m_{H} (N) \leq \sum_{i = 0}^{k} (\binom{N}{i})$
(ii): $k = 3$ , $RHS = \sum_{i = 0}^{2} (\binom{N}{i}) = \frac{N (N - 1)}{2} + N + 1 = \frac{N (N + 1)}{2} + 1$ , while $m_{H} (N) = (\binom{N + 1}{2}) + 1 = \frac{N (N + 1)}{2} + 1$ , so $m_{H} (N) \leq \sum_{i = 0}^{k} (\binom{N}{i})$
(iii): There’s no such $k$ exists. Maximum $k = N + 1$ , since $\sum_{i = 0}^{N} (\binom{N}{i}) = 2^{N}$ , we still have $m_{H} (N) \leq \sum_{i = 0}^{k} (\binom{N}{i})$

(b)

m_{H} (N) = N + 2^{\frac{N}{2}}

, then the break point

k = 3

. According to bound theorem 2.4, we have for all

N

m_{H} (N) = N + 2^{\frac{N}{2}} \leq \sum_{i = 0}^{2} (\binom{N}{i}) = \frac{N (N + 1)}{2} + 1

. But this won’t hold for all

N

since left hand side is exponentially increasing while the RHS is polynomical increasing. For example, when

N = 20

, the inequality breaks. So such hypothesis set doesn’t exist.

niuers

2021-12-07 22:02