Problem 2.14(c)

joseqft · #11 11-11-2019, 05:19 AM

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

$7(d_{VC}+K)\log_2(d_{VC}K)$ .

is a valid $\ell$ as explains magdon in

Quote:

Originally Posted by magdon

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

.

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

Thread Tools
Show Printable Version Email this Page
Display Modes
Switch to Linear Mode Switch to Hybrid Mode Threaded Mode