# Convex Combinations of Low Probability Bernoulli Variables

Let $X_1,\dots,X_n$ be independent Bernoulli variables with probability $p<\frac{1}{2}$ (even $p\le\frac{1}{3}$ if needed). Let $\alpha_1,\ldots,\alpha_n$ be non-negative real numbers such that $\sum\limits_{i=1}^n \alpha_i = 1$, and let $Y = \sum\limits_{i=1}^n \alpha_i X_i$.

Prove (or disprove): $\Pr(Y\ge p)\ge p$.

I can prove this for all $p=\frac{1}{k}$, $k\ge3$, but intuitively it seems to me that it should be true for all $p<\frac{1}{2}$, and I could not find a proof for that.

EDIT: my (or rather, a friend's) proof for $p = \frac{1}{k}$:

For each Bernoulli variable define a random variable $Z_i$ that takes values from a set of formal objects $\{b_1,\ldots b_k\}$ uniformly, and define a function $f$ on these formal objects as $f(b_1) = 1$, $\forall_{i>1}f(b_i)=0$.

Clearly, $f(Z_i)$ is a Bernoulli variable with probability $p$, but the sample space for a convex combination of $f(Z_1),\ldots f(Z_n)$ can be now viewed as consisting of $k^n$ states of the form $(b_{i_1},\ldots,b_{i_n})$ from which one is selected uniformly.

Group these states into sets of $k$ states of cyclic shifts of the indices (that is, $(b_{i_1},\ldots,b_{i_n})$ and $(b_{j_1},\ldots,b_{j_n})$ are in the same set iff for all for all $1\le s \le n$, $b_{j_s} = b_{i_s} + c (\mod k)$ for some $s$-independent integer $c$).

The sum of the values of a convex combination of such sets under $f$ is exactly $1$, since each component is $b_0$ in exactly one member of the set, so in each set there exists at least one state whose value is greater than or equal to $\frac{1}{k}$.

To sum up, I have proven that the new sample space can be divided into sets of $k$ points such that in each set there exists at least one point valued above (or at) $\frac{1}{k}$, and the probability of choosing such a point is at least $\frac{1}{k}$.

-

Counterexample: $n=3$, $p=0.48$, $\alpha_1=0.44$, $\alpha_2=\alpha_3=0.28$

The set $Y\ge p$ has probability $0.470016$

-
Thanks! Is it also false for $p \le \frac{1}{3}$? I can't find a way to extend the counterexample. – Alfonso Fernandez Dec 26 '12 at 15:19
It does not seem easy to get some general conclusion from this. Perhaps you could post your proof for $p=1/3$? – leonbloy Dec 26 '12 at 15:55

Here is another counterexample: $n=3$, $p=0.35$, $\alpha_1 = 0.33$, $\alpha_2 = \alpha_3 = \frac{1-\alpha_1}{2}$, then $\mathbb{P}[Y \geq p] \approx 0.281475$

I tried to generalize the counterexmaple in the following way: Consider $Y= \sum_{i=1}^n \alpha_i \cdot X_i$ where $\alpha_k = \frac{1-\alpha_1}{n-1}$ for $k \geq 2$ and $\alpha_1$ is chosen close to $p$. Then one can calculate $\mathbb{P}[Y \geq p]$ explicitely (using combinatorics).

Until now I wasn't able to find $p \leq \frac{1}{3}$ and $n \in \mathbb{N}$ such that $\mathbb{P}[Y \geq p] < p$...

-