Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

This argument appeared in a proof in a paper (I am paraphrasing), and I am not sure why it is true. It should be rather simple.

Let $(\Omega,P)$ be some sample space. Let $X$ be a random variable between $0$ and $1$. Let $U \subseteq \Omega$ and let

$U^\prime = ${$ \omega \colon X(\omega) \ge E[X \mid U] - 1/m$}.

Then $P(U^\prime) \ge P(U)/m$.

Can't see exactly why this is true.

share|cite|improve this question
It is true with $U = \omega$ and $m=1$. In that case, $U^\prime = U$ (because all $X(w)$ are greater than something negative.) and we get $P(U^\prime) = P(U) \ge P(U)$. – normvector Dec 2 '10 at 20:16
I do know that the fact that $X$ is smaller than $1$ is important, because the way the authors explain it is by arguing that the argument is true because $X is smaller than 1$. – normvector Dec 2 '10 at 20:17
Note that my answer given below shows exactly where we use the fact that $X \leq 1$. – Shai Covo Dec 7 '10 at 16:38
up vote 2 down vote accepted

We can assume that $U = \Omega$. So you want to show $$\Pr[X \geq E[X] - \alpha] \geq \alpha,$$ where $\alpha = 1/m$. If not, then $$E[X] < \alpha + (1-\alpha)(E[X] - \alpha) = (1-\alpha) E[X] + \alpha^2,$$ so that $\alpha E[X] < \alpha^2$ and $E[X] < \alpha$. But in that case, the inequality trivially holds.

EDIT: Some more details. Suppose that $\Pr[X > E[X] - \alpha] = p < \alpha$. Given $p$, the distribution maximizing $E[X]$ under this constraint is $$\Pr[X=E[X]-\alpha]=1-p,\quad \Pr[X=1]=p.$$ Its expectation is $$p + (1-p)(E[X] - \alpha)= E[X] - \alpha + p(1 - E[X] + \alpha).$$ Since $p < \alpha$ and $1 - E[X] + \alpha > 0$, we get that $$E[X] < E[X] - \alpha + \alpha(1 - E[X] + \alpha).$$ Rearranging, $$\alpha (1 + E[X]) < \alpha (1 + \alpha)$$ and so $E[X] < \alpha$, in which case the inequality trivially holds.

share|cite|improve this answer
But if we assume that $P(X \ge E[X]-\alpha) < \alpha$, then we can't assume that $P(X < E[X]-\alpha) < 1-\alpha$. It is larger or equal to $1-\alpha$, and then we cannot have the inequality starting at $E[X] < \alpha + ...$. – normvector Dec 2 '10 at 20:29
If $\Pr[X \geq c] = p$, then the maximal $E[X]$ is obtained by the random variable which is $1$ w.p. $p$ and $c$ w.p. $1-p$. – Yuval Filmus Dec 3 '10 at 4:52
This maximum is monotone in $p$, hence the inequality. – Yuval Filmus Dec 3 '10 at 5:02
this seems correct, I couldn't find a mistake. I still find it rather surprising you did not use the fact that $X \le 1$, because that was something the authors mentioned should be used -- in fact, that's the only point they made about the validity of this inequality. Any ideas? – normvector Dec 3 '10 at 13:48
never mind, you used it for $1 - E[X] + \alpha > 0$. – normvector Dec 3 '10 at 14:17

We want to show that $$ {\rm P}[X \ge {\rm E}(X|U) - 1/m] \ge {\rm P}(U)/m. $$ This is trivially not true if $0 < m < 1$, for if $U = \Omega$, the right-hand side is greater than $1$. So, assume that $m \geq 1$, and ${\rm P}(U)>0$. Further, if ${\rm E}(X|U) - 1/m \leq 0$, then the inequality is trivial; hence we assume that ${\rm E}(X|U) - 1/m > 0$. Let $P_{X|U}$ denote the conditional distribution of $X$ given $U$, so that $$ P_{X|U} {(A)} = {\rm P}(X \in A | U) = \frac{{{\rm P}([X \in A],U)}}{{{\rm P}(U)}}. $$ Then, $$ {\rm E}(X|U) = \int_{[0,1]} {xP_{X|U} ({\rm d}x)}. $$ Next, decompose $[0,1]$ into the union of the intervals $I_1 = \lbrace 0 \leq x < {\rm E}(X|U) - 1/m \rbrace$ and $I_2 = \lbrace {\rm E}(X|U) - 1/m \leq x \leq 1 \rbrace$. On the one hand, $$ \int_{I_1 } {xP_{X|U} ({\rm d}x)} \le [{\rm E}(X|U) - 1/m]P_{X|U} (I_1 ) \le {\rm E}(X|U) - 1/m, $$ and on the other hand, $$ \int_{I_2 } {xP_{X|U} ({\rm d}x)} \leq \int_{I_2 } {P_{X|U} ({\rm d}x)} = P_{X|U} {(I_2)} \leq \frac{{{\rm P}(X \in I_2 )}}{{{\rm P}(U)}}. $$ Combining it all, we get $$ {\rm E}(X|U) \leq {\rm E}(X|U) - 1/m + {\rm P}(X \in I_2)/{\rm P}(U). $$ That is ${\rm P}(X \in I_2) \geq {\rm P}(U)/m$, which is exactly what we want.

share|cite|improve this answer

looks like chebyshev inequality.

share|cite|improve this answer
We want: $\Pr[|X-E[X]| \leq 1/m] \geq 1/m$. We know that $V[X] \leq 1/4$ (Bernoulli $1/2$). So Chebyshev gives that the probability is at least $1 - m^2/4$. So the argument works as long as $1 - m^2/4 \geq 1/m$ which, as it happens, is never the case. – Yuval Filmus Dec 3 '10 at 5:28
so my argument is not applicable? – Ross James Dec 3 '10 at 5:34
You haven't presented an argument. I was sketching the simplistic application of Chebyshev, which doesn't seem to work. – Yuval Filmus Dec 3 '10 at 6:48

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.