# How to prove the double sample trick inequality $\frac{1}{2} \Pr[|v_1-p| \geq 2 \epsilon] \leq \Pr[|v_1-v_2| \geq \epsilon]$?

$x_i$ is i.i.d random variables with mean $p$. $v_1 = \frac{1}{n}\sum_{i=1}^n{x_i}$, $v_2 = \frac{1}{n}\sum_{i=n+1}^{2n}{x_i}$.Then $\frac{1}{2} \Pr[|v_1-p| \geq 2 \epsilon] \leq \Pr[|v_1-v_2| \geq \epsilon]$ is a lemma to prove VC bound in statistical learning. However, I feel hard to prove it. Any hints?

-
Is the second $v_1$ supposed to be $v_2$? – Byron Schmuland Oct 2 '12 at 14:31
@ByronSchmuland, no. It is $v_1-v_2$. – Strin Oct 3 '12 at 15:18
You have two different equations for $v_1$. One says $v_1 = \sum_{i=1}^n{x_i}$, while the other says $v_1 = \sum_{i=n+1}^{2n}{x_i}$. It makes the statement of the problem a little confusing. – Byron Schmuland Oct 3 '12 at 15:25
@ByronSchmuland,excuse me, $v_2 = \sum_{i=n+1}^{2n}{x_i}$ – Strin Oct 4 '12 at 6:42

The orignal problem is a lemma to prove

$$\frac{1}{2} \Pr[\sup\limits_{\phi \in \Phi}{|\mu_1(\phi)-E[\phi(z)]|} \geq 2\epsilon] \leq \Pr[\sup\limits_{\phi \in \Phi}{|\mu_1(\phi)-\mu_2(\phi)|} \geq \epsilon]$$

where $\mu_1 = \frac{1}{n}\sum\limits_{i=1}^{n}{z_i}, \mu_2 = \frac{1}{n}\sum\limits_{i=n+1}^{2n}{z_i}$. And also $n \geq \frac{\ln(2)}{\epsilon^2}$.

Now we directly prove the general theorem. The prove of the lemma can be adapted from this proof in a straight-forward way.

Fix $z_1,z_2,...,z_{2n}$. Consider $\phi^*$

$$\phi^* = \arg\sup_{\phi \in \Phi}{|\mu_1-E[\phi]|}$$

We have relationship

$$\begin{array}{ll} &I[|\mu_1(\phi^*)-\mu_2(\phi^*)| \geq \epsilon|] \\ \geq & I[|\mu_1(\phi^*)-E[\phi^*]| \geq 2\epsilon] \land I[|\mu_2(\phi^*)-E[\phi^*]| \leq \epsilon]] \\ =& I[|\mu_1(\phi^*)-E[\phi^*]| \geq 2\epsilon]I[|\mu_2(\phi^*)-E[\phi^*]| \leq \epsilon]] \end{array}$$

Taking expectation on both sides,

$$\begin{array}{ll} & \Pr[\sup\limits_{\phi \in \Phi}{|\mu_1(\phi)-E[\phi(z)]|} \geq 2\epsilon] \Pr[|\mu_2(\phi^*)-E[\phi(z)]| \leq \epsilon] \\ \leq & \Pr[|\mu_1(\phi^*)-\mu_2(\phi^*)| \geq \epsilon] \\ \leq & \Pr[\sup\limits_{\phi \in \Phi}{|\mu_1-\mu_2|} \geq \epsilon] \end{array}$$

According to Chernoff Bound and the condition that $n \geq \frac{\ln(2)}{\epsilon^2}$,

$$\Pr[|\mu_2(\phi^*)-E[\phi^*(z)]| \leq \epsilon] \geq 1-2e^{-2n\epsilon^2} \geq \frac{1}{2}$$

Now we conclude that

$$\frac{1}{2} \Pr[\sup\limits_{\phi \in \Phi}{|\mu_1(\phi)-E[\phi(z)]|} \geq 2\epsilon] \leq \Pr[\sup\limits_{\phi \in \Phi}{|\mu_1(\phi)-\mu_2(\phi)|} \geq \epsilon]$$

-

$$|v_1 - p| = |(v_1 - v_2) + (v_2 - p)| \leq |v_1 - v_2| + |v_2 - p|$$ $$P(|v_1 - p| \geq 2\epsilon) \leq P(|v_1 - v_2| + |v_2 - p| \geq 2\epsilon) \leq P(|v_1 - v_2| \geq \epsilon) + P(|v_2 - p| \geq \epsilon)$$ Therefore, $$P(|v_1 - p| \geq 2\epsilon) \leq P(|v_1 - v_2| \geq \epsilon) + P(|v_2 - p| \geq \epsilon) \leq P(|v_1 - v_2| \geq \epsilon) + \frac{1}{2}P(|v_1 - p| \geq 2\epsilon)$$

Q.E.D I am leaving it to you to write in arguments that justify each step. They are not particularly hard but this is a very simple and a powerful trick in learning theory and if you plan to stick with it, you will see this occurring in different places in different forms. So, the arguments are good to realize and understand by oneself.

-
The last step $\Pr[|v_2-p| \geq \epsilon] \leq \frac{1}{2}\frac{1}{2}\Pr[|v_2-p| \geq 2\epsilon]$ may not generally hold true. Consider $n=1$ and $X$ is a random variable uniformly distributed at $-1,0,1$ each with prob. $\frac{1}{3}$. Let $\epsilon = \frac{2}{3}$. Then $\Pr[|v_2-p| \geq \epsilon] = \frac{2}{3}$ while $\frac{1}{2}\Pr[|v_2-p| \geq 2\epsilon] = 0$. – Strin Oct 4 '12 at 7:53
I already figure out the solution. It uses chernoff bound to get that $\frac{1}{2}$. – Strin Oct 4 '12 at 7:54
@Strin If you have a solution, you should post it as an answer. That will help future readers of this site. – Byron Schmuland Oct 4 '12 at 11:52
@ByronSchmuland,nice suggestion. – Strin Oct 5 '12 at 5:17