When does the variance of the sum of Bernoulli r.v.s attain a maximum?

Question

Let $Y = X_1 + ... + X_n$, where the $X_i$ are independent Bernoulli random variables taking values in $\{0, 1\}$, with $P(X_i = 1) = p_i$.

We can prove that: $$E(Y) = \sum_{i=1}^n p_i \text{ and } \text{Var}(Y) = \sum_{i=1}^n p_i(1-p_i)$$

Keeping $E(Y)$ fixed, I am trying to prove that $Var(Y)$ is maximal when $p_1 = ... = p_n$.

Writing $\text{Var}(Y) = \sum_{i=1}^n p_i(1-p_i) = \sum_{i=1}^n p_i - \sum_{i=1}^n p_i^2 = E(Y) - \sum_{i=1}^n p_i^2$. Then we want to minimize $\sum_{i=1}^n p_i^2$ without changing $\sum_{i=1}^n p_i$. I'm not sure where to go from here.

I would appreciate a small hint to point me in the right direction. Thank you!

Answer 1

Observe that $Var(Y)=\sum_{i} (p_i-p_i^2)$ is a concave function of the $\mathbf p$ vector. Let us compute the gradient of this function as \begin{align*} \nabla_{\mathbf p} Var(Y) &= \mathbf 1-2\mathbf p \end{align*} Where $\mathbf 1$ is the all one vector. This is constrained optimization of concave function and so the optimal solution $\mathbf p^\ast$, such that $\sum_i p^\ast_i = \mathbb E [Y]$, satisfies for any $\mathbf p$ in the constrained domain, \begin{align*} &\nabla_{\mathbf p^\ast} Var(Y)^T (\mathbf p - \mathbf p^\ast) \leq 0 \end{align*} This condition is standard and pretty intuitive if you think it means that the tangent plane at $\mathbf p^\ast$ needs to be above the function for all point in the constrained domain, concavity does the rest. For more information you can see any convex optimization material such as this one on page 11, having concavity means that $-f$ is convex and so it reverse the inequality. I don't actually know the name of this handy condition

So the only thing you need to show is that this means that $\mathbf p^\ast = c \mathbf 1$ is you solution for constant $c=\mathbb E [Y]/n$.

You can plug in everything to get \begin{align*} (\mathbf 1 - 2 c \mathbf 1)^T(\mathbf p - c \mathbf 1)&=(1-2c)\mathbf 1^T(\mathbf p - c \mathbf 1)\\ &=(1-2c)\sum_i (p_i-c)\\ &=(1-2c)\left( \sum_i p_i - nc \right)\\ &=(1-2c)(\mathbb E [Y] - \mathbb E [Y])\\ &= 0 \end{align*}

Which indeed satisfy the inequality and so you are right, having $p_1=p_2=\dots = p_n$ gives an optimal solution

Answer 2

By Cauchy-Schwarz, we have that $$(\sum_{i=1}^n a_ib_i)^2 \leq \sum_{i=1}^n a_i^2 \sum_{i=1}^n b_i^2$$ Choosing $a_i = p_i$ and $b_i = 1$, we have $$(\sum_{i=1}^n p_i)^2 \leq n\sum_{i=1}^n p_i^2 \Rightarrow \frac{E(Y)^2}{n} \leq \sum_{i=1}^n p_i^2$$. If we can provide a choice of $p_1, ..., p_n$ which attains equality, then this choice minimizes $\sum_{i=1}^n p_i^2$. Suppose $p_1 = ... = p_n $, then we have that $$E(Y) = \sum_{i=1}^n p_i \Rightarrow p_1 = ... = p_n = \frac{E(Y)}{n}$$ And that $\sum_{i=1}^n p_i^2 = \sum_{i=1}^n (\frac{E(Y)}{n})^2 = \frac{E(Y)^2}{n}$.