Probability Calculation

1. Sep 15, 2010

davee123

Suppose I have an infinite mix of marbles, each of which can be one of 16 colors. You pick 16 marbles at random. How do you calculate the probability of receiving, say, 12 different colors within the 16 you picked?

The probability of getting 1 color is pretty easy: 16/16^16

And the probability of getting all 16 colors is also easy: 16!/16^16

But the probability of getting something in the middle, I'm fuzzy on how to calculate. I wrote a script to test, so I know the rough probability of getting 12 colors is 13.04%, but I can't quite wrap my brain around how to calculate the more accurate probability, if (say) the number of picks changed, or if the number of colors changed.

DaveE

2. Sep 15, 2010

awkward

Hi DaveE,

I get a probability of 0.13029987, which is pretty close to your value of 0.1304.

You can possibly draw any of 16^16 sequences of colors, each of which we assume is equally likely.

There are $$\binom{16}{12}$$ ways to select 12 colors out of the 16.

Let's say there are n ways of ordering 16 colors, 12 of which are distinct; then the probability we seek is
$$p = \frac{\binom{16}{12} n}{16^{16}}$$

It remains only to find n. I used an exponential generating function for this, but there are sure to be other ways. Let's say $$a_r$$ is the number of ways to order a selection of r colors drawn from a pallet of 12. Let
$$f(x) = \sum_{r=0}^{\infty} \frac{1}{r!} a_r x^r$$
Then (it's easy when you know how!) we see
$$f(x) = (x + (1/2) x^2 + (1/3!) x^3 + \dots)^{12}$$
$$= (e^x -1)^{12}$$
$$= \sum_{i=0}^{12} (-1)^i \binom{12}{i} e^{ix}$$

From this we can see that
$$n = a_{16} = -\binom{12}{1} + \binom{12}{2} 2^{16} - \binom{12}{3} 3^{16} + \dots + \binom{12}{12} 12^{16}$$
which is approximately 1.3206639 x 10^15. Substituting this value for n in the equation for p above, we find p is approximately 0.13029987, as claimed.