$P[X\geq m/2]\geq\frac{1}{m+1}$ if $\mathbb{E}[X]=\frac{m}{2}$

Question

Let $m\gt 0$ and let $X$ be a random variable on the set $\{0,\dots,m\}$.

Assuming that $\mathbb{E}[X]=\frac{m}{2}$, prove that:

$$P[X\geq m/2]\geq\frac{1}{m+1}$$

I tried induction but it didn't work, know I am trying to prove it by contradiction, someone got a hint?

Answer 1

If $P(X \ge m/2) < \frac{1}{m+1}$, then \begin{align} E[X] &= \sum_{k < m/2} k P(X=k) + \sum_{k \ge m/2} kP(X=k) \\ &\le \left(\left\lceil\frac{m}{2}\right\rceil - 1\right) P(X < m/2) + m P(X \ge m/2) \\ &= \left(\left\lceil\frac{m}{2}\right\rceil - 1\right)(1-P(X \ge m/2)) + mP(X \ge m/2) \\ &= \left(\left\lceil\frac{m}{2}\right\rceil - 1\right) + \left(m+1 - \left\lceil\frac{m}{2}\right\rceil\right) P(X \ge m/2) \\ &{\color{blue}<} \left(\left\lceil\frac{m}{2}\right\rceil - 1\right) + \left(m+1 - \left\lceil\frac{m}{2}\right\rceil\right) \frac{1}{m+1} \\ &= \left\lceil\frac{m}{2}\right\rceil \frac{m}{m+1} \\ &= \begin{cases} \frac{m}{2} \cdot \frac{m}{m+1} & \text{$m$ even} \\ \frac{m+1}{2} \cdot \frac{m}{m+1} & \text{$m$ odd} \\ \end{cases} \\ &\le \frac{m}{2}, \end{align} a contradiction.

Note that the statement is true even if $E[X]=m/2$ is replaced with $E[X] \ge m/2$.

Intuition: we want to see how small $P(X \ge m/2)$ can be while still keeping the expectation $E[X]$ large. Thus we should consider random variables that only take values $\lceil m/2 \rceil - 1$ and $m$. This is the first inequality in the work above.

Answer 2

Let $P[X=j]=p_j$ for $0\leq j\leq m$. If $m=2k+1$, then $P[X\geq m/2]=p_{k+1}+\dots+p_{2k+1}$. If $$ p_{k+1}+\dots+p_{2k+1}<\frac{1}{m+1}, $$ then $$ E[X]=p_1+2p_2+\dots+(k+1)p_{k+1}+(2k+1)p_{2k+1} $$ and $$ E[X]\leq(p_1+\dots+{p_{k+1}})k+(p_{k+1}+\dots+p_{2k+1})(2k+1) $$ from which $$ E[X]<\frac{2k+1}{2k+2}k+\frac{2k+1}{2k+2}=\frac{m}{2} $$ similarly for $m=2k$.

Answer 3

Let $m = 2k$. $\widetilde{X} = k - 1$ if $X < k$ and $\widetilde{X} = 2k$ if $X\geqslant k$. So $\widetilde{X} \geqslant X \Rightarrow \mathbb E[\widetilde{X}] \geqslant \mathbb E[X] = k$. Let $\alpha = P[X \geqslant k] \Rightarrow E[\widetilde{X}] = (k - 1)(1 - \alpha) + 2k\alpha \geqslant k \Rightarrow k \alpha + \alpha \geqslant 1 \Rightarrow \alpha \geqslant \frac{1}{k + 1} > \frac{1}{m + 1}$. Otherwise $m = 2k + 1$. $\widetilde{X} = k$ if $X < k + 1$ and $\widetilde{X} = 2k+1$ if $X\geqslant k + 1$.

So $\widetilde{X} \geqslant X \Rightarrow \mathbb E[\widetilde{X}] \geqslant \mathbb E[X] = k + \frac{1}{2}$.

Let $\alpha = P[X \geqslant k + 1] \Rightarrow E[\widetilde{X}] = k(1 - \alpha) + (2k+1)\alpha \geqslant k + \frac{1}{2} \Rightarrow k \alpha + \alpha \geqslant \frac{1}{2}$, so$ \alpha \geqslant \frac{1}{2k + 2} = \frac{1}{m + 1}$.