LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 2 (http://book.caltech.edu/bookforum/forumdisplay.php?f=131)
-   -   Hoeffding’s inequality (http://book.caltech.edu/bookforum/showthread.php?t=880)

raghu 07-24-2012 05:37 AM

Re: Hoeffding’s inequality
 
From what I understood we are sampling a coin's error 100,000 times and then we plot the probability distribution and this should satisfy the Hoffding inequality.

fgpancorbo 07-24-2012 03:10 PM

Re: Hoeffding’s inequality
 
Quote:

Originally Posted by raghu (Post 3633)
From what I understood we are sampling a coin's error 100,000 times and then we plot the probability distribution and this should satisfy the Hoffding inequality.

Statistically speaking, there is no difference between c_1 and c_rand.
One way to see this is to consider you have only 1 coin and want to know coin bias by using 10 experiments. If you just take that coin and perform the 10 experiments, you might, or might not, get 10*p (p is the bias) heads. To make sure that you have a statistically meaningful result, you average over 100000 different realizations of that experiment.

Now go back to the situation where you have the 1000 coins. c_1 obviously corresponds to the case where you have 1 coin only. However, if all 1000 coins have the same bias, when you average over 100000 realizations of the the experiment, it doesn't matter whether you pick, for a given realization, any of the available 1000 coins at random since they will all behave the same, statistically speaking.

The case of c_min is different because you are making the distinction of, for each realization, which one is the worst behaved vs how the average coin behaves (which is what c_1 and c_rand measure).


All times are GMT -7. The time now is 07:55 PM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2021, 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.