Seven sportsmen (named A,B,C,D,E,F and G) buy 7 hats choosing randomly out of 4 available colors (say G,R,W and Y).
What is the probability that all the colors were chosen?

Using "&" to represent "and", and "|" to represent "or":

The inclusion/exclusion principle gives us:

p(g & r & w & y) = p(g)+p(r)+p(w)+p(y)
                  - p(g|r) - p(g|w) - p(g|y)
                  - p(r|w) - p(r|y) - p(w|y)
                  + p(g|r|w) + p(g|r|y) + p(g|w|y) + p(r|w|y)
                  - p(g|r|w|y)

                 
Now p(g), or any of the single color probabilities (that is the probability that a given color shows up among the sportsmen, not necessarily exclusively), is 1 - (3/4)^7.

The probability that a given pair of colors will have at least one representation among the sportsmen, such as p(g|r), is 1 - (1/2)^7.

And the probability of one of the triples is 1 - (1/4)^7.

And of course p(g|r|w|y) = 1, as one of these colors must be represented at least once among the sportsmen.

So the probability that all four colors will be represented is:

4 * (1 - (3/4)^7) - 6 * (1 - (1/2)^7) + 4 * (1 - (1/4)^7) - 1

which is equal to 525/1024, or about 0.5126953125.

Simulation verification:

FOR tr = 1 TO 1000000
 REDIM used(3)
 FOR spm = 1 TO 7
   choice = INT(RND(1) * 4)
   used(choice) = 1
 NEXT
 good = 1
 FOR i = 0 TO 3
   IF used(i) = 0 THEN good = 0
 NEXT
 IF good THEN hits = hits + 1
 PRINT tr, hits / tr, 1024 * hits / tr
NEXT

finds as its last line:

1000000       .512473       524.7723

meaning that after a million trials, the fraction of successes is .512473, or, relative to a denominator of 1024: 524.7723/1024.

Posted by Charlie on 2010-04-26 13:50:11