Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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$

share|cite|improve this answer
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$...

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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