# concentration inequality for a weighted sum of independent but not identical binary variables

Let $$\alpha\in[0,1]$$ be a fixed constant, and let $$w,x\in[0,1]^n$$ be two vectors such that $$\sum_i w_i x_i=\alpha$$.

Define $$Y = \sum_i w_i X_i$$, where $$X_i \sim \operatorname{Bernoulli}(x_i)$$, so it holds $$\mathbb{E}[Y]=\alpha\leq 1$$, and assume that the $$X_i$$'s are independent variables, .

Can we use some concentration inequality for $$Y$$ to obtain some bound of the form $$\Pr[Y>1] \leq c(\alpha)$$ for some constant $$c(\alpha)\ll 1$$? Of course, we know from Markov's inequality that $$\Pr[Y>1]\leq\alpha$$, but I wans hopping to optain better bounds using the particular structure of $$Y$$, in particular for $$\alpha$$ close (or even equal) to $$1$$.

What I tried so far

• The Chernoff-Hoeffding inequality gives me a bound of the form $$\Pr[Y>1] \leq \exp\left(-\frac{2(1-\alpha)^2}{n}\right),$$ but this is useless when $$n\to\infty$$.

• We can also use Bernstein inequality, as $$\mathbb{V}[Y]=\sum_i w_i^2 x_i (1-x_i)\leq\sum_i w_i x_i=\alpha$$, to obtain: $$\Pr[Y>1] \leq \exp\left(-\frac{(1-\alpha)^2}{2(\alpha+\frac{1-\alpha}{3})}\right).$$ This is better, but it does not beat the Markov bound $$\Pr[Y>1]\leq \alpha$$ neither!

Without further restrictions on $$w,x$$, you cannot beat the Markov bound by much for $$\alpha$$ close to $$1$$ (as in your post).
Indeed, let $$a:=\alpha$$. Let $$x_i=a$$ for all $$i=1,\dots,n$$, and let $$w_1=1$$ and $$w_2=\cdots=w_n=0$$. Then all the conditions in the OP on $$w,x$$ will hold, and $$\begin{equation} P(Y\ge1)=P(X_1=1)=a, \end{equation}$$ which is the Markov bound on $$P(Y\ge1)$$.
For $$P(Y>1)$$ and $$a$$ close to $$1$$, you can get about half as good as this, as follows. Take any natural $$n\ge2$$ and any $$a\in(0,1]$$. For $$t\in(0,a/2)$$, let $$\begin{equation} w_1=\frac a2,\quad w_2=1+t-\frac a2,\quad w_3=\cdots=w_n=0, \end{equation}$$ $$\begin{equation} x_1=\frac{a/2}{w_1}=1,\quad x_2=\frac{a/2}{w_2}=\frac a{2-a+t},\quad x_3=\cdots=x_n=0. \end{equation}$$ Then all the conditions in the OP on $$w,x$$ will hold, and one will also have $$w_1+w_2>1$$, whence $$\begin{multline} P(Y>1)=P(w_1X_1+w_2X_2>1)\ge P(X_1=X_2=1) \\ =x_1x_2=\frac a{2-a+t}\underset{t\downarrow0}\longrightarrow \frac a{2-a} =1-(1-a)(2+o(1)) \end{multline}$$ as $$a\uparrow1$$, which is indeed about about half as good for $$a$$ close to $$1$$ as the Markov bound $$a=1-(1-a)$$.