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!


1 Answer 1


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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.