# Is it true that $\sum_{k=1}^n(p_k\prod_{i=1}^k(1-p_i)) \stackrel{\mbox{?}}{=} 1 - \prod_{i=1}^n(1-p_i)$

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.

-
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

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.

-
So simple! Thanks a lot! –  FKaria Feb 16 '12 at 21:14

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

-
+1: Same as what I have. (I have simplified it a bit I suppose). –  Aryabhata Feb 16 '12 at 21:23

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.

-

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.

-