Now, if we choose P uniformly at random from fP+; Pg and generate an (n; m)-sample z according to P, Lemma 30 shows that

$$\Pr\{(\mathbf{P},\mathbf{z})\colon\,\operatorname{er}_{\mathbf{P}}\left({\mathcal{A}}_{n}(\mathbf{z})\right)\geq\operatorname{opt}_{\mathbf{P}}\left({\frac{\pi}{2}}^{n}\,\right)+\varepsilon\}>{\frac{1}{4}}\left[1-{\sqrt{1-e^{\frac{\pi\,m\,\varepsilon^{2}}{1-\varepsilon^{2}}}}}\right],$$

;

which is at least Æ if

$$m<\frac{1-\varepsilon^{2}}{\varepsilon^{2}}\frac{1}{n}\log\frac{1}{8\delta(1-2\delta)}\tag{85}$$

provided 0 < Æ < 1=4. Combining the two constraints on m: (84) (with k = 7) and (85), and using

```
maxfx1; x2g  1
             2
              
               (x1 + x2) finishes the proof.

```

## Appendix D. Measurability

In order for Theorems 2 and 18 to hold in full generality we had to impose a constraint called "permissibility" on the hypothesis space family H . Permissibility was introduced by Pollard (1984)
for ordinary hypothesis classes H. His definition is very similar to Dudley's "image admissible Suslin" (Dudley, 1984). We will be extending this definition to cover hypothesis space families.

Throughout this section we assume all functions h map from (the complete separable metric space) Z into [0; 1℄. Let B(T ) denote the Borel -algebra of any topological space T . As in Section 2.2, we view P, the set of all probability measures on Z, as a topological space by equipping it with the topology of weak convergence. B(P) is then the -algebra generated by this topology. The following two definitions are taken (with minor modifications) from Pollard (1984).

Definition 8. *A set* H of [0; 1℄*-valued functions on* Z is indexed by the set T *if there exists a function* f : Z - T ! [0; 1℄ *such that* H = ff (  ; t) : t 2 T g :

Definition 9. *The set* H is permissible if it can be indexed by a set T such that 1. T is an analytic subset of a Polish7space T , and

2. the function f : Z - T ! [0; 1℄ indexing H by T *is measurable with respect to the product*
*-algebra* B(Z)  B(T ).
An analytic subset T of a Polish space T is simply the continuous image of a Borel subset X
of another Polish space X. The analytic subsets of a Polish space include the Borel sets. They are important because projections of analytic sets are analytic, and can be measured in a complete measure space whereas projections of Borel sets are not necessarily Borel, and hence cannot be measured with a Borel measure. For more details see Dudley (1989), section 13.2.

Lemma 31. H1      Hn : (X - Y )
n ! [0; 1℄ *is permissible if* H1; : : : ; Hn *are all permissible.*
Proof. Omitted.

We now define permissibility of hypothesis space families.

7. A topological space is called *Polish* if it is metrizable such that it is a complete separable metric space.