# Chernoff bound for weighted sums of Bernoulli random variables

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.

• How does your bound relate to the following standard multiplicative variant of the Chernoff bound? $$\Pr[S > (1+\epsilon) E[S]] \le \exp(-\epsilon^2 E[S]/3)$$ (assuming here by scaling that $\tau=1$) Jan 16, 2023 at 1:29
• When all $a_i$'s equal to $1$, this is exactly Chernoff bound. To see this, let $\epsilon = t / \mathbf{E}[S] = t / np$, the inequality can be rewrite as $\Pr[S > (1 + \epsilon)\mathbf{E}[S]] \leq \exp(-C(\epsilon np)^2 / (np)) = \exp(- C\epsilon^2 \mathbf{E}[S] )$. Jan 16, 2023 at 2:50
• I'm not asking about the case when all $a_i$'s equal 1. I'm suggesting you consider the general case (which reduces by scaling to the case $\tau=1$). Note that the bound I cite makes no assumptions on the $X_i$'s other than that they are independent and in $[0,1]$. Jan 16, 2023 at 3:42

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).
• Thank you! It's a very neat proof and works perfectly when $\tau = 1$. However, when $\tau < 1$, it seems that the above argument gives $\exp(-t^2 / (3np\tau))$, while the bound using Hoeffding inequality has $\tau^2$ in the denominator, which is particularly useful when $\tau$ is very small. So my anticipated bound also has $\tau^2$ in it. Jan 16, 2023 at 4:31
• @XinyuMao “Assume WLOG by scaling that $τ=1$” means $\Pr[S\ge E[S]+t]=\Pr[\frac1\tau S\ge E[\frac1\tau S]+\frac t\tau]\le\exp(-(t/\tau)^2/3np)$ for arbitrary $\tau>0$. Jan 16, 2023 at 7:47