Calculating the probability of combinations with unequal probabilities for each element 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?
Example:
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:
$p_1p_2p_3=0.0225$
$p_1p_2p_4=0.0075$
$p_1p_3p_4=0.00375$
$p_2p_3p_4=0.00225$
I'm looking for an efficient way to calculate this result, without having to iterate over ${n \choose k}$ formulas.
 A: 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$$
A: 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))
  return(prob[k+1])
}

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.
