Thread: Problem 2.14(c)
View Single Post
Old 11-11-2019, 05:19 AM
joseqft joseqft is offline
Junior Member
Join Date: Dec 2015
Posts: 1
Default Re: Problem 2.14(c)

Ive been struggling with this problem too. Essentialiy we have to prove that the second expression in the min expression


is a valid \ell as explains magdon in

Originally Posted by magdon View Post
Rather than solve the inequality in (b) to get this bound, you may rather just verify that this is a bound by showing that if \ell=7(d_{VC}+K)\log_2(d_{VC}K), then the inequality in (b) is satisfied, namely 2^\ell>2K\ell^{d_{VC}}.
this means that the inequality

(d_{VC}+K)^{7(d_{VC}+K)} > 2K\left[7(d_{VC}+K)\log_2(d_{VC}K)\right]^{d_{VC}} (1)

must be satisfied.

I have been finding upper bounds to the right hand side of (1), using the following tricks

d_{VC}+K \geq d_{VC}K if d_{VC}\geq 2 (the case d_{VC}= 1 must be proved apart).

\log_2(d_{VC}K) < d_{VC}K,

7 < 2^3 \leq K^3, because K \geq 2 (this is not the seven in the exponent) and

K + 1< K^2.

Then we arrive at an expression that can be compared easily with the left hand side of (1) proving that this inequality is valid.
Reply With Quote