Take the 2-minute tour ×

Suppose that we have $n$ independent random variables, $x_1,\ldots,x_n$ such that each $x_i$ takes value $a_i$ with success probability $p_i$ and value $0$ with failure probability $1-p_i$ ,i.e.,

\begin{align} P(x_1=a_1) & = p_1,\ P(x_1=0)= 1-p_1 \\ P(x_2=a_2) & = p_2,\ P(x_2=0) = 1-p_2 \\ & \vdots \\ P(x_n=a_n) & = p_n,\ P(x_n=0)=1-p_n \end{align}

where $a_i$'s are positive Real numbers.

What would be the CDF of the sum of these random variables? That is, what would be $P(x_1+\cdots+x_n\le k)$ ? and how can we find it in an efficient way?

share|improve this question
It should be divised in many cases if there is an aswer for this. For example, if we have only three variables giving $a_1$, $a_2$ and $a_3$. If the three are different, we have $8$ possible values to get. If the three are equal, we have only $4$ possible values to get on the sum. And when $n$ gets bigger, the difficulties increase with combinations. –  juanrapha Dec 20 '12 at 3:27
A sum of iid Bernoulli trials has a Binomial distribution, not Poisson. The distribution you described does not have a name. –  Jonathan Christensen Dec 20 '12 at 3:28
The ordinary binomial distribution is a special case of the Poisson binomial distribution, when all success probabilities are the same: en.wikipedia.org/wiki/Poisson_binomial_distribution –  May Dec 20 '12 at 3:29
I edited the question and deleted the part regarding Poisson binomial distribution since it was not relevant to my question. –  May Dec 20 '12 at 4:19
add comment

3 Answers

up vote 4 down vote accepted

This will be CDF of discrete distribution with certain number of values $s_1,...,s_r$ where $r$ is number of possible distinct sums among all subsets $\{a_{i_1},...,a_{i_m}\}$. It is not possible to evaluate $r$ in general case because this number solely depends on particular values $a_1,...,a_n$ and can vary from $n+1$ to $2^n$. The minimal $r=n+1$ is represented by case of $a_1=a_2=...=a_n$ while maximal $r=2^n$ is always achieved when ascending reordered set $\{a_{(1)},...,a_{(n)}\}$ complies with the condition: $\forall i: \sum\limits_{1\le j<i}a_{(j)}\le a_{(i)}$. Example of such maximal case could be $a_i=2^{i-1}$. Note, that failing this condition does not necessarily mean $r<2^n$. For example, for $a_i=ln(prime(i))$ the condition above fails, however all possible sums $a_{i_1}+...+a_{i_m}$ are still distinct, causing $r=2^n$.

We can always consider set $\{s_1,...,s_r\}$ as ordered, then $s_1=0$ and $s_r=\sum\limits_i a_i$. Then $$P(s_1)=P(0)=\prod\limits_i (1-p_i)$$ as all $x_i=0$; $$P(s_r)=P\left(\sum\limits_i a_i\right)=\prod\limits_i p_i$$ as all $x_i=a_i$; and $$P(s_k)=\sum\limits_{i_1,...,i_m|a_{i_1}+...+a_{i_m}=s_k}\left(\prod\limits_{j\in\{i_1,...,i_m\} } p_j\times\prod\limits_{j\in[1;n]\setminus\{i_1,...,i_m\} } (1-p_j)\right)=\\P(0)\times\sum\limits_{i_1,...,i_m|a_{i_1}+...+a_{i_m}=s_k}\left(\prod\limits_{j\in\{i_1,...,i_m\} }\frac{p_j}{1-p_j}\right)$$ as we can eliminate the second product of complemented set $[1;n]\setminus\{i_j\}$ by using the fact that $P(0)$ contains all $(1-p_i)$ for the whole set $[1;n]$.

share|improve this answer
to calculate $P(x_1+⋯+x_n≤k)$ we need to find all the $s_i$ 's that $s_i<=k$ right? –  May Feb 2 '13 at 21:31
do you mean $P(s_k)=P(x_1+⋯+x_n=k)$? –  May Feb 2 '13 at 22:06
would you please explain your solution to me more? thank you. –  May Feb 3 '13 at 1:48
Yes, as I started to talk about discrete distribution, I implied discrete form of CDF such as $P(s_k) = P(x_1+...+x_n=s_k)$ for all $s_k$ (sum is equal to $s_k$ not $k$) and $P(m)=0$ for any other $m$. This simplified the result but I accept that I needed to state it explicitly. As $\{s_k\}$ is set of fixed consts depending only on consts $\{a_k\}$, then I simplified the result by using this new set instead of the original consts. The last simplification was working on the result by eliminating the complementary set of sums using structure of $P(0)$. –  Van Jone Feb 6 '13 at 23:17
thank you a lot for your clarification. –  May Feb 7 '13 at 0:04
add comment

This answer is an attempt at providing an answer to a previous version of the question in which the $x_i$ were independent Bernoulli random variables with parameters $p_i$.

$P\{\sum_{i=1}^n x_i = k\}$ equals the coefficient of $z^k$ in $(1-p_1+p_1z)(1-p_2+p_2z)\cdots(1-p_n+p_nz)$. This can be found by developing the Taylor series for this function. It is not much easier than grinding out the answer by brute force.

share|improve this answer
add comment

My solution to this problem is as follows

$P(x_1+⋯+x_n≤k)=∑ ^ n _{m=0}∑ _{A\epsilon T_m } \Pi_{i \epsilon A} p_i \Pi_{i \epsilon A^c } (1-p_i) $


$T_m=${{$r_1$,...,$r_m$}| $ a_{r_1}+...+a_{r_m}<=k$ }

and $A^c$ is the complement of $A$.

share|improve this answer
@Van Jone : I have this solution but I am not sure if it is correct. –  May Feb 2 '13 at 21:54
Yes, your approach is correct. The difference to my solution is that I tried to go even further and squeeze as much as possible results by investigating intrinsic structure of set ${T_m}$ and how it "visually" contributes to behaviour of CDF. I could achieve it by presenting CDF in more particular discrete form and working out the result to eliminate some "impractical" operators such as $\sum$ and $\prod$. –  Van Jone Feb 6 '13 at 22:59
SE "ate" curly braces where I said "set" and for some unknown reason it refuses any edits after 5 mins. So please use your imagination to put the braces and read $\{T_m\}$ instead of ${T_m}$ –  Van Jone Feb 6 '13 at 23:22
add comment

Your Answer


