# 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?

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.

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

• Cool! So the trick is to get a base case, and demonstrate that if the $k$-th case is true, then also the $k+1$-th case is true. I wonder about the generalizability of this technique, if it can be applied to all inequalities that involve product or summation at the left hand-side (or the right hand-side. The "magic" is that here, on the right hand-side we get the summation expression plus a negative constant. I wonder if we could demonstrate this also by subtracting $p_{k+1}$ to both sides at the $k$-th case. Nov 9, 2014 at 22:38

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.

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.