$P[X\geq m/2]\geq\frac{1}{m+1}$ if $\mathbb{E}[X]=\frac{m}{2}$ 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?
 A: 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$.
A: 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.
A: 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}$.
