Hence, by the triangle inequality for d ,

 dz(h; f )+d - ^erz(1) (f ); ^erz(2) (f )   d - ^erz(1)(h); ^erz (1)(f )  2 (59) + d - ^erz(2) (h); ^erz(2)(f )  + d - ^erz (1)(f ); ^erz(2)(f )   d - ^erz (1)(h); ^erz(2)(h)  :

But 2 dz(h; f )  =4 by construction and d
-

^erz(1)(h); ^erz (2)(h)

> =2 by assumption, so
(59) implies d

-

^erz(1)(f ); ^erz (2)(f )

> =4. Thus,

$$\left\{\sigma\in\Gamma_{\left(2m,n\right)}:\,\exists\mathbf{h}\in\mathcal{H}\colon d_{\nu}\,\left[\hat{\mathrm{er}}_{\mathbf{z}_{\sigma}\left(1\right)}(\mathbf{h}),\hat{\mathrm{er}}_{\mathbf{z}_{\sigma}\left(2\right)}(\mathbf{h})\right]>\frac{\alpha}{2}\right\}$$ $$\subseteq\left\{\sigma\in\Gamma_{\left(2m,n\right)}\colon\,\exists\mathbf{f}\in\hat{\mathcal{H}}\colon d_{\nu}\,\left[\hat{\mathrm{er}}_{\mathbf{z}_{\sigma}\left(1\right)}(\mathbf{f}),\hat{\mathrm{er}}_{\mathbf{z}_{\sigma}\left(2\right)}(\mathbf{f})\right]>\frac{\alpha}{4}\right\},$$

which gives (58).

Now we bound the probability of each term in the right hand side of (58).

Lemma 22. Let f : (X - Y )
n ! [0; 1℄ *be any function that can be written in the form* f =
f1      fn*. For any* z 2 (X - Y )
(2m;n)
,

$$\operatorname*{Pr}\left\{\sigma\in\Gamma_{\{2m,n\}}\colon d_{\nu}\left[\mathrm{er}_{\mathbf{z}_{\nu}\,(1)}(\mathbf{f}),\mathrm{er}_{\mathbf{z}_{\nu}\,(2)}(\mathbf{f})\right]>{\frac{\alpha}{4}}\right\}\leq2\exp\left({\frac{-\alpha^{2}\nu m n}{8}}\right),$$

$$(60)$$
$$(61)$$
; (60)
where each  2 (2m;n) is chosen uniformly at random. Proof. For any  2 (2m;n) ,

$$d_{\nu}\left[\widehat{\mathrm{r}}_{\mathbf{z}_{\sigma}\,(1)}(\mathbf{f}),\widehat{\mathrm{e}}\widehat{\mathrm{r}}_{\mathbf{z}_{\sigma}\,(2)}(\mathbf{f})\right]=\frac{\left|\sum_{i=1}^{m}\sum_{j=1}^{n}\left[f_{j}\big{(}z_{\sigma\,(i,j)}\big{)}-f_{j}\big{(}z_{\sigma\,(m+i,j)}\big{)}\right]\right|}{\nu m\,n+\sum_{i=1}^{2\,m}\sum_{j=1}^{n}f_{j}\big{(}z_{i,j}\big{)}}.$$  The transition element $\mathbf{f}_{\nu}$ is $\mathbf{0}$. For each point $i$, the joint vector $\mathbf{f}_{\nu}$ is $\mathbf{0}$.  

: (61)
To simplify the notation denote fj (zij ) by ij . For each pair ij, 1  i  m, 1  j  n, let Yij be an independent random variable such that Yij = ij  m+i;j with probability 1=2 and Yij = m+i;j  ij with probability 1=2. From (61),

Pr n  2 (2m;n) : d - ^erz(1)(f ); ^erz(2)(f )  >  4 o = Pr 8 < :  2 (2m;n) :       Xm j=1 - fj (z(i;j))  fj (z(m+i;j))        >  4 0 j=1 ij 1 A 9 = i=1 Xn mn +X 2m i=1 Xn ; = Pr 8 < :       Xm j=1 Yij        4 0 A 9 = j=1 ij 1 mn +X 2m i=1 Xn i=1 Xn ;

For zero-mean independent random variables Y1; : : : ; Yk with bounded ranges ai  Yi  bi, Hoeffding's inequality (Devroye, Gy¨orfi, & Lugosi, 1996) is

$$\mathrm{Pr}\left\{\left|\sum_{i\,=\,1}^{k}Y_{i}\right|\geq\eta\right\}\leq\,2\exp\left(-\frac{2\eta^{2}}{\sum_{i\,=\,1}^{k}(b_{i}\,-\,a_{i}\,)^{2}}\right).$$

183