2
$\begingroup$

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.

$\endgroup$

3 Answers 3

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – fstab
    Nov 9, 2014 at 22:38
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.