For context, consider a sum $X$ of $n$ independent random variables in $[0,1]$. For this situation, some Chernoff bounds bound the probability of a deviation with additive error, while others consider multiplicative error. E.g., letting $\mu = E[X]$, one standard Chernoff bound bounds the probability of a deviation proportional to the number of variables $n$:

$$\Pr[X \ge \mu + \epsilon n] ~\le~ \exp(-\Omega(\epsilon^2 n)).~~~~(1)$$

Another gives a bound on the probability of a deviation proportional to the expectation $\mu$:

$$\Pr[X \ge \mu + \epsilon \mu] ~\le~ \exp(-\Omega(\epsilon^2 \mu)).~~~~(2)$$

The latter variant is independent of $n$, and stronger when $\mu \ll n$.

Now, McDiarmid's inequality (which generalizes Chernoff to the case when $X=f(x_1,x_2,\ldots,x_n)$ for a function $f$ other than the sum) gives the weaker bound, (1).

Is there a variant of McDiarmid's inequality that gives the stronger bound, (2)? (Assuming that $X=f(x_1,..,x_n)$ is always non-negative, and changes by at most 1 when any $x_i$ is changed.)

In case the answer to that is no, here is the specific application I have in mind. Does the bound (2) hold for this application?

Fix $m$ arbitrary values $x_1, x_2, ..., x_m$ in $[0,1]$, and an integer $n$. Obtain $n$-set $S$ by drawing $n$ times randomly without replacement from $\{1,2,..,m\}$. Define r.v. $X = \sum_{i \in S} x_i$.

Following the hint here, we can use McDiarmid's inequality to give the bound

$$\Pr[X \ge \mu + \epsilon n] ~\le~ \exp(-\Theta(\epsilon^2 n)),$$

where $\mu = E[X]$.

In this case, does it also hold that, say,

$$\Pr[X \ge \mu + \epsilon\mu] ~\le~ \exp(- \Theta(\epsilon^2 \mu))?$$

It seems plausible that, at least in this specific case, one might be able to prove this using a carefully designed super-martingale.

A related but different question was asked here.