Fun problem. Apparently $\prod_i(1-p_i) \geq 1 - \sum_ip_i$ with $p_i \in [0,1]$ is always true. But how to demonstrate it?

Question

so, I want to demonstrate the validity of the following inequality:

$$ \prod_i(1-p_i) \geq 1 - \sum_ip_i $$

with $p_i \in [0,1]$, it is always true, which it seems to be always the case if you test it with some random numbers.

So, i tried to do a demonstration. I started by noticing that I could replace $p_i$ with $1-q_i$ obtaining the following inequality:

$$ \prod_iq_i \geq 1 - \sum_i(1 - q_i) $$

That, if the quantity of numbers is $n$ becomes:

$$ \prod_iq_i \geq 1 - n + \sum_iq_i $$

Now it's possible to establish the truthfulness of the inequality under certain conditions, by noticing the range of the various terms:

$$ \prod_iq_i \in [0,1]\\ \sum_iq_i \in [0,n] $$

Therefore: $$ 1 - n + \sum_iq_i \in [-(n+1),1] $$

Luckily, at least I have now demonstrated that if $\sum_iq_i \leq n-1$, then the inequality is true, which is good, because it covers most cases (especially for $n \rightarrow \infty$)!

Now I am left with the problem of the last case: $\sum_iq_i \in [n-1,n]$, and I am stuck.

How would you demonstrate the inequality for this subset of cases?

A last few passages: if I use a $\delta$ term for the uncovered subset of cases as follows: $$ \sum_i q_i = n-1+\delta $$

Then all I have to demonstrate is that $\prod_iq_i \geq \delta$.

Stuck.

Answer 1

Isn't this straight forward by induction? The base case $P(n=1)$, easy.

Suppose $P(k)$. Then

$$\prod_{i=1}^{k+1} (1 - p_i) = \left(\prod_{i=1}^{k} (1 - p_i) \right) (1 - p_{k+1}) \geq \left( 1 - \sum_{i=1}^k p_i\right)(1 - p_{k+1}) $$

$$ = 1 - \sum_{i=1}^{k+1} p_i + p_{k+1} \sum_{i=1}^k p_i \geq 1 - \sum_{i=1}^{k+1} p_i$$

...this last inequality as the $p_i$ are non-negative. I.e., $P(k) \Rightarrow P(k+1)$ for arbitrary $k \geq 1$.

Answer 2

Assume that both sides are positive, since otherwise, it's easy!

Taking inverses, we need to show

$$ \prod \left(1-p_i\right)^{-1} \leq \frac{1}{1-\sum p_i} $$

Expanding the geometric series, the right hand side becomes $$ 1 + \sum p_i + \left( \sum p_i \right) ^2 + \ldots $$

and the left hand side becomes

$$ \left( 1 + p_1 + p_1^2 + \ldots \right) \cdot \ldots \cdot \left( 1 + p_n + p_n^2 + \ldots \right) $$

Expanding out, and looking at the term of degree $k$, on the left hand side we get every possible $p_1^{j_1}\cdot\ldots\cdot p_n^{j_n}$ with $\sum j_i = k $ exactly once, but for the right hand side, we can get the same term multiple times. For example, in the case $k=2$ and $n=2$, we get $p_1^2 + p_1p_2 + p_2^2$ for the left hand side and we get $p_1^2 + 2\cdot p_1p_2 + p_2^2$ for the right hand side.

THis has a nice combinatorial explanation, too. The $k^{th}$ term is giving you the number of ways to pick $k$ objects where order doesn't matter for the left hand side and the right hand side is where order matters.

Answer 3

Thanks to Simon S for his answer using induction. It's possible to solve by induction also by subtracting $p_{k+1}$ on both sides of the $k$-th case:

$$ \prod_i^k(1-p_i)-p_{k+1} \geq 1 - \sum_i^{k+1}p_i\\ \frac{\prod_i^{k+1}(1-p_i)}{1-p_{k+1}} - p_{k+1} \geq 1 - \sum_i^{k+1}p_i\\ $$

Multiplying both sides for the positive quantity $1-p_{k+1}$, the inequality is still valid:

$$ \prod_i^{k+1}(1-p_i) - p_{k+1}(1-p_{k+1}) \geq (1 - \sum_i^{k+1}p_i)(1-p_{k+1}) $$ $$ \prod_i^{k+1}(1-p_i) - p_{k+1} + p_{k+1}^2 \geq 1 - \sum_i^{k+1}p_i - p_{k+1} + p_{k+1}\sum_i^{k+1}p_i $$ $$ \prod_i^{k+1}(1-p_i) + p_{k+1}^2 \geq 1 - \sum_i^{k+1}p_i + p_{k+1}\sum_i^{k+1}p_i $$ $$ \prod_i^{k+1}(1-p_i) \geq 1 - \sum_i^{k+1}p_i + p_{k+1}\sum_i^{k+1}p_i - p_{k+1}^2 $$ $$ \prod_i^{k+1}(1-p_i) \geq 1 - \sum_i^{k+1}p_i + p_{k+1}\sum_i^{k}p_i \\ $$

Since the quantity $p_{k+1}\sum_i^{k}p_i$ is still positive, then the inequality for the case $k+1$ is still valid.