Changeing the hypothesis while generating samples I'm currently reading / working through: Learning from Data: A short course by Abu-Mostafa et. al to familiarize my self with the shift in language from Stats to ML. In the section on feasibility we consider a hypothesis set $H = \{h_i(x)\} \; i=1,2,3...$ and the supervisor function $f(x)$ both of which are defined on some observation space $X$. 
We define out sample error as $E_{out}(h) = P[h(x) \neq f(x)] = P(\{x \in X \;|\; h(x) \neq f(x)\})$. In sample error, $E_{in}(h)$, is define similarly, with the notable exception of being restricted to the sample values $S \subset X$, that is $E_{in}(h) = P(\{x \in S \;|\; h(x) \neq f(x)\})$. The difference between these two values is bounded by the Hoeffding inequality $P[|E_{out}(h) - E_{in}(h)| < \epsilon] \leq 2e^{-2\epsilon^2N}$, where $N = |S|$, the number of samples. Here $E_{in}(h)$ is computable from the samples, and can serve as a bound on $E_{out}(h)$.
With this notation in hand we move to the ensemble $H$, and the author states that it is required that "$h$ is fixed before you generate the data set". This is the reason we have to resort to the union bound to ensure that $E_{in}(g)$ is close to $E_{out}(g)$ for our eventual choice $g$ from $H$.
My question is what breaks in the assumption of the Hoeffding inequality when we violate this rule of fixing the $h$ ahead of time? For example we could change our $h$ to map $x$ to higher or lower values if we notice that our previous errors were over or under the actual. If we do so, what is violated in Hoeffdings requirements. 
The book goes on to give an Exercise/Example (1.10), where we consider 1000 fair coins, each flipped 10 times (for 100,000 trials). We compare adherence to the Hoeffding inequality for 3 different coins choices. The first coin in the collection, a coin chosen randomly, and one chosen to minimize heads. It's clear that the min heads coin is introducing a bias, but the coins are all fair so the samples are still random. Since all the coins are fair the samples are still IID. So what is breaking down in the Hoeffinding proof?
 A: It turns out, the act of minimization causes the assumption of independence in the inequality to break down. In the statement of the Hoeffding inequality, there are really only two requirements, IID samples and that these samples come from a bounded RV. In our case the bound comes for free since the RV's are binary (simple coins). To see what breaks down in the given example we need to consider the process between trials for the experiment.
Let us number all the coins from 1 to 1000. Then flip each of them and begin our selection process for a single trial. The case of the "first" one means we simply choose coin with index 1. The case of the "random" coin means we select an index at random uniformly. These are the "obvious" cases. Since all the coins are fair between each trial selecting the first coin is equivalent to selecting a random coin (because the true parameters are all equal).
However the process for choosing the coin with the minimal number of heads (and thus the minimal sample mean since the sample mean can be written as $\frac{\#\;of\;heads}{10}$) is a bit more involved. The first step is to go through the entire list of coins to determine what the observed minimum is, and then the next step is to pick the first (lowest index) coin from that subset of coins that achieve this minimum. This selection of the minimum introduces a correlation by conditioning. To see this consider what the probability of selecting an arbitrary index (say $i = 17$) is. This probability can be written as $P(pick\;17 | 17 = min)P(17 = min)$. If $17$ is not minimal $P(17\;chosen | 17 \neq min) = 0$. We can see that this choice is no longer independent of the other coins since $min$ is a function of all of the coins.
If we now consider what is happening over all the trials we see that between each trail, the in the min case is evaluating the sample mean for a coin that is distributed quite differently than the source coins which the samples are drawn from. It's essentially drawing from a coin with mean $0$. What makes this problem difficult is that the random case and the minimum case look almost the same. When you consider the sequence of indices that are chosen across trials, the first coin case produces a constant sequence of $1$s. The random case is, of course, random. The min case is also random (since there is no apriori condition that would force any one coin to be minimal, it's equally likely that any would be.). 
At a glance it would seem like the random case and the min case should be similar, but the noted correlation by selection in the linchpin that causes the proof to break down. Sorry for the length, All comments welcome.
