Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's say you have an urn full of balls. Each ball has one or more colors on it. I'm trying to figure out, given that you draw E balls from an urn without replacement, what is the probability that you will remove all of the balls of one or more colors? I think I have it solved for 2 colors, but beyond that, double-counting becomes problematic, and I'm at a bit of a loss as to the proper way to incorporate it.

I've started by thinking about this problem with two colors, red and green, and no mixed color balls. What is the probability of removing all of the red balls, R, given E draws? Well, we can get that from the density function of the hypergeometric function. For shorthand, dh(a,b,c,d) is the probability of drawing a balls of a color with b balls of that color in the urn, c balls not of that color, and d draws.

The probability of drawing out all of the red balls is dh(R, R, G, E). The probability of drawing out all of the green balls is dh(G,G,R,E). The probability of drawing out all of either the red OR the green (since we can't do both with 2 colors) is dh(R, R, G, E)+dh(G,G,R,E).

Great. This leads to an easy general expression for single color balls. Let's sum over all colors, with i being the number of balls with color i. T is the total number of balls.

p(removing all of 1 or more) = sum(dh(i, i, T-i, E))

Now let's say there are M mixed balls - both red and green. Let's go back to the probability of drawing out all balls with red on it.

Here, we have dh(R+M, R+M, G, E). And we can just flip the Rs and Gs to get the same expression for G.

Can we just sum these two to get the answer to the probability of drawing out all balls with either red or green on them? Do we need to worry about double-counting? Not usually in the case of two colors only. One can only draw out either all of the red or all of the green balls, unless you are removing all of the balls. In which case double counting does become a problem.

How can I derive a general term that corrects for double counting with C number of colors, mixtures having any number of colors on them from 2...C, and E draws. I'm guessing that the 1 color per ball case is a special case. I'm just not seeing the correction term. Thoughts? Just pointers in the right direction would be appreciated.

share|improve this question
    
out of curiosity, how/why did you think of think of this problem? –  picakhu Nov 29 '11 at 22:11
    
I'm actually thinking about bipartite directed graphs composed of out-nodes and in-nodes only. If you delete E number of out-nodes, what's the probability that one or more in-nodes will have lost all of its connections? I realized I could boil this down to a ball-and-urn problem with multicolored balls. Each ball is an out-node and each color is an in-node. –  jebyrnes Nov 29 '11 at 23:04
1  
Note that the probability of getting all the balls of at least one colour with $E$ draws from $N$ balls is $1-$ the probability of getting at least one ball of each colour with $N-E$ draws from the same $N$ balls. –  Henry Nov 29 '11 at 23:15
    
Henry, this sounds like it could be the answer - could you elaborate? I initially started thinking along these lines - namely, that this problem is the same as looking at the probability of 1-no balls of a color left summed over all colors. But that doesn't seem to be it. –  jebyrnes Nov 29 '11 at 23:34
    
For example, consider 3 balls and three colors. One ball is red, one is white, and one is red/white/black. 2 are drawn. So, I thought, of the remaining, what's the probability that there is one or more of each color? This is 1-(p(no white)+p(no red)+p(no black)). –  jebyrnes Nov 30 '11 at 4:42
show 1 more comment

2 Answers 2

up vote 1 down vote accepted

Suppose you have $B$ balls in $C$ colours, with $b_j$ balls of colour $j$, and draw $E$ balls. For any subset $S$ of $\{1,2,\ldots, C\}$, let $b_S = \sum_{j \in S} b_j$. The probability $P(S)$ that you get all the balls of all the colours in $S$ is $0$ if $E < b_S$ and ${{B-b_S} \choose {E-b_S}}/{B \choose E}$ if $E \ge b_S$. By the inclusion-exclusion principle, the probability that you get all the balls of at least one colour is $ \sum_S (-1)^{|S|-1} P(S)$, where the sum is over all nonempty subsets $S$ of $\{1,2,\ldots, C\}$ with $b_S \le E$.

share|improve this answer
    
Is n=E in the above? |S| is the size of the set. –  jebyrnes Nov 30 '11 at 2:22
    
Yes (edited to fix it). –  Robert Israel Nov 30 '11 at 7:49
    
Either I've misunderstood your answer or have not made the problem clear. Consider 3 balls. 1 red, 1 green, 1 red/green/blue. Let's say E=2. The probability of removing all of the balls of one or more colors is 2/3 (i.e., the probability of not removing the mixed ball) Using your method the sets for 1 color the probabilities are {red} P(S) = 1/3 from ${{3-2} \choose {2-2}}/{3 \choose 2}$, {green} P(S) = 1/3 (same), {blue} P(S) = 2/3 from ${{3-1} \choose {2-1}}/{3 \choose 2}$. All 2 or 3 color sets have a probability of 0, as E<bs. This adds up to $1\frac{1}{3}$ which is not possible. –  jebyrnes Nov 30 '11 at 15:46
    
Ah - although if $\sum_{j \in S} b_j$ means the total number of balls in $b_s$ rather than totaling over all colors, then this works. See my answer below as well. Now the trick is to find a way to get at this algorithmically without having to go through every single possible set, which I feel like I should be able to do if I know the number of mixed balls of each kind, number of colors, and number of balls. Hrm... –  jebyrnes Dec 2 '11 at 18:51
add comment

Thanks for the leads. I have an answer, but am unsatisfied with it from a computational perspective. First, the answer, then the ongoing quandary. So, assume you have B balls in an urn. There are C possible colors. For any subset of the colors, there is a set of balls that contains those colors - both of single and mixed color. Let's say that any subset of some j colors, $S \subset \{1\ldots C\}, j=\left | S \right |$, can be called $S_i|j$. For any value of j, there are t=$\binom{C}{j}$ combinations. So, using that information and the inclusion/exclusion principle...

$\sum_{j=1}^{C}-1^{(j-1)}\sum_{S_0 |j}^{S_t|j}dh(|S|, |S|, B-|S|, E) $

This is great. But, here's the problem. Computationally, it's a bear, as for even moderately large numbers of colors, it becomes slow to calculate. Indeed, one is often just better at iterating through all of the combinations of balls.

Compare the following R code which works with matrices where columns are colors and rows are balls

anyGone<-function(amat, E){
 totals<-colSums(amat) 
 #combn doesn't play well with E=1
 if(E==1) return( mean(colSums(apply(amat, 1, function(x) x==totals))>0) )    
 mean(combn(1:nrow(amat), E, function(rows) sum(totals==colSums(amat[rows,])))>0)

}

to this function, which takes the same matrix.

anyGone3<-function(amat, E){  
  eachColor<-colSums(amat)
  ret<-sum(dhyper(eachColor, eachColor, nrow(amat)-eachColor, E))

  if(E>1){for (j in 2:ncol(amat)){
    values<-combn(1:ncol(amat), j, function(x) sum(rowSums(amat[,x])>0))
    ret<- ret+(-1)^(j-1)*sum(dhyper(values, values, nrow(amat)-values, E))
  }}

  ret
}

For a simple matrix with 15 colors, 15 balls, and 8 draws, the difference in performance is noticeable.

So......I guess the followup question is more algorithmic. Knowing the number of types of mixed balls, the number of colors, and the total number of balls, is there some way to shave off a large amount of time from this calculation.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.