I'm reading the book "The Probabilistic Method" (for discrete mathematics) by Alon and Spencer, and I'm having trouble deciphering the following implication from the proof of Theorem 1.5.1.
Link to the key part of the proof.
Here, I will try to provide what I think is the minimal amount of detail required. If more details is needed, I apologize, but please ask me!
Let $Y$ be a discrete random variable taking on values $0,1,\dots,m$ such that its expectation satisfies the lower bound:
$$ \mathbb{E}(Y)\geq 2\cdot m^{1-t\delta^2/2} $$
I would like to conclude, using the fact that $Y\leq m$, that:
$$ \mathbb{P}(Y\geq m^{1-t\delta^2/2})\geq m^{-t\delta^2/2} $$
I have spent a long time staring at it, and cannot seem to find why this is true. I have a feeling that I'm missing something very small.
Thank you!
Best Answer
The result follows directly from the reverse Markov inequality. Reverse Markov Inequality states that for a random variable $Y$ that is upper bounded by $m$, we have that $\Pr(Y \leq a) \leq \dfrac{\mathbb{E}[m - Y]}{m - a}$. (It is essentially the Markov inequality applied to $m - Y$).Applying the above inequality for $a = m^{1 - t\delta^2/2}$, we get $\displaystyle \Pr(Y \leq m^{1 - t\delta^2/2}) \leq \dfrac{m - \mathbb{E}[Y]}{m - m^{1 - t\delta^2/2}} $. Therefore, we have, \begin{align*} \Pr(Y \geq m^{1 - t\delta^2/2}) &\geq 1 - \dfrac{m - \mathbb{E}[Y]}{m - m^{1 - t\delta^2/2}} \\ &\geq \dfrac{\mathbb{E}[Y] - m^{1 - t\delta^2/2}}{m - m^{1 - t\delta^2/2}}\\ &\geq m^{-t\delta^2/2} \end{align*}