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.

  • $\begingroup$ 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. $\endgroup$
    – user834
    Nov 25 '11 at 22:17
  • 1
    $\begingroup$ 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 $\endgroup$ Nov 26 '11 at 2:06
  • $\begingroup$ @Jonathan Shewchuk, thanks for the clarification. $\endgroup$
    – Kaveh
    Nov 26 '11 at 10:17
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 26 '11 at 10:25
  • 1
    $\begingroup$ p.s I assume you've read Schelling ? (coupon collecting with unequal probabilities) ? $\endgroup$ Nov 26 '11 at 10:26

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.

  • $\begingroup$ This is a nice solution, but what to extent can you prove it is correct (or correct in the limit)? $\endgroup$ Nov 26 '11 at 13:43
  • $\begingroup$ @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). $\endgroup$ Nov 26 '11 at 15:58
  • 2
    $\begingroup$ The answer you are going to get with this looks a lot like the inclusion-exclusion formula. $\endgroup$ 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.

  • 4
    $\begingroup$ 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)$. $\endgroup$ Nov 27 '11 at 13:36

This model is used in the analysis of poker tournaments, where it is called the Independent Chip Model (ICM). When there are prizes for finishing second or lower, you have to estimate your equity from lower prizes, and these are quite significant at the final table or in single table tournaments. They can greatly distort the proper strategy, and professional single table tournament players study the amount of rational risk aversion according to the ICM. You can download my program for computing quantities related to the ICM equities from http://www.icmexplorer.com; the free version probably does all you want and more. If you enter the stacks and press the ICM button, you see the probability distribution for the caller according to the ICM.

One way to describe the ICM is that you remove the chips from the table one by one, and players are knocked out when their last chip is eliminated. Another way to describe the ICM is that players finish first in proportion with their stacks, and then the winner's chips are removed. Then the second place finisher is determined in proportion with the remaining stacks, etc. It isn't obvious that these are the same, since the former description seems to require an integral chip count and isn't obviously scale-invariant. To see that these are the same, shuffle the chips together and rank players by their highest chips. If you reveal the chips from the bottom, you get the first description. If you reveal the chips from the top, you get the second description.

If you rescale the stacks and use the second description, you get something close to James Martin's continuous version.

There doesn't seem to be a very easy way to compute the probabilities, but there are a lot of improvements possible on the most naive approaches in case you need to calculate probabilities with more than 5 stacks. Jonathan Shewchuk's calculation is also what you get from one approach to dynamic programming. As Peter Shor observed, if there is some repetition in stack sizes, there are simplifications possible.

Anyway, for the first problem, there are two possibilities, red-yellow and yellow-red before green, ignoring white. These have probabilities $\frac{18}{32}\times\frac{12}{14}$ and $\frac{12}{32}\times \frac{18}{20}$, for a total of $\frac{459}{560} = 81.96\%.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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