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!

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!

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)<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 I don't really believe that this bound is tight. In particular, the above bound is trivial when $\alpha=1$, but intuitively I think it is possible to bound $Pr[Y<1]$ away from $1$.

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!