Proving $\log (N)$ mistake bound is "tight" for a learner when learning thresholds
I am assuming the learning model described in Wikipedia. The environment will maintain a set of hypothesis forming an interval $S = [h_\alpha,h_\beta]$ consistent with its current answers, and will ensure that the first $\log N$ answers by the algorithm are wrong. In the beginning, $S = H$. At each step, the environment presents the middle point of the interval (we're identifying hypotheses with points in the domain in a natural way). Depending on the learner's answer, the interval $S$ is halved so that the learner is wrong. This process can go on for $\log N$ steps, in each of which the learner is mistaken, so that in total the learner makes at least $\log N$ mistakes.