Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

We're looking for an upper bound on (or a method to compute) probabilities of the following type: Suppose I put 12 yellow balls, 18 red balls, 7 white balls, and 2 green balls in a bag. Then I start withdrawing random balls one by one. What is the probability that I draw at least one red ball and at least one yellow ball before I draw the first green ball?

More generally, I have a set $A$ of $m$ colors, a set $B \subset A$ of colors, a color $c \in A \setminus B$ and a set of $n$ balls with colors from $A$ where the number of balls of each color is known. Whats the probability that I draw at least one ball of each color in $B$ before I draw a ball of color $c$?

Peter Shor points out that this is related to the coupon collector's problem (thanks!), the main difference being that we want to know the probability of a particular color being last (not the number of steps required to collect every coupon). The literature we've searched on the coupon collector's problem (in the last few hours) doesn't seem to address this question. (A minor difference is that we're sampling without replacement, though a solution for sampling with replacement would be welcome too.) Ideally we'd like a closed-form upper bound (an asymptotic upper bound would probably do), but a polynomial-time algorithm to compute an upper bound would be useful too.

We seek this bound to help us analyze a randomized geometric algorithm.

share|improve this question
    
It seems like one could employ a dynamic programming solution in $O(C^B N)$ (where $C$ is the maximum number of colored balls in a single bin, $B$ is the number of bins and $N$ is the number of draws), but this is not very efficient. –  user834 Nov 25 '11 at 22:17
1  
The white balls are completely irrelevant. Otherwise, it is some kind of twist on a coupon-collector's problem, and these problems generally aren't that easy. There's a substantial literature on them, though. I expect you might have better luck finding a solution if you asked this question on math.stackexchange.com –  Peter Shor Nov 26 '11 at 2:06
    
@Jonathan Shewchuk, thanks for the clarification. –  Kaveh Nov 26 '11 at 10:17
1  
A non-rigorous argument that you might be able to develop is that the coupon collector bounds are quite sharply concentrated. In effect, you have two processes (one that samples from B and the other from A) and you're asking for the probability that the B process completes before an A event occurs. By treating the coupon collector component (the B process) as "deterministic" you'd get a crude bound. –  Suresh Venkat Nov 26 '11 at 10:25
1  
p.s I assume you've read Schelling ? (coupon collecting with unequal probabilities) ? –  Suresh Venkat Nov 26 '11 at 10:26

2 Answers 2

First observation: the cases with and without replacement have exactly the same answer. (Once you have drawn a red ball, say, you don't care about future draws of red balls: all you care about now is the relative order of future green and yellow balls).

A good way to attack the case with replacement is by embedding in continuous time.

Imagine that the balls arrive according to independent Poisson processes with appropriate rates: rate 12 for yellow balls, rate 18 for red balls, rate 2 for green balls. Then whenever a ball arrives, it has probability 12/32 of being yellow, 18/32 of being red and 2/32 of being green, as desired - I'm ignoring the white balls since they're irrevelant. So the sequence of colours observed is exactly as it would be from a sequence of independent draws with replacement.

Now you want to know the following: does the first event in the green process occur after the first events in the yellow and red processes? This is easy enough to calculate, since the first event in a Poisson process of rate $r$ has exponential distribution with rate $r$, and the three processes are independent.

So, integrating over the time of the first event in the green process, you get the following expression for your probability:

$\int_0^\infty 2e^{-2x} (1-e^{-12x})(1-e^{-18x})dx$

which is straightforward to evaluate and generalises nicely.

share|improve this answer
    
This is a nice solution, but what to extent can you prove it is correct (or correct in the limit)? –  David Harris Nov 26 '11 at 13:43
    
@David: the answer is exact. Which part worries you? The sequence of colours seen in the continuous time process has precisely the same distribution as the sequence of colours drawn by sampling with replacement (by the memoryless property for Poisson processes). –  James Martin Nov 26 '11 at 15:58
    
Thanks, James! That should help a lot. –  Brielin Brown Nov 26 '11 at 20:07
1  
The answer you are going to get with this looks a lot like the inclusion-exclusion formula. –  Peter Shor Nov 27 '11 at 1:34

This is an addendum to James Martin's brilliant answer. To integrate the expression

$\int_0^\infty a e^{-a t} \left(1-e^{-b t}\right) \left(1-e^{-c t}\right) \left(1-e^{-d t}\right) \left(1-e^{-e t}\right) \left(1-e^{-f t}\right) \, dt$,

I ran it through Mathematica and got

$a \left[ \frac{1}{a}-\frac{1}{a+b}-\frac{1}{a+c}+\frac{1}{a+b+c}-\frac{1}{a+d}+\frac{1}{a+b+d}+\frac{1}{a+c+d}-\frac{1}{a+b+c+d}- \right.$ $\left. \frac{1}{a+e}+\frac{1}{a+b+e}+\frac{1}{a+c+e}-\frac{1}{a+b+c+e}+\frac{1}{a+d+e}-\frac{1}{a+b+d+e}-\frac{1}{a+c+d+e}+ \right.$ $\left. \frac{1}{a+b+c+d+e}-\frac{1}{a+f}+\frac{1}{a+b+f}+\frac{1}{a+c+f}-\frac{1}{a+b+c+f}+\frac{1}{a+d+f}-\frac{1}{a+b+d+f}- \right.$ $\left. \frac{1}{a+c+d+f}+\frac{1}{a+b+c+d+f}+\frac{1}{a+e+f}-\frac{1}{a+b+e+f}-\frac{1}{a+c+e+f}+\frac{1}{a+b+c+e+f}- \right.$ $\left. \frac{1}{a+d+e+f}+\frac{1}{a+b+d+e+f}+\frac{1}{a+c+d+e+f}-\frac{1}{a+b+c+d+e+f} \right]$.

I think the pattern is fairly clear. Many thanks to Prof. Martin, and also to Suresh and Peter.

share|improve this answer
3  
And if you set $b=c=d=e=f$ in the formula above and simplify it, then, assuming there are $k$ colors in the set $B$, you get $k!\,b^k/(a+b)(a+2b)(a+3b)\ldots(a+kb)$. –  Peter Shor Nov 27 '11 at 13:36

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.