CMIMC 2016 Math Contest Question

Shen, Ling, and Ru each place four slips of paper with their name on it into a bucket.
They then play the following game:
Slips are removed one at a time from the bucket, and whoever has all of their slips removed first wins.
Shen cheats, however, and adds an extra slip of paper into the bucket, and will win when four (out of five) of his are drawn.
Compute the probability that Shen wins by cheating.

The solution is given in this link : https://cmimc.math.cmu.edu/math/past-problems/2016
I would like to challenge that answer with my approach. Let me know where I am making a mistake.

I would like to invoke negative multinomial distribution to solve this

$P(X = x_o) =\gamma{(n)}\frac{p_0^{x_0}}{\gamma{(x_0)}}$$\prod{\frac{p_i^{x_i}}{x_i!}}$

$P_0 = \frac{5}{13}$ $P_1 = \frac{4}{13}$, $P_2 = \frac{4}{13}$

$x_0$ = Shen's number of slips, $x_1$ = Ling's number of slips and $x_2$ = Ru's number of slips.

enter image description here

According to the Solution posted, answer is $\frac{67}{117} = 0.57265$

Let me know where I am going wrong.


1 Answer 1


The negative multinomial distribution would be appropriate in a sequence of draws with replacement, where each slip of paper says "Shen" on it with probability $\frac{5}{13}$, "Ru" with probability $\frac{4}{13}$, and "Ling" with probability $\frac{4}{13}$.

This is not the problem in question. We are drawing without replacement: if the first slip of paper drawn says "Ru", then the probabilities for the second draw become $\frac{5}{12}$, $\frac3{12}$, and $\frac{4}{12}$ respectively.

I don't think there's a standard term for this kind of distribution. The negative hypergeometric distribution is the corresponding equivalent of the negative binomial distribution (it's what we'd use if only Shen and Ru were playing). The most natural name for what's happening here is the "negative multihypergeometric distribution", which is a monstrosity.

Let's compute the probability mass function for this distribution: the function $p(x,y)$ that gives the probability that, by the time Shen draws $4$ slips, Ru has drawn $x$ slips and Ling has drawn $y$ slips.

  • In this event, we have drawn a total of $x+y+4$ slips, and the last slip is one of Shen's.
  • There are $\binom{x+y+3}{x,y,3} = \frac{(x+y+3)!}{x!\, y!\, 3!}$ ways to choose the owners of the first $x+y+3$ slips. (This factor is identical to what we see for the negative multinomial distribution.)
  • Let $n^{\underline r}$ denote the falling product $n(n-1)(\cdots)(n-r+1) = \frac{n!}{(n-r)!}$. Then there are $5^{\underline 4} \cdot 4^{\underline x} \cdot 4^{\underline y}$ ways to choose the specific slips that we draw to match what we want, and $13^{\underline{x+y+4}}$ total ways to choose $x+y+4$ slips.

So we get $$ p(x,y) = \frac{(x+y+3)!}{x!\,y!\,3!} \cdot \frac{5^{\underline 4} \cdot 4^{\underline x} \cdot 4^{\underline y}}{13^{\underline{x+y+4}}}. $$ (Compare this to the expression $\frac{(x+y+3)!}{x!\,y!\,3!} \cdot \frac{5^4 \cdot 4^x \cdot 4^y}{13^{x+y+4}}$ that we'd get from the negative multinomial distribution. The only difference really is that we replace powers with falling powers.)

If we now solve the problem the brute-force way and take $$\sum_{x=0}^3 \sum_{y=0}^3 p(x,y),$$ we get the probability $\frac{67}{117}$ that Shen wins.

  • $\begingroup$ Shoot!!, I forgot about property of replacement. Thanks for deriving the pmf. really appreciate $\endgroup$ Nov 11, 2023 at 7:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .