<p>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).</p>

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

<p>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. </p>

<p>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. </p>

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

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

<p>which is straightforward to evaluate and generalises nicely. </p>

CC BY-SA 3.0
2011-11-26T13:43:05.403Z
This is a nice solution, but what to extent can you prove it is correct (or correct in the limit)?
David Harris
CC BY-SA 3.0
2011-11-26T15:58:03.097Z
@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
CC BY-SA 3.0
2011-11-27T01:34:26.787Z
The answer you are going to get with this looks a lot like the inclusion-exclusion formula.
Peter Shor 
CC BY-SA 4.0
2023-04-03T17:56:13.890Z
Can someone explain "So, integrating over the time of the first event in the green process, you get the following expression for your probability" a bit? Thank you!
1a1a11a
CC BY-SA 3.0
2011-11-26T10:48:48.573Z
2011-11-26T11:04:30.897Z
2011-11-26T11:04:30.897Z
James Martin
<p>This is an addendum to James Martin's brilliant answer.  To integrate the expression</p>

<p>$\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$,</p>

<p>I ran it through Mathematica and got</p>

<p>$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]$.</p>

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

CC BY-SA 3.0
2011-11-27T13:36:10.533Z
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 
CC BY-SA 3.0
2011-11-27T12:13:05.023Z
2011-11-27T12:13:05.023Z
Jonathan Shewchuk
<p>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 <a href="http://www.icmexplorer.com" rel="nofollow">http://www.icmexplorer.com</a>; 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. </p>

<p>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.</p>

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

<p>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. </p>

<p>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\%.$</p>

CC BY-SA 3.0
2014-08-06T18:40:07.230Z
2014-08-06T18:40:07.230Z
Douglas Zare
<p>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?</p>

<p>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$?</p>

<p>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.</p>

<p>We seek this bound to help us analyze a randomized geometric algorithm.</p>

CC BY-SA 3.0
2011-11-25T22:17:48.733Z
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
CC BY-SA 3.0
2011-11-26T02:06:09.943Z
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 
CC BY-SA 3.0
2011-11-26T10:17:11.523Z
@Jonathan Shewchuk, thanks for the clarification.
Kaveh
CC BY-SA 3.0
2011-11-26T10:25:53.143Z
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
CC BY-SA 3.0
2011-11-26T10:26:19.353Z
p.s I assume you've read Schelling ? (coupon collecting with unequal probabilities) ?
Suresh Venkat
CC BY-SA 3.0
2011-11-26T20:09:37.693Z
@Suresh and Peter. Thanks! I'll try that line of reasoning and see where it leads me. I have not read Schelling, but I just pulled it up and will do so shortly. This is my first year of grad school so I haven't quite gotten to all of the seminal papers yet.
Brielin Brown
CC BY-SA 3.0
2014-08-07T03:01:56.123Z
If the number of colors is a small constant, then it is easy enough to build the state space, and compute the probabilities explicitly. If you have n balls, and c colors, the space complexity is roughly $n^c$. You could easily write a program to compute these if you had to... So, what is $n$ and what is $c$ for you?
Sariel Har-Peled
<co.combinatorics><pr.probability>
Order of drawing colored balls from a bag
Brielin Brown
# Order of drawing colored balls from a bag

(Asked by: username_0 on 2011-11-25)

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

username_2points 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.

**Tags:** co.combinatorics, pr.probability

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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  
> **username_3**: @username_9, thanks for the clarification.  
> **username_4**: 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.  
> **username_4**: p.s I assume you've read Schelling ? (coupon collecting with unequal probabilities) ?  
> **username_0**: @Suresh and Peter. Thanks! I'll try that line of reasoning and see where it leads me. I have not read Schelling, but I just pulled it up and will do so shortly. This is my first year of grad school so I haven't quite gotten to all of the seminal papers yet.  
> **username_5**: If the number of colors is a small constant, then it is easy enough to build the state space, and compute the probabilities explicitly. If you have n balls, and c colors, the space complexity is roughly $n^c$. You could easily write a program to compute these if you had to... So, what is $n$ and what is $c$ for you?  

---

## 3 answers

### Answer by username_6 on 2011-11-26. Score: 15

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.

> **Comments:**
> **username_7**: This is a nice solution, but what to extent can you prove it is correct (or correct in the limit)?  
> **username_6**: @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).  
> **username_2**: The answer you are going to get with this looks a lot like the inclusion-exclusion formula.  
> **username_8**: Can someone explain "So, integrating over the time of the first event in the green process, you get the following expression for your probability" a bit? Thank you!  

---

### Answer by username_9 on 2011-11-27. Score: 7

This is an addendum to username_6'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.

> **Comments:**
> **username_2**: 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)$.  

---

### Answer by username_10 on 2014-08-06. Score: 3

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 username_6'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. username_9's calculation is also what you get from one approach to dynamic programming. As username_2observed, 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\%.$


---

