2
$\begingroup$

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.

$\endgroup$
1
  • $\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

2
$\begingroup$

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

$\endgroup$
2
  • $\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
0
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

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