# a simple argument?

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.

-
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

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.

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

-

looks like chebyshev inequality.

-
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