LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Chapter 2 - Training versus Testing (http://book.caltech.edu/bookforum/forumdisplay.php?f=109)
-   -   Problem 2.5 (http://book.caltech.edu/bookforum/showthread.php?t=4704)

CountVonCount 10-25-2016 02:46 AM

Problem 2.5
 
Hello,

I tried to prove the unequally of problem 2.5 on page 69:

https://latex.codecogs.com/gif.latex...+&space;1

However I was not able to find a good prove. I tried by using the same scheme like in the prove for

https://latex.codecogs.com/gif.latex...ce;=&space;2^N

But I had no success.

Can anyone give me the answer or at least a hint, how to start the prove well?

Thanks a lot,
André

P.S.: Is there a good way to embedd latex to this Forum? At the moment I just use https://www.codecogs.com for generating latex pictures.

P.P.S.: The book is very good and the course videos make a lot of fun to watch. Really: Thanks to everyone who worked on it!

ntvy95 11-14-2016 09:18 PM

Re: Problem 2.5
 
I hope that I didn't make any mistake.

Base cases:

D = 0: \sum_{i=0}^{0}\binom{N}{i} \leq N^{0} + 1 \Leftrightarrow 1 \leq 2
D = 1: \sum_{i=0}^{1}\binom{N}{i} \leq N^{1} + 1 \Leftrightarrow N + 1 \leq N + 1
D = 2: \sum_{i=0}^{2}\binom{N}{i} \leq N^{2} + 1 \Leftrightarrow \frac{N^{2}}{2} + \frac{N}{2} + 1 \leq \frac{N^{2}}{2} + \frac{N^{2}}{2} + 1 \leq N^{2} + 1

Induction step for D > 2:

\sum_{i=0}^{D}\binom{N}{i} = \sum_{i=0}^{D-1}\binom{N}{i} + \binom{N}{D} \leq N^{D-1} + 1 + \binom{N}{D}

I will prove \frac {N!}{(N-D)!} \leq N^{D} later, for now, I will use its result:

N^{D-1} + 1 +\binom{N}{D} \leq N^{D-1} + 1 + \frac {N^{D}}{D!}

D > 2 \Rightarrow D! > 2 \Leftrightarrow \frac{1}{D!} < \frac{1}{2} :

N^{D-1} + 1 + \frac {N^{D}}{D!} \leq N^{D-1} + 1 + \frac {N^{D}}{2}

D > 2, N \geq D \Rightarrow N > 2 \Leftrightarrow \frac {1}{N} < \frac {1}{2} \Leftrightarrow \frac {N^{D-1}}{N^{D}} < \frac {1}{2} \Leftrightarrow N^{D-1} < \frac {N^{D}}{2}:

N^{D-1} + 1 + \frac {N^{D}}{2} \leq \frac {N^{D}}{2} + 1 + \frac {N^{D}}{2} \leq N^{D} + 1

So \sum_{i=0}^{D}\binom{N}{i} \leq N^{D} + 1 follows.

Quote:

Prove:

\frac {N!}{(N-D)!} \leq N^{D}
\frac{1}{N^{D}} \times \frac {N!}{(N-D)!} = \frac{1}{N^{D}} \times \prod_{i=0}^{D+1} (N - i) = \prod_{i=0}^{D+1} \frac{N - i}{N^{D}} \leq 1

k_sze 03-16-2018 10:07 AM

Re: Problem 2.5
 
Quote:

Originally Posted by ntvy95 (Post 12511)
\frac{1}{N^{D}} \times \frac {N!}{(N-D)!} = \frac{1}{N^{D}} \times \prod_{i=0}^{D+1} (N - i) = \prod_{i=0}^{D+1} \frac{N - i}{N^{D}} \leq 1

Aside from the slight mistake in the product (it should be \prod_{i=0}^{D-1} (N - i)), the whole proof is just amazing! How did you even come up this chain of logic and deduction?


All times are GMT -7. The time now is 09:47 AM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.