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.