# Multinomial Distribution -- How to calculate percentiles?

I've read the rules and searched but I do not even know what I'm looking for. Here is my problem:

Suppose I have a bag containing three different marbles: red, green, and blue. I am drawing a single marble from the bag each time with replacement. I would like to know how many times, on average, do I need to draw marbles from the bag until I have drawn $$25$$ of each type of marble. I would like to plot this distribution and be able to calculate percentiles on this distribution.

After some research I think this is a multinomial distribution. I can calculate the probability that I have exactly $$25$$ of each marble after $$75$$ draws by the following:

$$\frac{75!}{25!\times25!\times25!}\times\left(\frac13\right)^{25}\times \left(\frac13\right)^{25} \times\left(\frac13\right)^{25}$$

which works out to about $$1.06\%$$. However, I don't know how to proceed with turning this into a distribution so I can calculate percentiles. Please advise on how to proceed.

• You can format math here using MathJax. Commented Feb 19, 2020 at 15:08

Based on your example, I am assuming that you have equal numbers of each marble.

Let $$R,G,B$$ be random variables representing the number of red, green, or blue marbles respectively that have been drawn. It sounds like you are looking for

$$P(R=r,G=g,B=b) = \dfrac{(r+g+b)!}{r!g!b!}\left(\dfrac{1}{3}\right)^{r+g+b}$$

Now, you can plot this as you vary $$r,g,b$$.

As for how many draws do you need on average to draw 25 of each, this is a modified coupon collector's problem. By linearity of expectation, drawing 25 of a single color marble will require $$\dfrac{25}{\tfrac{1}{3}} = 75$$ pulls of a marble. And drawing 25 of each would require $$75+75+75 = 225$$ draws on average.

Edit: this coupon collector solution does not work, unfortunately. The chances of getting multiples of the same thing are different from getting one of each of different things. I should have realized that. Through simulation, I am getting much smaller numbers. Like around $$87.7$$.

This gives a much closer estimate than my ill-conceived use of the Coupon Collector's Problem:

$$3\sum_{a=25}^{75}\sum_{b=25}^{75}(25+a+b)\dfrac{(24+a+b)!}{24!a!b!}\cdot \dfrac{1}{3^{25+a+b}} \approx 87.9057$$

Now, technically, I am undercounting, as $$a,b$$ should go to infinity, but I am also overcounting by multiplying by 3, as I am counting when $$a=b=25$$ three times, even though it should only be counted once. So, this is an estimate of the expected value.

• Yes, I should have been more clear. I have one of each marble. I want to know how many draws on average it would take to end up with /at least/ 25 of each color... which I think you answered in the last sentence. Commented Feb 18, 2020 at 23:50
• @DariusHaskell I was incorrect about being able to use the Coupon Collector's Problem as the solution. It does not apply. Commented Feb 19, 2020 at 14:06
• Thank you, can you post the code you used to run the simulation? Commented Feb 20, 2020 at 1:04
• I actually used Excel. In cell $A1$, I put $$\text{=RANDBETWEEN(1,3)}$$ and copied that down for $400$ columns and $1000$ rows. This gives me $1000$ trials per go. (So, the same formula in every cell of $A1:OJ1000$. Then, in cell $A1001$, I put the formula: $$\text{=IF(AND(COUNTIF(}\\text{A1:A1,1)>=25,COUNTIF(}\\text{A1:A1,2)>=25,COUNTIF(}\\text{A1:A1,3)>=25),COLUMN(),"")}$$. I copied that from $A1001:OJ2000$. Then in cell $OK1001$, I used the formula $$\text{=MIN(A1001:OJ1001)}$$ and copied that down. Then take the average of $OK:OK$. Commented Feb 20, 2020 at 13:49

Let $$E(r,g,b)$$ be the expected number of draws to obtain at least $$r$$ red, $$b$$ blue, and $$g$$ green marbles. Then $$E(0,0,0)=0$$ and otherwise $$E(r,g,b)= 1+\frac{1}{3}\left[E(\max(r-1,0),g,b)+E(r,\max(g-1,0),b)+E(r,g,\max(b-1,0))\right].$$ Solving this recursion yields $$E(25,25,25)\approx 87.9057937186312$$, in close agreement with @InterstellarProbe's second estimate. A plot of $$E(n,n,n)$$ for $$n=1$$ to $$50$$ is nearly linear:

The Wikipedia article for the Coupon collector's problem gives a reference to Newman and Shepp (1960) for this generalization, and the exact value is $$E(25,25,25)=3 \int_{0}^\infty \left[1-\left(1-e^{-t}\sum_{k=0}^{25-1} \frac{t^k}{k!}\right)^3\right] \mathrm{d}t.$$