Exercises and Problems

[Roelof]

Originally Posted by yaser

Interesting question indeed. Hoeffding does apply to each randomly selected coin individually as you point out. If the coins have different values of , then the added randomization due to the selection of a coin affects the relationship between and . This is exactly the premise of the complete bin model analysis.

As I understand it each coin will represent a separate bin and each flip will represent a marble in the bin. The target function determines if any particular flip will be heads or tails. Note that coins that have different degrees of fairness will have different target functions.

The definition and subsequent analysis makes the assumption that there is a single target function f which we are trying to approximate. Clearly, if there are multiple target functions then we don't satisfy the initial assumptions for using the learning algorithm.