Given an $n$-vector $\vec{p}$ of probabilities that sum up to $1$.

What is the total probability of all possible combinations of picking $k$ elements out of the $n$ items?


Say $n=4$, $k=3$ and $\vec{p}=\left\langle0.5,0.3,0.15,0.05\right\rangle$, then the total probability it $p_s=0.0036$: there are four possible combinations:





I'm looking for an efficient way to calculate this result, without having to iterate over ${n \choose k}$ formulas.

  • $\begingroup$ Why do call the result a probability? Which event in which experiment? The closest I can think of is the experiment of picking an arbitrary subset from the $n$, where each $i$ has independent probability $p_i$ of being selected, and the event is that a subset of $k$ elements is selected. However (1) then there is no reason why $p_1+\cdots+p_n=1$ should be true, as the selections are not exclusive (2) then you should not only multiply the $p_i$ for the selected $i$, but also $(1-p_i)$ for the non-selected $p_i$. As you state it $k=0,1$ both give "probability" $1$ regardless, which is strange. $\endgroup$ Commented Nov 21, 2014 at 7:49

2 Answers 2


The value you want is the coefficient of $x^n$ in the polynomial $\displaystyle\prod_{i=1}^{n}(1+p_ix)$. You can multiply the factors one at a time and discard terms with $x^m$ for $m>k$. This will save some work if $k$ is much smaller than $n$. You can also use the binomial theorem to evaluate the product of repeated factors, if any of your $p_i$ values are equal. In your example, $p$ is $0.0036,$ not $0.003675$. $$(1+0.5) (1+0.3x) (1+0.15x) (1+0.05 x)=1 + 1. x + 0.3175 x^2 + 0.036 x^3 + 0.001125 x^4$$

  • $\begingroup$ Note that here $k=0,1$ both give probability $1$, and the "total probability" for all $k$ together is $2.354625$. I can see this method computes $\sum_{I\in\binom{[n]}k}\prod_{i\in I}p_i$ correctly, but I cannot make sense of this as a probability. This is really just restating my comment at the question. $\endgroup$ Commented Nov 21, 2014 at 7:56
  • $\begingroup$ This function is not a probability. It is the generating function for the total probability of picking $k$ elements. The probability of picking 0 elements is the coefficient of $x^0$, or 1. The probability of picking 1 element is the sum of the $p_i$, or 1. The probability of picking 2 elements is $0.3175$, etc. The sum of the coefficients is not 1, because the probabilities represented by the coefficients are not independent. For example, if you choose $3$ elements, you have chosen various combinations of $2$ elements as well. $\endgroup$
    – Steve Kass
    Commented Nov 21, 2014 at 13:44

I would like to share a function which might be useful to compute the probability you want. I found this codes from the following link. With a little modification, I wrote the following algorithm:

genUnProb<-function(ph, k) {
  prob <- setNames(Reduce(function(x,y) 
        convolve(x, rev(y), type="open"),
        Map(c,1,ph)), 0:length(ph))

It is written in R. Let's have a try on your problem above:

p = c(0.5,0.3,0.15,0.05)
genUnProb(p, 3)
## 3 
## 0.036 
genUnProb(p, 0:4)
## 0        1        2        3        4 
## 1.000000 1.000000 0.317500 0.036000 0.001125 

Unsurprisingly, you get all the polynomial coefficients derived above. Hopefully, this helps you with the coding you're seeking for.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .