Uniform convergence in probability

Lemma: Let ${\displaystyle V=\{x\in X^{m}:|Q_{P}(h)-{\widehat {Q}}_{x}(h)|\geq \varepsilon {\text{ for some }}h\in H\}}$ and

${\displaystyle R=\{(r,s)\in X^{m}\times X^{m}:|{\widehat {Q_{r}}}(h)-{\widehat {Q}}_{s}(h)|\geq \varepsilon /2{\text{ for some }}h\in H\}.}$

Then for ${\displaystyle m\geq {\frac {2}{\varepsilon ^{2}}}}$, ${\displaystyle P^{m}(V)\leq 2P^{2m}(R)}$.

Proof: By the triangle inequality,
if ${\displaystyle |Q_{P}(h)-{\widehat {Q}}_{r}(h)|\geq \varepsilon }$ and ${\displaystyle |Q_{P}(h)-{\widehat {Q}}_{s}(h)|\leq \varepsilon /2}$ then ${\displaystyle |{\widehat {Q}}_{r}(h)-{\widehat {Q}}_{s}(h)|\geq \varepsilon /2}$.

Therefore,

${\displaystyle {\begin{aligned}&P^{2m}(R)\\[5pt]\geq {}&P^{2m}\{\exists h\in H,|Q_{P}(h)-{\widehat {Q}}_{r}(h)|\geq \varepsilon {\text{ and }}|Q_{P}(h)-{\widehat {Q}}_{s}(h)|\leq \varepsilon /2\}\\[5pt]={}&\int _{V}P^{m}\{s:\exists h\in H,|Q_{P}(h)-{\widehat {Q}}_{r}(h)|\geq \varepsilon {\text{ and }}|Q_{P}(h)-{\widehat {Q}}_{s}(h)|\leq \varepsilon /2\}\,dP^{m}(r)\\[5pt]={}&A\end{aligned}}}$

since ${\displaystyle r}$ and ${\displaystyle s}$ are independent.

Now for ${\displaystyle r\in V}$ fix an ${\displaystyle h\in H}$ such that ${\displaystyle |Q_{P}(h)-{\widehat {Q}}_{r}(h)|\geq \varepsilon }$. For this ${\displaystyle h}$, we shall show that

${\displaystyle P^{m}\left\{|Q_{P}(h)-{\widehat {Q}}_{s}(h)|\leq {\frac {\varepsilon }{2}}\right\}\geq {\frac {1}{2}}.}$

Thus for any ${\displaystyle r\in V}$, ${\displaystyle A\geq {\frac {P^{m}(V)}{2}}}$ and hence ${\displaystyle P^{2m}(R)\geq {\frac {P^{m}(V)}{2}}}$. And hence we perform the first step of our high level idea.

Notice, ${\displaystyle m\cdot {\widehat {Q}}_{s}(h)}$ is a binomial random variable with expectation ${\displaystyle m\cdot Q_{P}(h)}$ and variance ${\displaystyle m\cdot Q_{P}(h)(1-Q_{P}(h))}$. By Chebyshev's inequality we get

${\displaystyle P^{m}\left\{|Q_{P}(h)-{\widehat {Q_{s}(h)}}|>{\frac {\varepsilon }{2}}\right\}\leq {\frac {m\cdot Q_{P}(h)(1-Q_{P}(h))}{(\varepsilon m/2)^{2}}}\leq {\frac {1}{\varepsilon ^{2}m}}\leq {\frac {1}{2}}}$

for the mentioned bound on ${\displaystyle m}$. Here we use the fact that ${\displaystyle x(1-x)\leq 1/4}$ for ${\displaystyle x}$.

Let ${\displaystyle \Gamma _{m}}$ be the set of all permutations of ${\displaystyle \{1,2,3,\dots ,2m\}}$ that swaps ${\displaystyle i}$ and ${\displaystyle m+i}$ ${\displaystyle \forall i}$ in some subset of ${\displaystyle \{1,2,3,\ldots ,2m\}}$.

Lemma: Let ${\displaystyle R}$ be any subset of ${\displaystyle X^{2m}}$ and ${\displaystyle P}$ any probability distribution on ${\displaystyle X}$. Then,

${\displaystyle P^{2m}(R)=E[\Pr[\sigma (x)\in R]]\leq \max _{x\in X^{2m}}(\Pr[\sigma (x)\in R]),}$

where the expectation is over ${\displaystyle x}$ chosen according to ${\displaystyle P^{2m}}$, and the probability is over ${\displaystyle \sigma }$ chosen uniformly from ${\displaystyle \Gamma _{m}}$.

Proof: For any ${\displaystyle \sigma \in \Gamma _{m},}$

${\displaystyle P^{2m}(R)=P^{2m}\{x:\sigma (x)\in R\}}$

(since coordinate permutations preserve the product distribution ${\displaystyle P^{2m}}$.)

${\displaystyle {\begin{aligned}\therefore P^{2m}(R)={}&\int _{X^{2m}}1_{R}(x)\,dP^{2m}(x)\\[5pt]={}&{\frac {1}{|\Gamma _{m}|}}\sum _{\sigma \in \Gamma _{m}}\int _{X^{2m}}1_{R}(\sigma (x))\,dP^{2m}(x)\\[5pt]={}&\int _{X^{2m}}{\frac {1}{|\Gamma _{m}|}}\sum _{\sigma \in \Gamma _{m}}1_{R}(\sigma (x))\,dP^{2m}(x)\\[5pt]&{\text{(because }}|\Gamma _{m}|{\text{ is finite)}}\\[5pt]={}&\int _{X^{2m}}\Pr[\sigma (x)\in R]\,dP^{2m}(x)\quad {\text{(the expectation)}}\\[5pt]\leq {}&\max _{x\in X^{2m}}(\Pr[\sigma (x)\in R]).\end{aligned}}}$

The maximum is guaranteed to exist since there is only a finite set of values that probability under a random permutation can take.

Lemma: Basing on the previous lemma,

${\displaystyle \max _{x\in X^{2m}}(\Pr[\sigma (x)\in R])\leq 4\Pi _{H}(2m)e^{-\varepsilon ^{2}m/8}}$.

Proof: Let us define ${\displaystyle x=(x_{1},x_{2},\ldots ,x_{2m})}$ and ${\displaystyle t=|H|_{x}|}$ which is at most ${\displaystyle \Pi _{H}(2m)}$. This means there are functions ${\displaystyle h_{1},h_{2},\ldots ,h_{t}\in H}$ such that for any ${\displaystyle h\in H,\exists i}$ between ${\displaystyle 1}$ and ${\displaystyle t}$ with ${\displaystyle h_{i}(x_{k})=h(x_{k})}$ for ${\displaystyle 1\leq k\leq 2m.}$

We see that ${\displaystyle \sigma (x)\in R}$ iff for some ${\displaystyle h}$ in ${\displaystyle H}$ satisfies, ${\displaystyle |{\frac {1}{m}}|\{1\leq i\leq m:h(x_{\sigma _{i}})=1\}|-{\frac {1}{m}}|\{m+1\leq i\leq 2m:h(x_{\sigma _{i}})=1\}||\geq {\frac {\varepsilon }{2}}}$. Hence if we define ${\displaystyle w_{i}^{j}=1}$ if ${\displaystyle h_{j}(x_{i})=1}$ and ${\displaystyle w_{i}^{j}=0}$ otherwise.

For ${\displaystyle 1\leq i\leq m}$ and ${\displaystyle 1\leq j\leq t}$, we have that ${\displaystyle \sigma (x)\in R}$ iff for some ${\displaystyle j}$ in ${\displaystyle {1,\ldots ,t}}$ satisfies ${\displaystyle |{\frac {1}{m}}\left(\sum _{i}w_{\sigma (i)}^{j}-\sum _{i}w_{\sigma (m+i)}^{j}\right)|\geq {\frac {\varepsilon }{2}}}$. By union bound we get

${\displaystyle \Pr[\sigma (x)\in R]\leq t\cdot \max \left(\Pr[|{\frac {1}{m}}\left(\sum _{i}w_{\sigma _{i}}^{j}-\sum _{i}w_{\sigma _{m+i}}^{j}\right)|\geq {\frac {\varepsilon }{2}}]\right)}$

${\displaystyle \leq \Pi _{H}(2m)\cdot \max \left(\Pr \left[\left|{\frac {1}{m}}\left(\sum _{i}w_{\sigma _{i}}^{j}-\sum _{i}w_{\sigma _{m+i}}^{j}\right)\right|\geq {\frac {\varepsilon }{2}}\right]\right).}$

Since, the distribution over the permutations ${\displaystyle \sigma }$ is uniform for each ${\displaystyle i}$, so ${\displaystyle w_{\sigma _{i}}^{j}-w_{\sigma _{m+i}}^{j}}$ equals ${\displaystyle \pm |w_{i}^{j}-w_{m+i}^{j}|}$, with equal probability.

Thus,

${\displaystyle \Pr \left[\left|{\frac {1}{m}}\left(\sum _{i}\left(w_{\sigma _{i}}^{j}-w_{\sigma _{m+i}}^{j}\right)\right)\right|\geq {\frac {\varepsilon }{2}}\right]=\Pr \left[\left|{\frac {1}{m}}\left(\sum _{i}|w_{i}^{j}-w_{m+i}^{j}|\beta _{i}\right)\right|\geq {\frac {\varepsilon }{2}}\right],}$

where the probability on the right is over ${\displaystyle \beta _{i}}$ and both the possibilities are equally likely. By Hoeffding's inequality, this is at most ${\displaystyle 2e^{-m\varepsilon ^{2}/8}}$.

Finally, combining all the three parts of the proof we get the Uniform Convergence Theorem.