Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$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?

share|cite|improve this question
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
up vote 0 down vote accepted

The orignal problem is a lemma to prove

\begin{equation} \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] \end{equation}

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^*$

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

We have relationship

\begin{equation} \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} \end{equation}

Taking expectation on both sides,

\begin{equation} \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} \end{equation}

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

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

Now we conclude that

\begin{equation} \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] \end{equation}

share|cite|improve this answer

$$|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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.