# 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)$$
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