<p>Your bound (at least when <span class="math-container">$t\le E[S]$</span>) seems to follow from the standard multiplicative Chernoff bound, as follows.</p>
<p><strong>Lemma 1.</strong> (a standard <a href="https://algnotes.info/on/background/probabilistic-method/chernoff-proof/" rel="nofollow noreferrer">multiplicative Chernoff bound</a>) <em>Let <span class="math-container">$S$</span> be the sum of independent random variables in <span class="math-container">$[0,1]$</span>.  Then <span class="math-container">$\forall \epsilon\in (0,1)$</span> we have <span class="math-container">$\Pr[S \ge (1+\epsilon)E[S]]$</span> is at most <span class="math-container">$\exp(-\epsilon^2 \mu/3)$</span>.</em></p>
<p>To use this to prove your bound, let <span class="math-container">$S$</span>, <span class="math-container">$a$</span>, <span class="math-container">$n$</span>, <span class="math-container">$\tau$</span>, and <span class="math-container">$t$</span> be as in your question.  Assume WLOG by scaling that <span class="math-container">$\tau=1$</span>.  Then, letting <span class="math-container">$\epsilon = t/E[S] \le 1$</span>,
<span class="math-container">$$\begin{aligned}
\Pr[S \ge E[S] + t]
&amp; {} = \Pr[ S \ge (1+\epsilon) E[S]] \\
&amp; {} \le \exp(-\epsilon^2 E[S]/3) &amp;&amp; \text{(Lemma 1)}\\
&amp; {} = \exp(-(t/E[S])^2 E[S]/3) \\
&amp; {} = \exp(-t^2 / (3E[S])) \\
&amp; {} \le \exp(-t^2/(3np)), &amp;&amp; \text{(see below)}
\end{aligned}
$$</span>
where the last line follows from <span class="math-container">$E[S] = \sum_{i=1}^n a_i p \le np$</span>.</p>
<p>My guess is you can handle the case when <span class="math-container">$t&gt;E[S]$</span> similarly but using the less simplified form of the upper bound in the standard multiplicative Chernoff bound (as one does to handle the case <span class="math-container">$\epsilon&gt;1$</span> when using that bound).</p>

CC BY-SA 4.0
2023-01-16T04:31:30.227Z
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.
Xinyu Mao
CC BY-SA 4.0
2023-01-16T07:47:49.450Z
@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$.
Emil Jeřábek
CC BY-SA 4.0
2023-01-16T08:42:39.280Z
@EmilJeřábek Thanks! I think the question is then fully resolved.
Xinyu Mao
CC BY-SA 4.0
2023-01-16T04:05:42.453Z
2023-01-16T04:05:42.453Z
Neal Young
<p>I tried to prove the following Chernoff-type bound when doing research, and found that it is of indepent interest.</p>
<p>Let <span class="math-container">$X_1, \dots, X_n$</span> be independent random varibles such that each <span class="math-container">$X_i$</span> is a Bernoulli random varible with parameter <span class="math-container">$p$</span>, i.e., <span class="math-container">$\Pr[X = 1] = 1 - \Pr[X = 0] = p$</span>.
Moreover, we have weights <span class="math-container">$a_1, \dots, a_n \in [0, \tau]$</span>, and write <span class="math-container">$S := \sum_{i = 1}^n a_iX_i$</span>.
I tried to show that<br />
<span class="math-container">$$
\Pr[S &gt; \mathbf{E}[S] + t] \leq \exp\left(-\frac{Ct^2}{np\tau^2}\right), \forall t &gt; 0
$$</span>
where <span class="math-container">$C$</span> is a constant.</p>
<p>One can surely apply <a href="https://en.wikipedia.org/wiki/Hoeffding%27s_inequality" rel="nofollow noreferrer">Hoeffding bound</a> here, which yields
<span class="math-container">$$
\Pr[S &gt; \mathbf{E}[S] + t] \leq \exp\left(-\frac{2t^2}{n\tau^2}\right), \forall t &gt; 0.
$$</span>
The drawback is that Hoeffding bound only uses the range of the random variables, however, it does not exploit the property that <span class="math-container">$X_i$</span>'s are Bernoulli variables,
and hence a <span class="math-container">$p$</span> factor is missing.</p>
<p>I tried to adapt the proof of Chernoff bound, but unfortunately failed. I would apprecaite it if anyone have some idea on it.</p>

CC BY-SA 4.0
2023-01-16T01:29:11.687Z
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$)
Neal Young
CC BY-SA 4.0
2023-01-16T02:50:43.587Z
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] )$.
Xinyu Mao
CC BY-SA 4.0
2023-01-16T03:42:32.813Z
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]$.
Neal Young
<pr.probability><randomness><chernoff-bound>
Chernoff bound for weighted sums of Bernoulli random variables
Xinyu Mao
# Chernoff bound for weighted sums of Bernoulli random variables

(Asked by: username_0 on 2023-01-15)

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](https://en.wikipedia.org/wiki/Hoeffding%27s_inequality) 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.

**Tags:** pr.probability, randomness, chernoff-bound
> **Comments:**
> **username_1**: 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$)  
> **username_0**: 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] )$.  
> **username_1**: 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]$.  

---

## 1 answers

### Answer by username_1 on 2023-01-16. Score: 2 | Accepted answer

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](https://algnotes.info/on/background/probabilistic-method/chernoff-proof/)) *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).

> **Comments:**
> **username_0**: 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.  
> **username_2**: @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$.  
> **username_0**: @EmilJeřábek Thanks! I think the question is then fully resolved.  

---

