4
$\begingroup$

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.

  • 0
    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).2012-02-16

4 Answers 4

3

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.

  • 0
    So simple! Thanks a lot!2012-02-16
2

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

  • 0
    +1: Same as what I have. (I have simplified it a bit I suppose).2012-02-16
2

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.

2

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.