Choosing every number at least once in a list of n numbers
August 19th, 2012 at 11:44:26 AM
permalink
If you are given a list of n numbers, and you pick numbers one at a time randomly allowing for repeats and without removing them, what is the average amount of picks that it would take to pick each number in the list at least once in terms of n?
For example, if there are 10 slips of paper in a hat with the numbers 1-10 written on them, how many picks (assuming the picks are random and that you put the slip back in the hat after picking it) would it take on average to pick each number at least once?
For example, if there are 10 slips of paper in a hat with the numbers 1-10 written on them, how many picks (assuming the picks are random and that you put the slip back in the hat after picking it) would it take on average to pick each number at least once?
August 19th, 2012 at 12:26:47 PM
permalink
For your 10 number question, I get about 29.29 draws (29.28968254)
=(10/10) + (10/9) + (10/8) + (10/7) + (10/6) + (10/5) + (10/4) + (10/3) + (10/2) + (10/1)
https://wizardofvegas.com/forum/off-topic/general/3110-a-little-math-problem/
and
https://wizardofvegas.com/forum/questions-and-answers/math/5739-ask-the-wizard-42-roulette-correction/
shows the math and the Wizard's link
way more math involved for the actual distribution and variance
standard deviation: 11.2110
=(10/10) + (10/9) + (10/8) + (10/7) + (10/6) + (10/5) + (10/4) + (10/3) + (10/2) + (10/1)
https://wizardofvegas.com/forum/off-topic/general/3110-a-little-math-problem/
and
https://wizardofvegas.com/forum/questions-and-answers/math/5739-ask-the-wizard-42-roulette-correction/
shows the math and the Wizard's link
way more math involved for the actual distribution and variance
standard deviation: 11.2110
x prob[X=x] prob[X<x] prob[X>=x] prob[X<=x] prob[X>x]
10 0.00036 0.00000 1.00000 0.00036 0.99964
11 0.00163 0.00036 0.99964 0.00200 0.99800
12 0.00419 0.00200 0.99800 0.00619 0.99381
13 0.00808 0.00619 0.99381 0.01427 0.98573
14 0.01305 0.01427 0.98573 0.02732 0.97268
15 0.01863 0.02732 0.97268 0.04595 0.95405
16 0.02436 0.04595 0.95405 0.07031 0.92969
17 0.02978 0.07031 0.92969 0.10009 0.89991
18 0.03458 0.10009 0.89991 0.13467 0.86533
19 0.03853 0.13467 0.86533 0.17320 0.82680
20 0.04154 0.17320 0.82680 0.21474 0.78526
21 0.04359 0.21474 0.78526 0.25832 0.74168
22 0.04473 0.25832 0.74168 0.30306 0.69694
23 0.04507 0.30306 0.69694 0.34813 0.65187
24 0.04471 0.34813 0.65187 0.39283 0.60717
25 0.04377 0.39283 0.60717 0.43660 0.56340
26 0.04238 0.43660 0.56340 0.47899 0.52101
27 0.04065 0.47899 0.52101 0.51963 0.48037
28 0.03867 0.51963 0.48037 0.55830 0.44170
29 0.03653 0.55830 0.44170 0.59483 0.40517
30 0.03430 0.59483 0.40517 0.62914 0.37086
31 0.03204 0.62914 0.37086 0.66118 0.33882
32 0.02980 0.66118 0.33882 0.69098 0.30902
33 0.02760 0.69098 0.30902 0.71857 0.28143
34 0.02547 0.71857 0.28143 0.74405 0.25595
35 0.02344 0.74405 0.25595 0.76749 0.23251
36 0.02152 0.76749 0.23251 0.78900 0.21100
37 0.01970 0.78900 0.21100 0.80871 0.19129
38 0.01801 0.80871 0.19129 0.82671 0.17329
39 0.01643 0.82671 0.17329 0.84314 0.15686
40 0.01496 0.84314 0.15686 0.85810 0.14190
41 0.01361 0.85810 0.14190 0.87170 0.12830
42 0.01236 0.87170 0.12830 0.88407 0.11593
43 0.01122 0.88407 0.11593 0.89528 0.10472
44 0.01017 0.89528 0.10472 0.90545 0.09455
45 0.00921 0.90545 0.09455 0.91467 0.08533
46 0.00834 0.91467 0.08533 0.92301 0.07699
47 0.00754 0.92301 0.07699 0.93055 0.06945
48 0.00682 0.93055 0.06945 0.93737 0.06263
49 0.00616 0.93737 0.06263 0.94354 0.05646
50 0.00557 0.94354 0.05646 0.94910 0.05090
51 0.00503 0.94910 0.05090 0.95413 0.04587
52 0.00454 0.95413 0.04587 0.95866 0.04134
53 0.00409 0.95866 0.04134 0.96276 0.03724
54 0.00369 0.96276 0.03724 0.96645 0.03355
55 0.00333 0.96645 0.03355 0.96978 0.03022
56 0.00300 0.96978 0.03022 0.97278 0.02722
57 0.00271 0.97278 0.02722 0.97548 0.02452
58 0.00244 0.97548 0.02452 0.97792 0.02208
59 0.00220 0.97792 0.02208 0.98012 0.01988
60 0.00198 0.98012 0.01988 0.98210 0.01790
61 0.00178 0.98210 0.01790 0.98388 0.01612
62 0.00161 0.98388 0.01612 0.98549 0.01451
63 0.00145 0.98549 0.01451 0.98694 0.01306
64 0.00130 0.98694 0.01306 0.98824 0.01176
65 0.00117 0.98824 0.01176 0.98941 0.01059
66 0.00106 0.98941 0.01059 0.99047 0.00953
67 0.00095 0.99047 0.00953 0.99142 0.00858
68 0.00086 0.99142 0.00858 0.99228 0.00772
69 0.00077 0.99228 0.00772 0.99305 0.00695
70 0.00069 0.99305 0.00695 0.99374 0.00626
71 0.00063 0.99374 0.00626 0.99437 0.00563
72 0.00056 0.99437 0.00563 0.99493 0.00507
73 0.00051 0.99493 0.00507 0.99544 0.00456
74 0.00046 0.99544 0.00456 0.99589 0.00411
75 0.00041 0.99589 0.00411 0.99630 0.00370
76 0.00037 0.99630 0.00370 0.99667 0.00333
77 0.00033 0.99667 0.00333 0.99700 0.00300
78 0.00030 0.99700 0.00300 0.99730 0.00270
79 0.00027 0.99730 0.00270 0.99757 0.00243
80 0.00024 0.99757 0.00243 0.99782 0.00218
81 0.00022 0.99782 0.00218 0.99803 0.00197
82 0.00020 0.99803 0.00197 0.99823 0.00177
83 0.00018 0.99823 0.00177 0.99841 0.00159
84 0.00016 0.99841 0.00159 0.99857 0.00143
85 0.00014 0.99857 0.00143 0.99871 0.00129
86 0.00013 0.99871 0.00129 0.99884 0.00116
87 0.00012 0.99884 0.00116 0.99896 0.00104
88 0.00010 0.99896 0.00104 0.99906 0.00094
89 0.00009 0.99906 0.00094 0.99915 0.00085
90 0.00008 0.99915 0.00085 0.99924 0.00076
91 0.00008 0.99924 0.00076 0.99931 0.00069
92 0.00007 0.99931 0.00069 0.99938 0.00062
August 19th, 2012 at 12:49:19 PM
permalink
A computer simulation for 10 slips confirms the above answer of 29.29.
For 5 slips it's about 11.42
For 20 slips it's about 71.94
For 5 slips it's about 11.42
For 20 slips it's about 71.94
August 19th, 2012 at 2:10:21 PM
permalink
I had made a table in Excel a while back
N Avg
1 1.0000
2 3.0000
3 5.5000
4 8.3333
5 11.4167
6 14.7000
7 18.1500
8 21.7429
9 25.4607
10 29.2897
11 33.2187
12 37.2385
13 41.3417
14 45.5219
15 49.7734
16 54.0917
17 58.4724
18 62.9119
19 67.4071
20 71.9548
21 76.5525
22 81.1979
23 85.8887
24 90.6230
25 95.3990
26 100.2149
27 105.0693
28 109.9608
29 114.8880
30 119.8496
31 124.8446
32 129.8718
33 134.9303
34 140.0191
35 145.1373
36 150.2841
37 155.4587
38 160.6603
39 165.8882
40 171.1417
41 176.4203
42 181.7232
43 187.0499
44 192.3999
45 197.7727
46 203.1676
47 208.5843
48 214.0223
49 219.4811
50 224.9603
August 19th, 2012 at 3:21:45 PM
permalink
Quote: guido111I had made a table in Excel a while back
Just in case somebody is particularly interested in the numbers 37 and 38. ;-)
August 19th, 2012 at 3:53:37 PM
permalink
There is a similar problem in economics.
The italian Panini group sells stickers for a collectible book of various themes (i.e. major sport events). You can buy a sticker packs containing random stickers.
Say the book needs N unique stickers before it is complete - how many stickers X does someone need to buy on average to fill the book ?
I.e. how much is a customer worth to Panini, who is determined to finish the book ?
The formula is X = N * (1/1 + 1/2 + ... + 1/N) ~= N * (ln(N) + 0.5772).
For N=10 it is X ~= 28.8. The approximation to the harmonic series (1/1 + 1/2 + ... + 1/N) becomes better with increasing N.
For N=37 it is X ~= 155
For N=38 it is X ~= 160
The italian Panini group sells stickers for a collectible book of various themes (i.e. major sport events). You can buy a sticker packs containing random stickers.
Say the book needs N unique stickers before it is complete - how many stickers X does someone need to buy on average to fill the book ?
I.e. how much is a customer worth to Panini, who is determined to finish the book ?
The formula is X = N * (1/1 + 1/2 + ... + 1/N) ~= N * (ln(N) + 0.5772).
For N=10 it is X ~= 28.8. The approximation to the harmonic series (1/1 + 1/2 + ... + 1/N) becomes better with increasing N.
For N=37 it is X ~= 155
For N=38 it is X ~= 160
August 19th, 2012 at 4:25:30 PM
permalink
This on my Math Problems site. #73 for the n=4 case, and #74 for the general case. I also state Mango's approximation formula in my solution to #74.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
