guarantees that $M\leq d$ always. Consequently, there is $0\leq i \leq d$ such that $$\Pr[M=i] \geq \frac{1}{d+1}.$$ Note that we can identify, with high probability, an $i$ such that $\Pr[M=i] \geq 1/2d$ by running ${\mathcal{A}}$ on $O(d)$ samples from ${\mathcal{D}}^n$. We next describe how to handle each of the $d+1$ possibilities for $i$. Let us first assume that $i=d$, namely that $$\Pr[M=d] \geq \frac{1}{2d}.$$ We claim that in this case we are done: indeed, after making $d$ mistakes it must be the case that ${\mathcal{A}}$ has completely identified the target concept $c$ (or else ${\mathcal{A}}$ could be presented with another example which forces it to make $d+1$ mistakes). Thus, in this case it holds with probability at least $1/2d$ that ${\mathcal{A}}(S)=c$ and we are done. Let us next assume that $i=d-1$, namely that $$\Pr[M=d-1] \geq \frac{1}{2d}.$$ The issue with applying the previous argument here is that before making the $d$’th mistake, ${\mathcal{A}}$ can output many different hypotheses (depending on the input sample $S$). We use the following idea: draw two samples $S_1,S_2 \sim {\mathcal{D}}^n$ independently, and set $f_1 = {\mathcal{A}}(S_1)$ and $f_2={\mathcal{A}}(S_2)$. Condition on the event that the number of mistakes made by ${\mathcal{A}}$ on each of $S_1,S_2$ is exactly 