# Chernoff bound when we only have a lower bound of expecation

This question: Chernoff bound when we only have upper bound of expectation is similar, but for an upper bound of expectation.

The standard Chernoff bound says that is $X$ is a sum of 0/1 random variables, then, for any $\delta \in (0,1)$,

$P(X \leq (1-\delta) E(X)) \leq e^{-\frac{\delta^2 E(X)}{2}}$.

Suppose we only have $\alpha \leq E(X)$. Is it true, and if so, how to prove, that

for any $\delta \in (0,1)$,

$P(X \leq (1- \delta) \alpha) \leq e^{-\frac{\delta^2 \alpha}{2}}$.

You can use a coupling. Let $X = X_1,\ldots,X_n$, and suppose that $\Pr[X_i=1] = \beta_i$ (so $\beta := \mathbb{E}[X] = \sum_i \beta_i \geq \alpha$). Let $p = \alpha/\beta$, and define $\alpha_i = p\beta_i$. Let $Z_i \sim \mathrm{Bernoulli}(p)$, and define $Y_i = X_i Z_i$. Notice that $X_i \geq Y_i$ and that $\Pr[Y_i=1] = p\beta_i = \alpha_i$. If we define $Y := Y_1 + \cdots + Y_n$ then $X \geq Y$ and $\mathbb{E}[Y] = \sum_i \alpha_i = \alpha$, and so Chernoff's bound apply to $Y$, showing that $\Pr[Y \leq (1-\delta)\alpha] \leq e^{-\delta^2\alpha/2}$. Since $Y \leq X$, we conclude that $$\Pr[X \leq (1-\delta)\alpha] \leq \Pr[Y \leq (1-\delta)\alpha] \leq e^{-\delta^2\alpha/2}.$$