1
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ Can you show it for $n=2$? If so, this would mean that any example of $p_i \not = p_j$ would not have minimal variance $\endgroup$
    – Henry
    Oct 12, 2018 at 6:56
  • $\begingroup$ @Henry do you mean to provide a proof by induction? I don't understand why proving that the statement holds for $n=2$ would extend to any $n$. $\endgroup$ Oct 12, 2018 at 7:10
  • 2
    $\begingroup$ If there is any pair which are different then you can reduce the variance by replacing them both by their average. So the minimum variance happens when they are all the same $\endgroup$
    – Henry
    Oct 12, 2018 at 7:18

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I have doubts about the first implication, could you expend it ? $\endgroup$
    – P. Quinton
    Oct 12, 2018 at 7:15
  • $\begingroup$ @P.Quinton Oops I had some errors there, fixed now $\endgroup$ Oct 12, 2018 at 7:37
  • 1
    $\begingroup$ Isn't it $\mathbb E [Y]^2/n\leq \sum p_i^2$ ? $\endgroup$
    – P. Quinton
    Oct 12, 2018 at 7:40
  • $\begingroup$ But then if you add a squared at the end too, your argument works nicely $\endgroup$
    – P. Quinton
    Oct 12, 2018 at 7:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .