If $X$ is a sum of i.i.d. random variables taking values in $\{0,1\}$ and $E[X]=\mu$, the Chernoff bound tells us that
$$\Pr(X\geq (1+\delta)\mu)\leq e^{-\frac{\delta^2\mu}{3}}$$
for all $0<\delta<1$.
If $E[X]\leq\mu$ instead, does there exist a constant $c$ such that
$$\Pr(X\geq (1+\delta)\mu)\leq e^{-c\delta^2\mu}$$
for all $0<\delta<1$?
(This question is related, but the answer there doesn't help.)
Yes, we can get a bound like this. To see why, we will need to look a little more closely at how Chernoff bounds are proved. A relatively standard form of this kind of tail bound would assume that $$ X = X_1 + \cdots + X_n $$ with all $X_i$ independent, discrete, supported in $[-1,1]$, with mean $\mu_i = 0$, variance $\sigma_i^2$. The resulting tail bound ends up being that: $$\operatorname{Pr}[X > \lambda\sigma]\le e^{-\lambda^2/4}$$ where $\sigma^2 = \sum_{i\in [n]} \sigma^2_i$ is the variance of $X$ and $\lambda\in[0,2\sigma]$. (Here is a proof by Van Vu.)
I'm more or less going to first reproduce the proof, so you can get an idea of why decreasing the expectation turns out to be ok.
All Chernoff bounds are based on applying Markov's inequality to $e^{tX}$ to get that $\operatorname{Pr}[X > \lambda\sigma]\le \mathbb{E}[e^{tX}]e^{-t\lambda\sigma}$. So the general method is to work out $\mathbb{E}[e^{tX}]$ and then optimize $t$. We can do the MGF computation a little differently from the link, namely as $$\mathbb{E}[e^{tX}] = \prod_{i\in [n]}\mathbb{E}[e^{tX_i}] \le \prod_{i\in [n]}\mathbb{E}[(1 + tX_i + t^2X_i^2)]$$ where we first used independence of the $X_i$ and then $e^x\le 1 + x + x^2$ for $x\in [0,1]$. Under the hypotheses we started with and linearity of expectation, $$\mathbb{E}[(1 + tX_i + t^2X_i^2)] = 1 + t^2\sigma_i^2\le e^{t^2\sigma_i^2}$$ so we get that $$ \operatorname{Pr}[X > \lambda\sigma] \le e^{t^2\sigma^2 - t\lambda\sigma}$$ With $t = \lambda/2\sigma$ this is what we wanted (and since $t\in[0,1]$, all the inequalities we used are valid).
Now let's assume that $\mu_i\le 0$ (instead of $= 0$ as before) and otherwise the same set of hypotheses. Returning to the MGF computation, we get $$ \mathbb{E}[(1 + tX_i + t^2X_i^2)] = 1 + t\mu_i + t^2\mathbb{E}[X_i^2] = 1 + t\mu_i + t^2\sigma_i^2 + t^2\mu_i^2 $$ Using that $x^2 + x < 0$ for $x\in (-1,0)$, this implies that $$ \mathbb{E}[(1 + tX_i + t^2X_i^2)] \le 1 + t^2\sigma_i^2 $$ and so we get the same tail bound as before.
Finally, note you always have $\sigma^2_i\le 4$, so $\sigma^2\le 4n$.
You can obtain this statement from your given form of Chernoff's bound using a coupling.
Write $\mu - \mathbf{E}[X] = i + f$ where $i$ is a nonnegative integer and $ 0 \le f \le 1$. Now define the random variable $$Y = X + \underbrace{1 + \dots + 1}_{\text{$i$ times}} + Z$$ where $Z \sim \text{Ber}(f)$ is an independent biased coin flip. Then $Y$ is also a sum of independent indicator random variables with $\mathbf{E}[Y] = \mu$, and we know $X \le Y$ always. Then applying Chernoff's bound to $Y$ gives the desired statement.
