Let \(T\) be a complete mistake tree for \(\mathcal{H}\) of depth \(d\). The adversary plays \(T\) as follows.

The adversary maintains a pointer to a node of \(T\), starting at the root. At round \(t\), the adversary presents the instance \(x_{v_t}\) labeling the current node \(v_t\). The learner predicts \(\hat{y}_t\). The adversary then sets \(y_t = 1 - \hat{y}_t\) (the opposite of the learner’s prediction) and descends to the child of \(v_t\) corresponding to label \(y_t\).

This strategy has two properties:

1. Every round is a mistake. By construction, \(y_t = 1 - \hat{y}_t \neq \hat{y}_t\).

2. Realizability is maintained. After \(d\) rounds, the adversary has descended from the root to a leaf of \(T\), tracing a path \((v_1, y_1), (v_2, y_2), \ldots , (v_d, y_d)\). By the definition of a mistake tree, there exists \(h^* \in \mathcal{H}\) consistent with all labels along this path: \(h^*(x_{v_i}) = y_i\) for all \(i \in \{ 1, \ldots , d\} \). For any subsequent rounds \(t {\gt} d\), the adversary can label consistently with this \(h^*\).

The adversary forces exactly \(d\) mistakes in the first \(d\) rounds, so \(A\) makes at least \(d\) mistakes.

For randomized learners, the argument extends by the minimax theorem (or directly): for any distribution over predictions \(\hat{y}_t\), the adversary’s strategy of playing the opposite forces an expected mistake at every round. Alternatively, one can apply Yao’s minimax principle: the worst-case deterministic adversary against the best randomized learner equals the best deterministic learner against the worst-case adversary, and we have shown the latter is at least \(d\).