Weighted Chernoff Bound

252 Views Asked by At

Given $n$ independent Bernoulli r.v.s $X_1,\ldots,X_n$, where $X_i$ has probability $p_i$ to be $1$, the standard Chernoff inequality bound the probability that $\sum_{i=1}^n X_i$ is far from its expectation.

I'm interested in a case where each $X_i$ is associated with a weight $w_i$, all $p_i$'s are identical (i.e., $p=p_1=\ldots,p_n$), and I'm looking to bound the probability that $X=\sum_{i=1}^n{w_iX_i}$ is far from $\mathbb E[X]=pW$ where $W=\sum_{i=1}^n w_i$.

Can we get a bound of the form $\Pr[X>Wp(1+\delta)]= f(Wp,\delta)$, similar to how the standard Chernoff inequality can be written if $w_1=\ldots=w_n$ as (for $\delta\le 1$) $$ \Pr[X\ge \mathbb E[X](1+\delta)]\le e^{-\mathbb E[X] \delta^2/3}? $$