A puzzle on random variables that must have the same sum $X_1,\dots,X_n$ and $Y_1,\dots,Y_n$ are random variables that take values in $\{0,1\}$. Their distribution is unknown, each variable may have a different distribution and they might be dependent. The only known facts are:


*

*$\sum_{i=1}^n X_i = \sum_{i=1}^n Y_i$

*For all $i$, $\Pr[X_i=0] \geq \alpha$

*For all $i$, $\Pr[Y_i=1] \geq \alpha$


I would like to prove (or disprove) that $\alpha \leq 1/2$.
The claim is obviously true for $n=1$, since in this case there are only two options:
A. $X_1 = Y_1 = 0$
B. $X_1 = Y_1 = 1$
Each of these options must happen with probability at least $\alpha$, but the total probability of these options is at most 1, so $\alpha$ must be at most $1/2$.
Is the claim also true for $n>1$?
 A: Since expectation is linear you can write $$\mathbb{E}\left(\sum_{i=1}^{n}X_{i}\right) = \sum_{i=1}^{n}\mathbb{P}(X_{i}=1) \leq n(1-\alpha)\ .$$ Similarly, $$\mathbb{E}\left(\sum_{i=1}^{n}Y_{i}\right) = \sum_{i=1}^{n}\mathbb{P}(Y_{i}=1) \geq n\alpha\ .$$
Since the two expectations are equal you have the following inequality, valid for any integer $n>0\ .$
$$n\alpha \leq n(1-\alpha) \quad \Rightarrow \quad \alpha \leq \frac{1}{2}\ .$$
A: Thanks to linearity of expectation, this is indeed true. Taking the expectation of both sides yields:
$$\mathbb{E}\left(\sum_{i = 1}^{n}X_i\right) = \mathbb{E}\left(\sum_{i = 1}^{n}Y_i\right)$$
$$\sum_{i = 1}^{n}\mathbb{E}(X_i) = \sum_{i = 1}^{n}\mathbb{E}(Y_i)$$
$$\sum_{i = 1}^{n}\left(1-\Pr[X_i = 0]\right) = \sum_{i = 1}^{n}\Pr[Y_i = 1]$$
Then, since $\Pr[X_i = 0] \ge \alpha$ and $\Pr[Y_i = 1] \ge \alpha$, we have: $$n-n\alpha \ge \sum_{i = 1}^{n}\left(1-\Pr[X_i = 0]\right) = \sum_{i = 1}^{n}\Pr[Y_i = 1] \ge n\alpha$$
Since $n-n\alpha \ge n\alpha$, we get $\alpha \le \dfrac{1}{2}$, as desired.
