All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Every Die Face (Posted on 2013-07-12)
You roll a k-sided die n times. What is the probability that each of the k faces appeared at least once?

 No Solution Yet Submitted by Danish Ahmed Khan No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution Comment 1 of 1

If p(n) represents the probability of having chosen face n at least once, then by the inclusion/exclusion principle the probability of completing all of the faces is given by:

P = p(1)+p(2)+...+p(k) - p(1 or 2) - p(1 or 3) - ... - p((k-1) or k)
+ p(1 or 2 or 3) + ... + p((k-2) or (k-1) or k)
...
+/- p(1 or 2 or ... or k)

where the final +/- depends on the mod 2 parity of k.

All single-number probabilities are the same as are all double-number probabilities etc., so that for example, p(1)+p(2)+...+p(k) = k*p(1) = 1 - ((k-1)/k)^n.

The probability of getting at least one occurrence from a set of i faces is 1 minus the probability of getting none of them, or 1 - ((k-i)/k)^n.

The formula is formalized as:

Sigma{i=1 to k}(C(k,i)*(1 - ((k-i)/k)^n)) * (-1)^(i+1))

`   \ k: n    2       3       4       5       6       7       8       9      10 2 0.50000 0.00000 0.00000 0.00000-0.00000-0.00000 0.00000-0.00000-0.00000 3 0.75000 0.22222 0.00000 0.00000-0.00000-0.00000 0.00000-0.00000-0.00000 4 0.87500 0.44444 0.09375 0.00000-0.00000-0.00000 0.00000-0.00000-0.00000 5 0.93750 0.61728 0.23438 0.03840-0.00000 0.00000 0.00000 0.00000-0.00000 6 0.96875 0.74074 0.38086 0.11520 0.01543-0.00000 0.00000-0.00000-0.00000 7 0.98438 0.82579 0.51270 0.21504 0.05401 0.00612 0.00000-0.00000-0.00000 8 0.99219 0.88340 0.62292 0.32256 0.11403 0.02448 0.00240 0.00000-0.00000 9 0.99609 0.92212 0.71136 0.42707 0.18904 0.05770 0.01081 0.00094-0.0000010 0.99805 0.94803 0.78060 0.52255 0.27181 0.10491 0.02816 0.00468 0.0003611 0.99902 0.96533 0.83399 0.60636 0.35621 0.16310 0.05576 0.01336 0.0020012 0.99951 0.97688 0.87476 0.67800 0.43782 0.22845 0.09331 0.02862 0.0061913 0.99976 0.98459 0.90570 0.73812 0.51386 0.29731 0.13932 0.05132 0.0142714 0.99988 0.98972 0.92909 0.78791 0.58285 0.36657 0.19172 0.08146 0.0273215 0.99994 0.99315 0.94673 0.82877 0.64421 0.43392 0.24825 0.11831 0.0459516 0.99997 0.99543 0.96000 0.86208 0.69800 0.49772 0.30680 0.16074 0.0703117 0.99998 0.99696 0.96998 0.88910 0.74463 0.55697 0.36556 0.20734 0.1000918 0.99999 0.99797 0.97747 0.91094 0.78471 0.61115 0.42310 0.25670 0.1346719 1.00000 0.99865 0.98310 0.92855 0.81892 0.66009 0.47835 0.30748 0.1732020 1.00000 0.99910 0.98732 0.94272 0.84799 0.70387 0.53056 0.35851 0.2147421 1.00000 0.99940 0.99049 0.95410 0.87258 0.74273 0.57927 0.40882 0.2583222 1.00000 0.99960 0.99287 0.96324 0.89332 0.77700 0.62425 0.45765 0.3030623 1.00000 0.99973 0.99465 0.97056 0.91076 0.80707 0.66542 0.50443 0.3481324 1.00000 0.99982 0.99599 0.97644 0.92542 0.83335 0.70284 0.54875 0.3928325 1.00000 0.99988 0.99699 0.98114 0.93770 0.85624 0.73665 0.59036 0.4366026 1.00000 0.99992 0.99774 0.98491 0.94798 0.87612 0.76704 0.62912 0.4789927 1.00000 0.99995 0.99831 0.98792 0.95659 0.89334 0.79426 0.66500 0.5196328 1.00000 0.99996 0.99873 0.99033 0.96378 0.90824 0.81854 0.69803 0.5583029 1.00000 0.99998 0.99905 0.99227 0.96979 0.92111 0.84013 0.72828 0.5948330 1.00000 0.99998 0.99929 0.99381 0.97480 0.93221 0.85930 0.75588 0.62914`

The above table includes k=2 for including a coin as a 2-sided die and 3 for a 3-sided pencil used as a die, and is from:

5   for K=2 to 10:print using(8,0),K;:next:print
10   for N=2 to 30
15      print using(3,0),N;
20      for K=2 to 10
30       Sum=0
40       for I=1 to K
50          Sum=Sum+combi(K,I)*(1-((K-I)/K)^N)*(-1)^(I+1)
60       next I
70       print using(2,5),Sum;
80      next:print
100   next:print

As a check, I'll simulate a 6-faced die rolled 12 times, with a million trials.

DEFDBL A-Z
n = 12: k = 6
FOR tr = 1 TO 1000000
REDIM used(k)
FOR roll = 1 TO n
r = INT(RND(1) * k + 1)
IF used(r) = 0 THEN used(0) = used(0) + 1
used(r) = 1
NEXT roll
IF used(0) = k THEN success = success + 1
PRINT USING "######## ##.#####"; tr; success / tr
NEXT tr

with the last line showing the success rate after 1,000,000 trials:

1000000  0.43745

agreeing statistically with the calculated 0.43782.

For the familiar 6-sided die, the probabilities as rational numbers are:

5       0   =  0
6       5/324   ~=     0.0154320987654320987
7       35/648   ~=    0.0540123456790123456
8       665/5832  ~=   0.1140260631001371742
9       245/1296   ~=  0.1890432098765432098
10      38045/139968 ~= 0.2718121284865112025
11      99715/279936 ~= 0.3562064186099679926
12      1654565/3779136   ~=   0.4378156806211790208
13      485485/944784    ~=    0.5138581940422361089
14      317181865/544195584 ~= 0.5828453488516363998
15      233718485/362797056 ~= 0.6442127385951003968
16      2279105465/3265173504    ~=    0.6980043976860593806
17      4862708305/6530347008    ~=    0.7446324520033836461
18      553436255195/705277476864  ~=  0.7847071164895857971
19      1155136002965/1410554953728 ~= 0.8189230769861569511
20      2691299309615/3173748645888 ~= 0.8479875408854210203
21      3692455480945/4231664861184 ~= 0.8725774847660946991
22      30241729508375/33853318889472    ~=    0.8933165344027712589
23      184994418145075/203119913336832   ~=   0.9107645582651482934
24      15225590090211325/16452712980283392 ~= 0.9254151645663163902
25      30855347500002025/32905425960566784 ~= 0.9376978598295146596
26      1122975934870626655/1184595334580404224   ~=   0.9479827432111204538
27      83938352963274355/87747802561511424 ~= 0.9565863818006538052
28      3425060881328615165/3553786003741212672   ~=   0.9637780321389404365
29      3446410906664072165/3553786003741212672   ~=   0.969785716707730165
30      1496550513734743428785/1535235553616203874304    ~=    0.9748018864008595101

 Posted by Charlie on 2013-07-12 17:54:06

 Search: Search body:
Forums (0)