Noting that the range of each Yij is [jij  i+m;j )j; jij  i+m;j )j℄, we have

$$\Pr\left\{\left|\sum_{i=1}^{m}\sum_{j=1}^{n}Y_{ij}\right|>\frac{\alpha}{4}\left(\nu mn+\sum_{i=1}^{2m}\sum_{j=1}^{n}\beta_{ij}\right)\right\}\leq2\exp\left(-\frac{\alpha^{2}\left[\nu mn+\sum_{i=1}^{2m}\sum_{j=1}^{n}\beta_{ij}\right]^{2}}{32\sum_{i=1}^{m}\sum_{j=1}^{n}(\beta_{ij}-\beta_{i+m,j})^{2}}\right)\.$$  Let $\gamma=\sum_{i=1}^{2m}\sum_{j=1}^{n}\beta_{ij}.$ As $0\leq\beta_{ij}\leq1,$ $\sum_{i=1}^{m}\sum_{j=1}^{n}(\beta_{ij}-\beta_{m+ij})^{2}\leq\gamma.$ Hence,

$$2\exp\left(-\frac{\alpha^{2}\left[\nu m n+\sum_{i=1}^{2m}\sum_{j=1}^{n}\beta_{i j}\right]^{2}}{32\sum_{i=1}^{m}\sum_{j=1}^{n}(\beta_{i j}-\beta_{i+m,j})^{2}}\right)\leq2\exp\left(-\frac{\alpha^{2}(\nu m n+\gamma)^{2}}{32\gamma}\right).$$

(mn + 
)

2

=
 is minimized by setting  = mn giving a value of 4mn. Hence

$$\mathrm{Pr}\left\{\sigma\in\Gamma_{\{2m,n\}}:\,d_{\nu}\left[\mathrm{\acute{e}r}_{\mathbf{z}_{\sigma}\,\{1\}}\mathbf{(f)},\mathrm{\acute{e}r}_{\mathbf{z}_{\sigma}\,\{2\}}\mathbf{(f)}\right]>\frac{\alpha}{4}\right\}\leq\,2\exp\left(\frac{-\,\alpha^{2}\,\nu m\,n}{8}\right),$$  d. 

as required.

A.1.3 PUTTING IT TOGETHER
For fixed z 2 (X - Y )
(2m;n)
, Lemmas 21 and 22 give:

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

$$>\frac{\alpha}{2}\biggr\}$$ $$\leq\,2\mathcal{N}\left(\alpha\nu/8,\mathcal{H},d_{\mathbf{z}}\,)\right)\exp\left(-\frac{\alpha^{2}\,\nu\,m n}{8}\right).$$

Note that dz is simply dP where P = (P1; : : : ; Pn) and each Pi is the empirical distribution that
puts point mass $1/m$ on each $z_{ji},j=1,\ldots,2m$ (recall Definition 3). Hence,  $$\Pr\left\{\sigma\in\Gamma_{\{2m,n\}},\mathbf{z}\in(X\times Y)^{\{2m,n\}}:\sup_{\eta}d_{\nu}\left[\mathrm{\acute{e}r}_{\mathbf{z}_{\nu}}(1),\mathbf{h}\right],\mathrm{\acute{e}r}_{\mathbf{z}_{\nu}}(2)(\mathbf{h})\right]>\frac{\alpha}{2}\right\}$$ $$\leq\mathcal{C}\left(\alpha\nu/8,\,\mathcal{H}\right)\exp\left(-\frac{\alpha^{2}\nu mn}{8}\right).$$

Now, for a random choice of z, each zij in z is independently (but not identically) distributed and 
only ever swaps zij and zi+m;j (so that  swaps a zij drawn according to Pj with another component
drawn according to the same distribution). Thus we can integrate out with respect to the choice of  and write Pr  z 2 (X - Y ) (2m;n) : sup H d - ^erz(1) (h); ^erz(2) (h)  >  2   2C (=8; H) exp   2 mn  : 8 Applying Lemma 20 to this expression gives Theorem 18.

