Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove that $$ p_1 + \sum_{k=2}^n \left(p_k\prod_{i=1}^{k-1}(1-p_i)\right) = 1 - \prod_{k=1}^n(1-p_k)\ . $$ I'm working in a code where I have to do those computations. I want to see if this equality holds in general (in order to save a lot of computation time). I tested it in practice and it seems that it is true but having the general proof would be great.

Thank you.

share|improve this question
    
Edited, since the conditions $p_1,\ldots,p_n\in \mathbb{R}$ and $ \sum_{k=1}^n p_k= 1\ . $ are clearly not needed (those were in the original question). –  FKaria Feb 16 '12 at 21:28
add comment

4 Answers

up vote 3 down vote accepted

Define, as in your second equation,

$$a_n=p_1 + \sum_{k=2}^n \left(p_k\prod_{i=1}^{k-1}(1-p_i)\right) \text{ and } b_n=1 - \prod_{k=1}^n(1-p_k)$$

Then

$$a_{n+1}-a_n=p_{n+1}\prod_{i=1}^n(1-p_i)=\left(1-\prod_{k=1}^{n+1}(1-p_k)\right)-\left(1-\prod_{k=1}^n(1-p_k)\right)=b_{n+1}-b_n.$$

With the fact that $a_1=b_1$, we must have $a_n=b_n$ for all $n$ by induction. This shows the equality holds regardless of what values the $p_i$ take on: it's just a generic telescoping reformulation.

share|improve this answer
    
So simple! Thanks a lot! –  FKaria Feb 16 '12 at 21:14
add comment

Take $A_1,\ldots A_n$ $n$ independent events with $P(A_i)=p_i$. Then $$p_1+\sum_{k=2}^np_k\prod_{i=1}^{k-1}(1-p_i)=P(A_1)+\sum_{k=2}^nP(A_k)P\left(\bigcap_{i=1}^{k-1}A_i^c\right)=P\left(\bigcup_{k=1}^nA_k\right)$$ since it's a disjoint union and $$1-\prod_{k=1}^n(1-p_k)=1-\prod_{k=1}^nP(A_k^c)=1-P\left(\bigcap_{k=1}^nA_k^c\right)=P\left(\left(\bigcap_{k=1}^nA_k^c\right)^c\right)=P\left(\bigcup_{k=1}^nA_k\right).$$ Note that we didn't use the fact that $\sum_{j=1}^np_i=1$.

share|improve this answer
    
+1: Same as what I have. (I have simplified it a bit I suppose). –  Aryabhata Feb 16 '12 at 21:23
add comment

A probabilistic interpretation (perhaps easier to understand as compared to Davide's answer).

You have $n$ coins, coin $i$ has probability $p_i$ of showing heads.

Now you toss coin 1, coin 2, coin 3 in order, till you get a heads, in which case you stop.

The probability that you get heads is

$$p_1 + p_2(1-p_1) + p_3(1-p_1)(1-p_2) + \dots + p_n(1-p_1)\dots(1-p_{n-1})$$

This is same as the probability of not having all tails which is

$$ 1 - (1-p_1)(1-p_2)\dots(1-p_n)$$

You left hand side is the first expression and the right hand side is the second.

share|improve this answer
add comment

Imagine that $E_1,E_2,\dots,E_n$ are the mutually exclusive possible outcomes of an experiment, where $E_k$ occurs with probability $p_k$. You perform the experiment $n$ times in a row, getting outcomes $R_1,\dots,R_n$. Say that the $k$-th trial is a hit if $R_k=E_k$. The righthand side of your equation is the probability of getting at least one hit. The term $p_k\prod_{i=1}^{k-1}(1-p_i)$ on the lefthand side is the probability that the first hit occurs on the $k$-th trial. For distinct $k$ these possibilities are disjoint, so the sum on the left is clearly the same probability as the righthand side.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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