Chernoff bound for weighted sums of Bernoulli random variables

Question

I tried to prove the following Chernoff-type bound when doing research, and found that it is of indepent interest.

Let $X_1, \dots, X_n$ be independent random varibles such that each $X_i$ is a Bernoulli random varible with parameter $p$, i.e., $\Pr[X = 1] = 1 - \Pr[X = 0] = p$. Moreover, we have weights $a_1, \dots, a_n \in [0, \tau]$, and write $S := \sum_{i = 1}^n a_iX_i$. I tried to show that
$$ \Pr[S > \mathbf{E}[S] + t] \leq \exp\left(-\frac{Ct^2}{np\tau^2}\right), \forall t > 0 $$ where $C$ is a constant.

One can surely apply Hoeffding bound here, which yields $$ \Pr[S > \mathbf{E}[S] + t] \leq \exp\left(-\frac{2t^2}{n\tau^2}\right), \forall t > 0. $$ The drawback is that Hoeffding bound only uses the range of the random variables, however, it does not exploit the property that $X_i$'s are Bernoulli variables, and hence a $p$ factor is missing.

I tried to adapt the proof of Chernoff bound, but unfortunately failed. I would apprecaite it if anyone have some idea on it.

Answer 1

Your bound (at least when $t\le E[S]$) seems to follow from the standard multiplicative Chernoff bound, as follows.

Lemma 1. (a standard multiplicative Chernoff bound) Let $S$ be the sum of independent random variables in $[0,1]$. Then $\forall \epsilon\in (0,1)$ we have $\Pr[S \ge (1+\epsilon)E[S]]$ is at most $\exp(-\epsilon^2 \mu/3)$.

To use this to prove your bound, let $S$, $a$, $n$, $\tau$, and $t$ be as in your question. Assume WLOG by scaling that $\tau=1$. Then, letting $\epsilon = t/E[S] \le 1$, $$\begin{aligned} \Pr[S \ge E[S] + t] & {} = \Pr[ S \ge (1+\epsilon) E[S]] \\ & {} \le \exp(-\epsilon^2 E[S]/3) && \text{(Lemma 1)}\\ & {} = \exp(-(t/E[S])^2 E[S]/3) \\ & {} = \exp(-t^2 / (3E[S])) \\ & {} \le \exp(-t^2/(3np)), && \text{(see below)} \end{aligned} $$ where the last line follows from $E[S] = \sum_{i=1}^n a_i p \le np$.

My guess is you can handle the case when $t>E[S]$ similarly but using the less simplified form of the upper bound in the standard multiplicative Chernoff bound (as one does to handle the case $\epsilon>1$ when using that bound).