Thread Rating:

DorothyGale
DorothyGale
  • Threads: 40
  • Posts: 639
Joined: Nov 23, 2009
October 15th, 2010 at 4:24:59 PM permalink
While I was milking the pigs today, I thought of a little problem. Nothing this simple is new, but it's got some twists to it.

Suppose you're playing American roulette ... 38 numbers. What is the expected number of spins until all the numbers 1..36, and 0 and 00 have each been hit at least one time?

In general, given numbers 1 .. N and a random number generator that generates values from 1 to N, what is the expected number of numbers the generator will have to turn out until it has hit each of 1, 2, 3, ... up to N?

For example, with N = 2, the answer is 2*(1/2) + 3*(1/4) + 4*(1/8) + 5*(1/16) + ... = 3. So, the expected number of flips of a coin to get both heads and tails to appear is 3.

It's kind of the opposite of the birthday problem. How many people do you need to have in a room so that you expect every birth date to be hit by one or more people?

Oh, well, this is probably well known ... and I think I know the answer for roulette ... just in case no one cares ...

--Ms. D.
"Who would have thought a good little girl like you could destroy my beautiful wickedness!"
FleaStiff
FleaStiff
  • Threads: 265
  • Posts: 14484
Joined: Oct 19, 2009
October 15th, 2010 at 5:28:54 PM permalink
Quote: DorothyGale

While I was milking the pigs today,

I didn't know they even had pigs in Australia much less that pigs got milked!

>So, the expected number of flips of a coin to get both heads and tails to appear is 3.
I wish I understood that proof more clearly. Certainly 2 tosses are the minimum that is required and a certain probability exists for further tosses that both Heads and Tails will appear.

Are you thinking of establishing a FireBet for roulette?
DorothyGale
DorothyGale
  • Threads: 40
  • Posts: 639
Joined: Nov 23, 2009
October 15th, 2010 at 5:34:13 PM permalink
Quote: FleaStiff

Are you thinking of establishing a FireBet for roulette?

No, I don't care about applications of this question. Though I do see the relationship ... maybe someone else who cares can make a side bet out of it and say it's the world's best new idea and make a ton of money, I don't care ...

Ms. D.
"Who would have thought a good little girl like you could destroy my beautiful wickedness!"
mkl654321
mkl654321
  • Threads: 65
  • Posts: 3412
Joined: Aug 8, 2010
October 15th, 2010 at 6:18:11 PM permalink
Well, we all know that the longer it has been since a roulette number has hit, the more it becomes "due".

Therefore, after one spin, there are 37 numbers that are due, and one that isn't. This continues until 37 numbers have come up, and there is one number left, which is so, like, totally due that it is certain to hit.

Therefore, I say the answer is 39 spins (not 38, because one has to take into account atmospheric and gravitational disturbances).

Before I read all the surefire roulette systems posted on this board, and absorbed their mighty wisdom, I might have resorted to silly old math to obtain my answer. This way is so much easier!
The fact that a believer is happier than a skeptic is no more to the point than the fact that a drunken man is happier than a sober one. The happiness of credulity is a cheap and dangerous quality.---George Bernard Shaw
Kelmo
Kelmo
  • Threads: 6
  • Posts: 85
Joined: Aug 15, 2010
October 15th, 2010 at 6:26:05 PM permalink
Quote: DorothyGale

While I was milking the pigs today, I thought of a little problem. Nothing this simple is new, but it's got some twists to it.

Suppose you're playing American roulette ... 38 numbers. What is the expected number of spins until all the numbers 1..36, and 0 and 00 have each been hit at least one time?

In general, given numbers 1 .. N and a random number generator that generates values from 1 to N, what is the expected number of numbers the generator will have to turn out until it has hit each of 1, 2, 3, ... up to N?

For example, with N = 2, the answer is 2*(1/2) + 3*(1/4) + 4*(1/8) + 5*(1/16) + ... = 3. So, the expected number of flips of a coin to get both heads and tails to appear is 3.

It's kind of the opposite of the birthday problem. How many people do you need to have in a room so that you expect every birth date to be hit by one or more people?

Oh, well, this is probably well known ... and I think I know the answer for roulette ... just in case no one cares ...

--Ms. D.



Just a guess, but would it be around 514 or so? Approximation using ln2?
Kelmo
Kelmo
  • Threads: 6
  • Posts: 85
Joined: Aug 15, 2010
October 15th, 2010 at 6:43:04 PM permalink
Quote: Kelmo

Just a guess, but would it be around 514 or so? Approximation using ln2?



A better guess, about 158-160?
miplet
miplet
  • Threads: 5
  • Posts: 2105
Joined: Dec 1, 2009
October 15th, 2010 at 6:54:23 PM permalink
160.66 according to the Wizard.
“Man Babes” #AxelFabulous
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26432
Joined: Oct 14, 2009
October 15th, 2010 at 7:34:33 PM permalink
160.6602765.

I'll refrain from giving a solution to let others enjoy the problem.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26432
Joined: Oct 14, 2009
October 15th, 2010 at 8:22:34 PM permalink
Quote: miplet

160.66 according to the Wizard.



I forgot I answered that. How did you dig that up?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
DorothyGale
DorothyGale
  • Threads: 40
  • Posts: 639
Joined: Nov 23, 2009
October 15th, 2010 at 8:30:24 PM permalink
Mr. Wizard, sir ... reading this post here., you said:
Quote: Mr. W

Once you have hit n numbers the probability of getting a new number on the next spin is (38-n)/38. If the probability of an event is p then the expected number of trials before it happens is 1/p. Thus the expected number of spins to get a new number, given that you already have n, is 38/(38-n). For example once you have hit 20 numbers the expected number of spins to get the 21st is 38/18=2.11. So the answer is the product of the expected number of spins at each step: (38/38)*(38/37)*(38/36)*...*(38/1)=160.66. March 11, 2001


The answer 160.66 is right. That's what I got too. But, I think you want to "add" the numbers, not "multiply" them.

(38/38) + (38/37) + (38/36) + ... (38/2) + (38/1) = 160.66.

--Ms. D.
"Who would have thought a good little girl like you could destroy my beautiful wickedness!"
guido111
guido111
  • Threads: 10
  • Posts: 707
Joined: Sep 16, 2010
October 15th, 2010 at 9:01:31 PM permalink
From the Wizard of Odds site:
"So the answer is the product of the expected number of spins at each step: (38/38)*(38/37)*(38/36)*Ö*(38/1)=160.66."

I only get the 160.66 when I ADD all the steps instead of multiply.
1
1.027027027
1.055555556
1.085714286
1.117647059
1.151515152
1.1875
1.225806452
1.266666667
1.310344828
1.357142857
1.407407407
1.461538462
1.52
1.583333333
1.652173913
1.727272727
1.80952381
1.9
2
2.111111111
2.235294118
2.375
2.533333333
2.714285714
2.923076923
3.166666667
3.454545455
3.8
4.222222222
4.75
5.428571429
6.333333333
7.6
9.5
12.66666667
19
38
___________
160.6602765
guido111
guido111
  • Threads: 10
  • Posts: 707
Joined: Sep 16, 2010
October 15th, 2010 at 9:12:48 PM permalink
Quote: DorothyGale


For example, with N = 2, the answer is 2*(1/2) + 3*(1/4) + 4*(1/8) + 5*(1/16) + ... = 3. So, the expected number of flips of a coin to get both heads and tails to appear is 3.


So then (2/2)+(2/1)=3 solves for the coin toss example.
Another Wizard Gem!
guido111
guido111
  • Threads: 10
  • Posts: 707
Joined: Sep 16, 2010
October 15th, 2010 at 9:24:40 PM permalink
Quote: Wizard

160.6602765.

I'll refrain from giving a solution to let others enjoy the problem.


A quick Excel simulation shows only a 59.4% chance that in 161 spins, all 38 numbers would hit.


65377 groups of 161 spins so the sample size is small and the error about 1.5%

Nope27 has a nice table showing the probability of NOT hitting "at least 1" number in x spins
https://wizardofvegas.com/member/nope27/blog/#post153
Ace
Ace
  • Threads: 6
  • Posts: 43
Joined: Aug 15, 2013
August 17th, 2016 at 9:44:04 AM permalink
I just found this old thread while searching for something else.

In case you didn't know the answer is closely approximated by 38 x (ln 38 + γ) = 160.16, where γ is the Euler constant .57721...

This is a version of the coupon collectors problem.
mustangsally
mustangsally
  • Threads: 25
  • Posts: 2463
Joined: Mar 29, 2011
May 26th, 2018 at 1:31:31 PM permalink
Quote: Ace

This is a version of the coupon collectors problem.

yes, the basic version
as you know
there are many many versions to the ccp.

one can run R code for this here online
https://sites.google.com/view/krapstuff/coupon-collecting


BruceZ R code provided above

data
       draw          Prob on X      cumulative    
[1,] 37 0 0
[2,] 38 4.86120346e-16 4.86120346e-16
[3,] 39 8.993226401e-15 9.479346747e-15
[4,] 40 8.614564237e-14 9.562498912e-14
[5,] 41 5.691765657e-13 6.648015548e-13
[6,] 42 2.915675884e-12 3.580477438e-12
[7,] 43 1.234202623e-11 1.592250366e-11
[8,] 44 4.493466909e-11 6.085717275e-11
[9,] 45 1.446233166e-10 2.054804894e-10
[10,] 46 4.197640261e-10 6.252445154e-10
[11,] 47 1.115394694e-09 1.740639209e-09
[12,] 48 2.745508363e-09 4.486147572e-09
[13,] 49 6.319513238e-09 1.080566081e-08
[14,] 50 1.370746777e-08 2.451312858e-08
[15,] 51 2.819825894e-08 5.271138752e-08
[16,] 52 5.531184799e-08 1.080232355e-07
[17,] 53 1.039291494e-07 2.119523849e-07
[18,] 54 1.877993422e-07 3.997517271e-07
[19,] 55 3.274732435e-07 7.272249706e-07
[20,] 56 5.526923563e-07 1.279917327e-06
[21,] 57 9.052368025e-07 2.185154129e-06
[22,] 58 1.442202938e-06 3.627357068e-06
[23,] 59 2.239645227e-06 5.867002295e-06
[24,] 60 3.39647971e-06 9.263482005e-06
[25,] 61 5.038511251e-06 1.430199326e-05
[26,] 62 7.322416712e-06 2.162440997e-05
[27,] 63 1.043949409e-05 3.206390406e-05
[28,] 64 1.461897549e-05 4.668287956e-05
[29,] 65 2.013070094e-05 6.68135805e-05
[30,] 66 2.728696108e-05 9.410054158e-05
[31,] 67 3.644333883e-05 0.0001305438804
[32,] 68 4.799841269e-05 0.0001785422931
[33,] 69 6.239222416e-05 0.0002409345173
[34,] 70 8.010345867e-05 0.0003210379759
[35,] 71 0.0001016453376 0.0004226833135
[36,] 72 0.000127560269 0.0005502435825
[37,] 73 0.0001584133524 0.0007086569349
[38,] 74 0.0001947848733 0.0009034418082
[39,] 75 0.000237261963 0.001140703771
[40,] 76 0.0002864296247 0.001427133396
[41,] 77 0.0003428613473 0.001769994743
[42,] 78 0.000407109541 0.002177104284
[43,] 79 0.0004796960279 0.002656800312
[44,] 80 0.0005611028174 0.003217903129
[45,] 81 0.0006517633789 0.003869666508
[46,] 82 0.0007520546081 0.004621721117
[47,] 83 0.0008622896541 0.005484010771
[48,] 84 0.0009827117486 0.006466722519
[49,] 85 0.001113489145 0.007580211664
[50,] 86 0.001254711243 0.008834922907
[51,] 87 0.001406385947 0.01024130885
[52,] 88 0.001568438264 0.01180974712
[53,] 89 0.001740710129 0.01355045725
[54,] 90 0.001922961422 0.01547341867
[55,] 91 0.002114872092 0.01758829076
[56,] 92 0.002316045332 0.01990433609
[57,] 93 0.002526011677 0.02243034777
[58,] 94 0.002744233928 0.0251745817
[59,] 95 0.002970112782 0.02814469448
[60,] 96 0.003202993039 0.03134768752
[61,] 97 0.003442170257 0.03478985777
[62,] 98 0.00368689774 0.03847675551
[63,] 99 0.003936393734 0.04241314925
[64,] 100 0.004189848706 0.04660299796
[65,] 101 0.004446432623 0.05104943058
[66,] 102 0.004705302106 0.05575473268
[67,] 103 0.004965607402 0.06072034009
[68,] 104 0.005226499062 0.06594683915
[69,] 105 0.005487134293 0.07143397344
[70,] 106 0.00574668291 0.07718065635
[71,] 107 0.006004332849 0.0831849892
[72,] 108 0.006259295209 0.08944428441
[73,] 109 0.006510808794 0.0959550932
[74,] 110 0.006758144154 0.1027132374
[75,] 111 0.007000607105 0.1097138445
[76,] 112 0.00723754173 0.1169513862
[77,] 113 0.007468332886 0.1244197191
[78,] 114 0.007692408205 0.1321121273
[79,] 115 0.007909239634 0.1400213669
[80,] 116 0.008118344515 0.1481397114
[81,] 117 0.008319286249 0.1564589977
[82,] 118 0.008511674556 0.1649706722
[83,] 119 0.008695165377 0.1736658376
[84,] 120 0.008869460438 0.1825352981
[85,] 121 0.009034306517 0.1915696046
[86,] 122 0.009189494436 0.200759099
[87,] 123 0.00933485782 0.2100939568
[88,] 124 0.009470271652 0.2195642285
[89,] 125 0.009595650648 0.2291598791
[90,] 126 0.009710947485 0.2388708266
[91,] 127 0.009816150919 0.2486869775
[92,] 128 0.009911283796 0.2585982613
[93,] 129 0.009996401006 0.2685946623
[94,] 130 0.01007158738 0.2786662497
[95,] 131 0.01013695557 0.2888032053
[96,] 132 0.01019264393 0.2989958492
[97,] 133 0.01023881434 0.3092346635
[98,] 134 0.01027565017 0.3195103137
[99,] 135 0.0103033542 0.3298136679
[100,] 136 0.01032214655 0.3401358145
[101,] 137 0.0103322628 0.3504680773
[102,] 138 0.01033395204 0.3608020293
[103,] 139 0.01032747508 0.3711295044
[104,] 140 0.01031310269 0.3814426071
[105,] 141 0.01029111397 0.391733721
[106,] 142 0.01026179471 0.4019955157
[107,] 143 0.01022543601 0.4122209518
[108,] 144 0.01018233277 0.4224032845
[109,] 145 0.01013278246 0.432536067
[110,] 146 0.01007708389 0.4426131509
[111,] 147 0.01001553604 0.4526286869
[112,] 148 0.009948437068 0.462577124
[113,] 149 0.009876083334 0.4724532073
[114,] 150 0.009798768516 0.4822519758
[115,] 151 0.00971678283 0.4919687587
[116,] 152 0.009630412305 0.501599171
[117,] 153 0.009539938145 0.5111391091
[118,] 154 0.009445636154 0.5205847453
[119,] 155 0.009347776235 0.5299325215
[120,] 156 0.009246621943 0.5391791434
[121,] 157 0.00914243011 0.5483215735
[122,] 158 0.009035450517 0.5573570241
[123,] 159 0.008925925627 0.5662829497
[124,] 160 0.008814090359 0.5750970401
[125,] 161 0.008700171916 0.583797212
[126,] 162 0.008584389651 0.5923816016
[127,] 163 0.008466954977 0.6008485566
[128,] 164 0.008348071305 0.6091966279
[129,] 165 0.008227934027 0.6174245619
[130,] 166 0.008106730519 0.6255312924
[131,] 167 0.007984640178 0.6335159326
[132,] 168 0.007861834482 0.6413777671
[133,] 169 0.00773847707 0.6491162442
[134,] 170 0.007614723847 0.656730968
[135,] 171 0.007490723104 0.6642216911
[136,] 172 0.007366615652 0.6715883068
[137,] 173 0.007242534973 0.6788308418
[138,] 174 0.007118607382 0.6859494491
[139,] 175 0.006994952199 0.6929444013
[140,] 176 0.006871681928 0.6998160833
[141,] 177 0.006748902444 0.7065649857
[142,] 178 0.006626713189 0.7131916989
[143,] 179 0.006505207365 0.7196969063
[144,] 180 0.006384472142 0.7260813784
[145,] 181 0.006264588852 0.7323459673
[146,] 182 0.006145633203 0.7384916005
[147,] 183 0.006027675475 0.7445192759
[148,] 184 0.005910780734 0.7504300567
[149,] 185 0.005795009025 0.7562250657
[150,] 186 0.005680415583 0.7619054813
[151,] 187 0.00556705103 0.7674725323
[152,] 188 0.005454961567 0.7729274939
[153,] 189 0.005344189176 0.778271683
[154,] 190 0.005234771804 0.7835064549
[155,] 191 0.005126743552 0.7886331984
[156,] 192 0.005020134854 0.7936533333
[157,] 193 0.004914972662 0.7985683059
[158,] 194 0.004811280611 0.8033795865
[159,] 195 0.004709079192 0.8080886657
[160,] 196 0.004608385915 0.8126970516
[161,] 197 0.004509215465 0.8172062671
[162,] 198 0.004411579859 0.821617847
[163,] 199 0.004315488595 0.8259333356
[164,] 200 0.00422094879 0.8301542843
[165,] 201 0.004127965323 0.8342822497
[166,] 202 0.004036540969 0.8383187906
[167,] 203 0.003946676521 0.8422654672
[168,] 204 0.003858370922 0.8461238381
[169,] 205 0.003771621375 0.8498954595
[170,] 206 0.003686423462 0.8535818829
[171,] 207 0.00360277125 0.8571846542
[172,] 208 0.003520657396 0.8607053116
[173,] 209 0.003440073247 0.8641453848
[174,] 210 0.003361008934 0.8675063937
[175,] 211 0.003283453461 0.8707898472
[176,] 212 0.003207394797 0.873997242
[177,] 213 0.003132819954 0.877130062
[178,] 214 0.003059715063 0.880189777
[179,] 215 0.002988065457 0.8831778425
[180,] 216 0.002917855732 0.8860956982
[181,] 217 0.002849069822 0.888944768
[182,] 218 0.002781691059 0.8917264591
[183,] 219 0.002715702232 0.8944421613
[184,] 220 0.002651085649 0.897093247
[185,] 221 0.002587823185 0.8996810702
[186,] 222 0.002525896339 0.9022069665
[187,] 223 0.002465286276 0.9046722528
[188,] 224 0.002405973878 0.9070782267
[189,] 225 0.002347939785 0.9094261664
[190,] 226 0.00229116443 0.9117173309
[191,] 227 0.002235628087 0.913952959
[192,] 228 0.002181310896 0.9161342699
[193,] 229 0.002128192904 0.9182624628
[194,] 230 0.002076254091 0.9203387168
[195,] 231 0.002025474402 0.9223641912
[196,] 232 0.001975833774 0.924340025
[197,] 233 0.001927312158 0.9262673372
[198,] 234 0.001879889547 0.9281472267
[199,] 235 0.001833545996 0.9299807727
[200,] 236 0.001788261643 0.9317690344
[201,] 237 0.001744016725 0.9335130511
[202,] 238 0.0017007916 0.9352138427
[203,] 239 0.001658566758 0.9368724095
[204,] 240 0.001617322841 0.9384897323
[205,] 241 0.001577040652 0.9400667729
[206,] 242 0.00153770117 0.9416044741
[207,] 243 0.001499285562 0.9431037597
[208,] 244 0.00146177519 0.9445655349
[209,] 245 0.001425151623 0.9459906865
[210,] 246 0.001389396645 0.9473800831
[211,] 247 0.001354492261 0.9487345754
[212,] 248 0.001320420707 0.9500549961
[213,] 249 0.001287164452 0.9513421606
[214,] 250 0.001254706207 0.9525968668
[215,] 251 0.001223028926 0.9538198957
[216,] 252 0.001192115813 0.9550120115
[217,] 253 0.001161950322 0.9561739618
[218,] 254 0.001132516164 0.957306478
[219,] 255 0.001103797306 0.9584102753
[220,] 256 0.001075777975 0.9594860533
[221,] 257 0.001048442655 0.9605344959
[222,] 258 0.001021776095 0.961556272
[223,] 259 0.0009957633018 0.9625520353
[224,] 260 0.000970389547 0.9635224249
[225,] 261 0.0009456403615 0.9644680652
[226,] 262 0.0009215015376 0.9653895668
[227,] 263 0.0008979591278 0.9662875259
[228,] 264 0.0008749994431 0.9671625253
[229,] 265 0.0008526090524 0.9680151344
[230,] 266 0.0008307747802 0.9688459092
[231,] 267 0.0008094837052 0.9696553929
[232,] 268 0.0007887231584 0.970444116
[233,] 269 0.0007684807205 0.9712125968
[234,] 270 0.0007487442199 0.971961341
[235,] 271 0.0007295017299 0.9726908427
[236,] 272 0.0007107415665 0.9734015843
[237,] 273 0.0006924522853 0.9740940366
[238,] 274 0.0006746226787 0.9747686592
[239,] 275 0.0006572417731 0.975425901
[240,] 276 0.0006402988256 0.9760661998
[241,] 277 0.0006237833211 0.9766899832
[242,] 278 0.0006076849692 0.9772976681
[243,] 279 0.0005919937005 0.9778896618
[244,] 280 0.0005766996639 0.9784663615
[245,] 281 0.0005617932228 0.9790281547
[246,] 282 0.0005472649521 0.9795754197
[247,] 283 0.0005331056343 0.9801085253
[248,] 284 0.0005193062567 0.9806278316
[249,] 285 0.0005058580076 0.9811336896
[250,] 286 0.000492752273 0.9816264418
[251,] 287 0.000479980633 0.9821064225
[252,] 288 0.0004675348586 0.9825739573
[253,] 289 0.0004554069079 0.9830293642
[254,] 290 0.0004435889232 0.9834729532
[255,] 291 0.0004320732272 0.9839050264
[256,] 292 0.0004208523196 0.9843258787
[257,] 293 0.0004099188739 0.9847357976
[258,] 294 0.000399265734 0.9851350633
[259,] 295 0.000388885911 0.9855239492
[260,] 296 0.0003787725794 0.9859027218
[261,] 297 0.0003689190746 0.9862716409
[262,] 298 0.0003593188889 0.9866309598
[263,] 299 0.0003499656689 0.9869809254
[264,] 300 0.0003408532121 0.9873217786
[265,] 301 0.0003319754636 0.9876537541
[266,] 302 0.0003233265134 0.9879770806
[267,] 303 0.0003149005929 0.9882919812
[268,] 304 0.0003066920722 0.9885986733
[269,] 305 0.0002986954573 0.9888973687
[270,] 306 0.0002909053867 0.9891882741
[271,] 307 0.0002833166287 0.9894715908
[272,] 308 0.0002759240789 0.9897475148
[273,] 309 0.000268722757 0.9900162376
[274,] 310 0.0002617078041 0.9902779454
[275,] 311 0.0002548744803 0.9905328199
[276,] 312 0.0002482181617 0.990781038
[277,] 313 0.0002417343379 0.9910227724
[278,] 314 0.0002354186097 0.991258191
[279,] 315 0.0002292666861 0.9914874577
[280,] 316 0.0002232743822 0.9917107321
[281,] 317 0.0002174376167 0.9919281697
[282,] 318 0.0002117524093 0.9921399221
[283,] 319 0.0002062148787 0.992346137
[284,] 320 0.00020082124 0.9925469582
[285,] 321 0.0001955678028 0.992742526
[286,] 322 0.0001904509686 0.992932977
[287,] 323 0.0001854672289 0.9931184442
[288,] 324 0.000180613163 0.9932990574
[289,] 325 0.0001758854358 0.9934749428
[290,] 326 0.0001712807963 0.9936462236
[291,] 327 0.0001667960747 0.9938130197
[292,] 328 0.0001624281814 0.9939754479
[293,] 329 0.0001581741043 0.994133622
[294,] 330 0.0001540309076 0.9942876529
[295,] 331 0.0001499957294 0.9944376486
[296,] 332 0.0001460657803 0.9945837144
[297,] 333 0.0001422383416 0.9947259527
[298,] 334 0.0001385107633 0.9948644635
[299,] 335 0.0001348804628 0.9949993439
[300,] 336 0.0001313449229 0.9951306889
[301,] 337 0.0001279016907 0.9952585906
[302,] 338 0.0001245483754 0.9953831389
[303,] 339 0.0001212826472 0.9955044216
[304,] 340 0.0001181022359 0.9956225238
[305,] 341 0.000115004929 0.9957375287
[306,] 342 0.0001119885705 0.9958495173
[307,] 343 0.0001090510597 0.9959585684
[308,] 344 0.0001061903493 0.9960647587
[309,] 345 0.0001034044449 0.9961681632
[310,] 346 0.0001006914027 0.9962688546
[311,] 347 9.804932913e-05 0.9963669039
[312,] 348 9.547637895e-05 0.9964623803
[313,] 349 9.297075443e-05 0.996555351
[314,] 350 9.053070399e-05 0.9966458817
[315,] 351 8.815452109e-05 0.9967340363
[316,] 352 8.584054311e-05 0.9968198768
[317,] 353 8.358715022e-05 0.996903464
[318,] 354 8.139276432e-05 0.9969848567
[319,] 355 7.925584798e-05 0.9970641126
[320,] 356 7.717490343e-05 0.9971412875
[321,] 357 7.514847154e-05 0.9972164359
[322,] 358 7.317513086e-05 0.9972896111
[323,] 359 7.125349666e-05 0.9973608646
[324,] 360 6.938221999e-05 0.9974302468
[325,] 361 6.755998678e-05 0.9974978068
[326,] 362 6.578551697e-05 0.9975635923
[327,] 363 6.405756363e-05 0.9976276499
[328,] 364 6.237491209e-05 0.9976900248
[329,] 365 6.073637919e-05 0.9977507611
[330,] 366 5.91408124e-05 0.997809902
[331,] 367 5.75870891e-05 0.997867489
[332,] 368 5.607411576e-05 0.9979235632
[333,] 369 5.460082725e-05 0.997978164
[334,] 370 5.316618609e-05 0.9980313302
[335,] 371 5.176918172e-05 0.9980830994
[336,] 372 5.040882985e-05 0.9981335082
[337,] 373 4.908417178e-05 0.9981825924
[338,] 374 4.77942737e-05 0.9982303866
[339,] 375 4.653822611e-05 0.9982769249
[340,] 376 4.531514316e-05 0.99832224
[341,] 377 4.412416205e-05 0.9983663642
[342,] 378 4.296444245e-05 0.9984093286
[343,] 379 4.18351659e-05 0.9984511638
[344,] 380 4.073553525e-05 0.9984918993
[345,] 381 3.966477413e-05 0.9985315641
[346,] 382 3.862212641e-05 0.9985701862
[347,] 383 3.760685564e-05 0.9986077931
[348,] 384 3.66182446e-05 0.9986444113
[349,] 385 3.565559477e-05 0.9986800669
[350,] 386 3.471822583e-05 0.9987147851
[351,] 387 3.380547524e-05 0.9987485906
[352,] 388 3.291669774e-05 0.9987815073
[353,] 389 3.205126492e-05 0.9988135586
[354,] 390 3.120856475e-05 0.9988447671
[355,] 391 3.038800123e-05 0.9988751551
[356,] 392 2.958899389e-05 0.9989047441
[357,] 393 2.881097744e-05 0.9989335551
[358,] 394 2.805340137e-05 0.9989616085
[359,] 395 2.731572954e-05 0.9989889242
[360,] 396 2.659743985e-05 0.9990155217
[361,] 397 2.589802382e-05 0.9990414197
[362,] 398 2.52169863e-05 0.9990666367
[363,] 399 2.455384506e-05 0.9990911905
[364,] 400 2.390813051e-05 0.9991150987
from avg draws
0 160.66028
1 159.66028
2 158.63325
3 157.57769
4 156.49198
5 155.37433
6 154.22282
7 153.03532
8 151.80951
9 150.54284
10 149.23250
11 147.87536
12 146.46795
13 145.00641
14 143.48641
15 141.90308
16 140.25090
17 138.52363
18 136.71411
19 134.81411
20 132.81411
21 130.70300
22 128.46770
23 126.09270
24 123.55937
25 120.84508
26 117.92201
27 114.75534
28 111.30079
29 107.50079
30 103.27857
31 98.52857
32 93.10000
33 86.76667
34 79.16667
35 69.66667
36 57.00000
37 38.00000

"A quick Excel simulation shows only a 59.4% chance that in 161 spins, all 38 numbers would hit."

that I calculated using a Markov chain in R (in the spoiler results)
161 spins: all 38 numbers prob: 0.583797212

Sally
I Heart Vi Hart
Ace2
Ace2
  • Threads: 32
  • Posts: 2672
Joined: Oct 2, 2017
May 26th, 2018 at 1:44:36 PM permalink
58 % sounds reasonable. We know it’s between 50 % and 63% (1 - 1/e).
It’s all about making that GTA
Ace2
Ace2
  • Threads: 32
  • Posts: 2672
Joined: Oct 2, 2017
June 28th, 2018 at 9:19:30 PM permalink
Has anyone ever worked the coupon collector problem, but with 2 hits required? So, for instance, what is the expected number of roulette spins for every number to have appeared at least twice ? I thought about it today but no solution so far.
It’s all about making that GTA
mustangsally
mustangsally
  • Threads: 25
  • Posts: 2463
Joined: Mar 29, 2011
June 28th, 2018 at 10:34:32 PM permalink
Quote: Ace2

Has anyone ever worked the coupon collector problem, but with 2 hits required?

yes, I actually have but it recently got off of my A-list.

I was reading this interesting pdf
(Handsome man, sweet family)

https://www.cmc3.org/conference/Tahoe15/Tahoe15_JLee.pdf

"Two Questions I Started To Ask Myself
1) How Many Happy Meals Do I Have To Buy
Before I Collect All 8 Toys?
2) How Much Money Will I Spend Until I Have
Collected All 8 Toys?"
What If We Want To Collect Two Complete Sets?

in the pdf he continues
"Another Method To Calculate The Waiting Time
Is To Use The Dirichlet Type-II C-Integral
This Is Used To Calculate The Lower Tail Of
The Multinomial Distribution"

ok
learn some more stuff

well,
I started with a Markov chain approach (states get large)
but found myself completing other projects first (as I usually do)

not much easy stuff out there that I found

I am more into the actual distribution (the mean is ok too)
as one can create fun games to play from them (imo, of course)
Sally
I Heart Vi Hart
mustangsally
mustangsally
  • Threads: 25
  • Posts: 2463
Joined: Mar 29, 2011
June 29th, 2018 at 9:05:57 AM permalink
ok, I have this close to being done using the Markov chain solution
yes, there are other methods too. I like this method and start in Excel


*****
regular coupon collect problem of at least 1 of each:
will start with coupons=3
(coupons=38 asked for will be later as only in Excel right now and NOT online yet. the number of states is (N+1)*(N+2) / 2 = 780 so I have to get it right the 1st time)

mean wait time for at least 1 of each = 11/2 = 5.5
the distribution
(from here: https://sites.google.com/view/krapstuff/coupon-collecting
section 3r.)
Draw xDraw x Probcumulative: x or less
200
30.2222222220.222222222
40.2222222220.444444444
50.1728395060.617283951
60.123456790.740740741
70.0850480110.825788752
80.0576131690.88340192
90.0387136110.922115531
100.0259106840.948026216
110.017307660.965333875
120.011549730.976883605
130.0077035830.984587188
140.0051369770.989724165
150.0034250690.993149234
160.0022835190.995432753
170.0015223920.996955146
180.0010149440.997970089
190.0006766340.998646724
200.0004510910.999097815


*****
coupon collect problem of at least 2 of each:
with coupons=3
mean wait time for at least 1 of each = 347/36 (about 9.638888889)
the distribution
draw xdraw x probcumulative: (x or less)
100
200
300
400
500
60.123456790.12345679
70.1646090530.288065844
80.160036580.448102423
90.1365645480.584666971
100.1088248740.693491846
110.0833206320.776812478
120.0622195130.83903199
130.0457021570.884734147
140.03318650.917920647
150.0238964540.941817101
160.0170960760.958913177
170.0121676170.971080794
180.0086226780.979703471
190.0060880830.985791554
200.0042847620.990076316


what they both look like
1st = at least 1
2nd = at least 2


1st to see
Sally
Last edited by: mustangsally on Jun 29, 2018
I Heart Vi Hart
Gabes22
Gabes22
  • Threads: 15
  • Posts: 1427
Joined: Jul 19, 2011
June 29th, 2018 at 1:26:48 PM permalink
The only problem I see in the McDonald's problem is don't they "release" the different toys at different dates. i.e. releasing toy A on June 1st and toy B on June 8th and so on and so forth, They might do it in waves to like release A, B and C on one date then D, E and F on another and so on and so forth. Knowing that information may drastically change the odds.
A flute with no holes is not a flute, a donut with no holes is a danish
beachbumbabs
beachbumbabs
  • Threads: 100
  • Posts: 14260
Joined: May 21, 2013
June 29th, 2018 at 4:50:50 PM permalink
Quote: Gabes22

The only problem I see in the McDonald's problem is don't they "release" the different toys at different dates. i.e. releasing toy A on June 1st and toy B on June 8th and so on and so forth, They might do it in waves to like release A, B and C on one date then D, E and F on another and so on and so forth. Knowing that information may drastically change the odds.



I have seen them do that, yes.
If the House lost every hand, they wouldn't deal the game.
mustangsally
mustangsally
  • Threads: 25
  • Posts: 2463
Joined: Mar 29, 2011
July 1st, 2018 at 9:51:07 AM permalink
Quote: Ace2

Has anyone ever worked the coupon collector problem, but with 2 hits required? So, for instance, what is the expected number of roulette spins for every number to have appeared at least twice ?

the simple answer is, of course, just less than 2x that of collecting at least 1 each...

I have some help with this question now,
as the pdf I was using had the transition matrix populated correctly
but how to do it was by far not correct. (the main diagonal is easy using a helper column, the others are elusive right now)

I found a formula for this
in this pdf on page 14 that looks good
"By termwise integration it is easy to obtain the following exact
formula, which is a finite sum, for T2,
the average number of trials needed to collect
at least two of each of the d kinds of coupons
:"

http://www.brynmawr.edu/math/people/anmyers/PAPERS/SIGEST_Coupons.pdf

but do not understand where and what m and j is (I think m=2 and j=number of states) in the formula they arrive at
(the results from the formula are correct so far)

but I never took calculus and the calculus to inclusion exclusion conversion
lost me
at this point in time

Sally
Last edited by: mustangsally on Jul 1, 2018
I Heart Vi Hart
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6218
Joined: Jun 22, 2011
July 1st, 2018 at 12:56:34 PM permalink
Quote: mustangsally

I found a formula for this in this pdf on page 14 that looks good
"By termwise integration it is easy to obtain the following exact formula, which is a finite sum, for T2, the average number of trials needed to collect
at least two of each of the d kinds of coupons
:"

http://www.brynmawr.edu/math/people/anmyers/PAPERS/SIGEST_Coupons.pdf

but do not understand where and what m and j is (I think m=2 and j=number of states) in the formula they arrive at
(the results from the formula are correct so far)


I think m and j under the sigma sign usually means "for all nonnegative integers m and j," but in this case, it appears to be 0 <= j <= m <= d - 1, as otherwise (d-1)C(m) and (m)C(j) are undefined.
However, while I get results of 2, 11/2, 347/36, and 11259/864, I get them for d = 1 through 4 instead of 2 through 5, which makes sense, as if d = 1, it will always take 2 draws to get "each" coupon twice, while for d = 2, getting all of the coupons in a total of 2 draws happens only half of the time.
mustangsally
mustangsally
  • Threads: 25
  • Posts: 2463
Joined: Mar 29, 2011
July 1st, 2018 at 8:28:17 PM permalink
Quote: ThatDonGuy

I think m and j under the sigma sign usually means "for all nonnegative integers m and j," but in this case, it appears to be 0 <= j <= m <= d - 1, as otherwise (d-1)C(m) and (m)C(j) are undefined.

ok, I have time now to look at this again.
nice observation
Quote: ThatDonGuy

However, while I get results of 2, 11/2, 347/36, and 11259/864,

what values did you use for m and j?
Quote: ThatDonGuy

I get them for d = 1 through 4 instead of 2 through 5, <snip>

I saw that too. I think that is a typo as the rows of results below that shows the correct values 1:4

For the 38 numbers on a 00 Roulette wheel,
Excel says (once I was shown how to populate the transition matrix fast)
mean spins = 234.8326629 for 'at least 2' of each number
that is just over a 40% increase for the 'at least 1' value.
(time for a fast simulation)

now, to see if I can too get the formula to work (from the pdf I linked to)
The Markov chain method may take some time to get into R or even Pari GP
I want the distribution (as always)

Sally
I Heart Vi Hart
Ace2
Ace2
  • Threads: 32
  • Posts: 2672
Joined: Oct 2, 2017
July 1st, 2018 at 9:26:42 PM permalink
Can someone run the number for 1000 coupons, getting at least 2 of each ? I’d be interested to know if there’s a limit. Based on what I’ve seen the limit could be the natural log of 2. So if the average is about 7,485 tries to get all of them once, it would be that divided by 0.693 = 10,800 to get all of them twice. Just a guess.
It’s all about making that GTA
mustangsally
mustangsally
  • Threads: 25
  • Posts: 2463
Joined: Mar 29, 2011
July 2nd, 2018 at 7:16:29 AM permalink
Quote: Ace2

Based on what I’ve seen the limit could be the natural log of 2. So if the average is about 7,485 tries to get all of them once, it would be that divided by 0.693 = 10,800 to get all of them twice. Just a guess.

Here is a small table of data so far
ABCDEF
couponsat least 1at least 2B/CC-BE/B
1120.50011
235.50.5452.50.833333333
35.59.63890.5714.13890.752527273
48.333314.1890.5875.85570.702686811
511.41719.0410.6007.6240.667776123
614.724.1340.6099.4340.641768707
718.1529.4250.61711.2750.621212121
821.74334.8850.62313.1420.604424412
925.4640.4920.62915.0320.590416339
1029.2946.230.63416.940.578354387
38160.66234.8330.68474.1730.461676833


Sally
I Heart Vi Hart
mustangsally
mustangsally
  • Threads: 25
  • Posts: 2463
Joined: Mar 29, 2011
July 4th, 2018 at 8:59:17 AM permalink
Quote: mustangsally

Here is a small table of data so far

extended the data as I finished the R code for the Markov chain solution (my computer is so small and old as 8GB ram is all)
couponsat least 1at least 2B/CC-BE/B
70338.299481.71050.702143.41150.423919373
80397.238562.72220.706165.48420.416587033
90457.431645.14010.709187.70910.410355004
100518.7378728.80520.712210.06740.404958729
110581.046813.59070.714232.54470.400217367
120644.264899.3930.716255.1290.396000708
125676.1905942.6480.717266.45750.394056852
130708.317986.12610.718277.80910.392210126
140773.141073.7170.720300.5770.388774349
2001175.6061614.3130.728438.3940.372908951
3001884.7992557.8840.737673.0850.35711235
4002627.9723538.970.7439110.346654378


to see what the 'at least 1' and 'at least 2' look like together
Oh, they look to be going apart


ok,
math is done 4 today
Happy 4th of July 2018 USA!

Sally
Last edited by: mustangsally on Jul 4, 2018
I Heart Vi Hart
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6218
Joined: Jun 22, 2011
July 4th, 2018 at 10:37:49 AM permalink
Quote: mustangsally

what values did you use for m and j?


For d = 3, I used the (m,j) pairs (0,0), (0,1), (0,2), (1,1), (1,2), and (2,2).
For d = 4, I used the (m,j) pairs (0,0), (0,1), (0,2), (1,1), (1,2), (2,2), (0,3), (1,3), (2,3), and (3,3).

In other words, replace the Sigma with "m,j" at the bottom with a Sigma with "m=0" at the bottom and "d-1" at the top, followed by another Sigma with "j=0" at the bottom and "m" at the top.
mustangsally
mustangsally
  • Threads: 25
  • Posts: 2463
Joined: Mar 29, 2011
July 5th, 2018 at 8:12:56 AM permalink
Quote: ThatDonGuy

In other words, replace the Sigma with "m,j" at the bottom with a Sigma with "m=0" at the bottom and "d-1" at the top, followed by another Sigma with "j=0" at the bottom and "m" at the top.

thank you.
I found another pdf that shows what m and j are
problem I see is this
(j + 2)!
in the formula

Excel does 170! and below but requires the gamma() for higher factorials
R takes too long over that (and precision suffers)
I used a recursion method in R to make this
couponsat least 1at least 2at least 3at least 4at least 5
112345
235.57.87510.187512.46094
35.59.638913.4868817.1920220.80842
48.333314.18919.5659124.7102329.71024
511.41719.04125.9868432.6027939.01481
614.724.1338732.6771640.7894348.63511
718.1529.42539.5895449.2179658.51471
821.74334.88546.6906857.8517568.61409
925.4640.49253.9558966.663778.90403
1029.2946.2361.3661475.6329689.36209
1133.2186552.0842568.906384.7429999.97046
1237.2385358.0450376.564193.98035110.7147
1341.3417464.1028484.32933103.3339121.5829
1445.5218770.2500392.19342112.7944132.5651
1549.7734376.48005100.149122.3537143.6525
1654.0916682.78725108.1899132.005154.838
1758.4723989.1667116.3104141.7422166.115
1862.9119595.61405124.5058151.5602177.4778
1967.40705102.1254132.7717161.4543188.9216
2071.955108.6974141.1043171.4202200.4418
2176.55253115.3269149.5002181.4542.
2281.19789122.0111157.9563191.553.
2385.8887128.7475166.4696201.7135.
2490.623135.5337175.0378211.9329.
2595.39895142.3677183.6583222.2086.
26100.2149149.2474192.329232.5384.
27105.0693156.1711201.0481242.92.
28109.9608163.1372209.8135253.3515.
29114.888170.144218.6236263.831.
30119.85177.1902227.4768274.3569.
31124.8446184.2745236.3717284.9274.
32129.8718191.3955245.3068295.5411.
33134.9303198.552254.2809..
34140.0191205.7431263.2927..
35145.1373212.9677272.3412..
36150.2841220.2247281.4251..
37155.4587227.5133290.5436..
38160.6603234.833299.6956..
39165.8882242.1819308.8803..
40171.142249.5602318.0967..


this looks good for now
Sally
Last edited by: mustangsally on Jul 5, 2018
I Heart Vi Hart
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6218
Joined: Jun 22, 2011
Thanked by
mustangsally
July 5th, 2018 at 4:23:09 PM permalink
Quote: Ace2

Can someone run the number for 1000 coupons, getting at least 2 of each ? I’d be interested to know if there’s a limit. Based on what I’ve seen the limit could be the natural log of 2. So if the average is about 7,485 tries to get all of them once, it would be that divided by 0.693 = 10,800 to get all of them twice. Just a guess.


I can't use the formula for anything above about 50, as there's either an overflow or an underflow (i.e. the number is so small that it is treated as zero) that's throwing the results off.
For those of you interested in details, it's something like this: for 51 coupons, with M = 50 and J = 25, the value involved in the sum is on the order of 1018. However, 64-bit floating point numbers as implemented by Microsoft are only accurate to about 15 digits, so it's going to be off by up to 1000, which is not good when the final sum (over all J from 0 to 50) is supposed to be around 400.

However, when I run a simulation on various numbers of coupons up to 1000, and divide the simulated average number of draws needed to get two of each by the expected number needed to get one of each, it approaches something like 1.319.
EDIT: At 5000, it's more like 1.278.
As a matter of fact, I wouldn't be surprised if the limit of the ratio is 1. If you have, say, Googolplex (that's 1 followed by googol zeroes) different coupons, there's a very, very, very good chance you will be very close to having chosen all of the coupons at least twice by the time you choose every coupon once.
Last edited by: ThatDonGuy on Jul 5, 2018
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6218
Joined: Jun 22, 2011
July 5th, 2018 at 6:18:03 PM permalink
After some fancy number crunching with big integers to get around the significant digits problem, here is an approximation to the 2-coupon problem for up to 1000 different coupons, along with a ratio of the 2-coupon to 1-coupon values.

Coupons2 of Each1 of EachRatio
1046.22129.2901.578
20108.66771.9551.510
30177.162119.8501.478
40249.529171.1421.458
50324.765224.9601.444
60402.279280.7921.433
70481.672338.2991.424
80562.691397.2381.417
90645.102457.4311.410
100728.775518.7381.405
110813.565581.0461.400
120899.351644.2641.396
130986.093708.3171.392
1401073.683773.1401.389
1501162.080838.6771.386
1601251.196904.8821.383
1701341.026971.7121.380
1801431.5021039.1311.378
1901522.6051107.1051.375
2001614.2831175.6061.373
2101706.5201244.6071.371
2201799.2741314.0851.369
2301892.5391384.0171.367
2401986.2911454.3851.366
2502080.5131525.1691.364
2602175.1481596.3531.363
2702270.2241667.9221.361
2802365.7131739.8611.360
2902461.5931812.1581.358
3002557.8561884.7991.357
3102654.4811957.7741.356
3202751.4552031.0711.355
3302848.7972104.6811.354
3402946.4632178.5951.352
3503044.4512252.8021.351
3603142.7442327.2951.350
3703241.3652402.0661.349
3803340.2562477.1071.348
3903439.4612552.4111.348
4003538.9392627.9721.347
4103638.6952703.7831.346
4203738.6962779.8371.345
4303838.9952856.1301.344
4403939.5522932.6561.343
4504040.3243009.4081.343
4604141.3583086.3831.342
4704242.6293163.5761.341
4804344.1263240.9811.340
4904445.8823318.5941.340
5004547.8283396.4121.339
5104650.0203474.4291.338
5204752.4043552.6431.338
5304855.0033631.0491.337
5404957.8363709.6441.336
5505060.8403788.4241.336
5605164.0623867.3851.335
5705267.4663946.5261.335
5805371.0564025.8411.334
5905474.8684105.3291.334
6005578.8354184.9871.333
6105683.0014264.8111.333
6205787.3524344.8001.332
6305891.8644424.9491.332
6405996.5484505.2581.331
6506101.4024585.7221.331
6606206.4524666.3411.330
6706311.6344747.1101.330
6806417.0054828.0301.329
6906522.5134909.0961.329
7006628.2244990.3071.328
7106734.0435071.6611.328
7206840.0175153.1561.327
7306946.1715234.7901.327
7407052.4775316.5611.327
7507158.9095398.4671.326
7607265.4955480.5061.326
7707372.2235562.6771.325
7807479.0805644.9771.325
7907586.1105727.4061.325
8007693.2665809.9621.324
8107800.5485892.6421.324
8207907.9605975.4461.323
8308015.5376058.3721.323
8408123.2096141.4191.323
8508231.0266224.5841.322
8608338.9616307.8671.322
8708447.0486391.2671.322
8808555.2366474.7811.321
8908663.5866558.4091.321
9008772.0026642.1491.321
9108880.6056726.0011.320
9208989.2796809.9621.320
9309098.0806894.0321.320
9409207.0026978.2101.319
9509316.0467062.4941.319
9609425.1877146.8831.319
9709534.4647231.3761.318
9809643.8647315.9731.318
9909753.3407400.6711.318
10009862.9427485.4711.318


Ace2
Ace2
  • Threads: 32
  • Posts: 2672
Joined: Oct 2, 2017
July 5th, 2018 at 8:42:27 PM permalink
Quote: ThatDonGuy

As a matter of fact, I wouldn't be surprised if the limit of the ratio is 1. If you have, say, Googolplex (that's 1 followed by googol zeroes) different coupons, there's a very, very, very good chance you will be very close to having chosen all of the coupons at least twice by the time you choose every coupon once.

Yes it does appear that way.

These are some great answers from you and Mustang Sally. I found a fairly slick way to simulate this in excel but my computer freezes for anything over about 500 coupons.

It’s amazing how this problem is very simple for 1 of each coupon, but gets quite tedious for any other number, even with a formula.

From what I can tell, the formula is basically an enormous inclusion-exclusion exercise which explodes before the number of coupons gets very large.
It’s all about making that GTA
mustangsally
mustangsally
  • Threads: 25
  • Posts: 2463
Joined: Mar 29, 2011
July 6th, 2018 at 10:53:25 AM permalink
Quote: Ace2

It’s amazing how this problem is very simple for 1 of each coupon, but gets quite tedious for any other number, even with a formula.

yes it is.
of course, if it was real simple, every one could do it.
Quote: Ace2

From what I can tell, the formula is basically an enormous inclusion-exclusion exercise which explodes before the number of coupons gets very large.

agree.
even the approximation formula given (online and in papers) is way off on most results.
I am not wasting my time figuring out how far off and what ranges
others have done that before

I can only think of fun dice games to play with the distribution data
other than that, hard to imagine what good knowing the mean for at least 2 is.
from my R code not published yet
Time difference of 2.952016 mins <<<< takes time even for my machine
> print(sprintf("for %g items at least 2 each, mean:%g ",N,meanTrials))
[1] "for 38 items at least 2 each, mean: 234.833 "
> print(formatC(data, digits=10),quote=FALSE)
Draw X Draw X Prob cumulative: (X or less)
[1,] 75 0 0
[2,] 76 5.925597361e-21 5.925597361e-21
[3,] 77 1.461647349e-19 1.520903323e-19
[4,] 78 1.851099439e-18 2.003189771e-18
[5,] 79 1.603948436e-17 1.804267413e-17
[6,] 80 1.069168303e-16 1.249595045e-16
[7,] 81 5.845270243e-16 7.094865288e-16
[8,] 82 2.728872441e-15 3.43835897e-15
[9,] 83 1.118442664e-14 1.462278561e-14
[10,] 84 4.106353755e-14 5.568632316e-14
[11,] 85 1.371398506e-13 1.928261737e-13
[12,] 86 4.216488998e-13 6.144750736e-13
[13,] 87 1.205063898e-12 1.819538971e-12
[14,] 88 3.22684756e-12 5.046386531e-12
[15,] 89 8.149328924e-12 1.319571546e-11
[16,] 90 1.951922687e-11 3.271494232e-11
[17,] 91 4.455253589e-11 7.726747822e-11
[18,] 92 9.730631824e-11 1.745737965e-10
[19,] 93 2.040930538e-10 3.786668503e-10
[20,] 94 4.123859188e-10 7.910527691e-10
[21,] 95 8.049689046e-10 1.596021674e-09
[22,] 96 1.521708889e-09 3.117730563e-09
[23,] 97 2.792061784e-09 5.909792347e-09
[24,] 98 4.982252249e-09 1.08920446e-08
[25,] 99 8.661951043e-09 1.955399564e-08
[26,] 100 1.469616449e-08 3.425016013e-08
[27,] 101 2.436887984e-08 5.861903997e-08
[28,] 102 3.95456994e-08 9.816473937e-08
[29,] 103 6.288315778e-08 1.610478971e-07
[30,] 104 9.809256193e-08 2.591404591e-07
[31,] 105 1.502659394e-07 4.094063985e-07
[32,] 106 2.262709568e-07 6.356773553e-07
[33,] 107 3.352204269e-07 9.708977822e-07
[34,] 108 4.89020241e-07 1.459918023e-06
[35,] 109 7.029972444e-07 2.162915268e-06
[36,] 110 9.966057708e-07 3.159521038e-06
[37,] 111 1.394208334e-06 4.553729373e-06
[38,] 112 1.925922459e-06 6.479651831e-06
[39,] 113 2.62852195e-06 9.108173782e-06
[40,] 114 3.546377208e-06 1.265455099e-05
[41,] 115 4.73241567e-06 1.738696666e-05
[42,] 116 6.249080252e-06 2.363604691e-05
[43,] 117 8.169260964e-06 3.180530787e-05
[44,] 118 1.057717281e-05 4.238248068e-05
[45,] 119 1.356915178e-05 5.595163246e-05
[46,] 120 1.725434028e-05 7.320597274e-05
[47,] 121 2.175523392e-05 9.496120666e-05
[48,] 122 2.720806277e-05 0.0001221692694
[49,] 123 3.376298279e-05 0.0001559322522
[50,] 124 4.158405603e-05 0.0001975163083
[51,] 125 5.08490024e-05 0.0002483653107
[52,] 126 6.174871013e-05 0.0003101140208
[53,] 127 7.448649723e-05 0.000384600518
[54,] 128 8.927712172e-05 0.0004738776397
[55,] 129 0.0001063455439 0.0005802231836
[56,] 130 0.0001259254492 0.0007061486328
[57,] 131 0.0001482575467 0.0008544061794
[58,] 132 0.0001735876611 0.001027993841
[59,] 133 0.000202164644 0.001230158484
[60,] 134 0.0002342381305 0.001464396615
[61,] 135 0.0002700561739 0.001734452789
[62,] 136 0.0003098627913 0.00204431558
[63,] 137 0.0003538954567 0.002398211037
[64,] 138 0.0004023825774 0.002800593614
[65,] 139 0.0004555409911 0.003256134605
[66,] 140 0.0005135735197 0.003769708125
[67,] 141 0.0005766666157 0.004346374741
[68,] 142 0.0006449881318 0.004991362873
[69,] 143 0.0007186852474 0.00571004812
[70,] 144 0.0007978825768 0.006507930697
[71,] 145 0.0008826804836 0.00739061118
[72,] 146 0.0009731536228 0.008363764803
[73,] 147 0.001069349725 0.009433114528
[74,] 148 0.001171288633 0.01060440316
[75,] 149 0.00127896161 0.01188336477
[76,] 150 0.001392330902 0.01327569567
[77,] 151 0.001511329574 0.01478702525
[78,] 152 0.001635861612 0.01642288686
[79,] 153 0.001765802276 0.01818868913
[80,] 154 0.0019009987 0.02008968783
[81,] 155 0.002041270724 0.02213095856
[82,] 156 0.002186411947 0.02431737051
[83,] 157 0.002336190974 0.02665356148
[84,] 158 0.002490352849 0.02914391433
[85,] 159 0.002648620644 0.03179253497
[86,] 160 0.002810697192 0.03460323217
[87,] 161 0.002976266928 0.03757949909
[88,] 162 0.003144997836 0.04072449693
[89,] 163 0.003316543459 0.04404104039
[90,] 164 0.00349054497 0.04753158536
[91,] 165 0.003666633263 0.05119821862
[92,] 166 0.003844431065 0.05504264969
[93,] 167 0.004023555033 0.05906620472
[94,] 168 0.004203617829 0.06326982255
[95,] 169 0.004384230146 0.06765405269
[96,] 170 0.004565002691 0.07221905538
[97,] 171 0.00474554808 0.07696460346
[98,] 172 0.004925482663 0.08189008613
[99,] 173 0.005104428255 0.08699451438
[100,] 174 0.005282013762 0.09227652814
[101,] 175 0.005457876702 0.09773440485
[102,] 176 0.005631664612 0.1033660695
[103,] 177 0.005803036336 0.1091691058
[104,] 178 0.005971663192 0.115140769
[105,] 179 0.00613723002 0.121277999
[106,] 180 0.006299436105 0.1275774351
[107,] 181 0.006457995976 0.1340354311
[108,] 182 0.006612640088 0.1406480712
[109,] 183 0.006763115387 0.1474111866
[110,] 184 0.006909185754 0.1543203723
[111,] 185 0.007050632352 0.1613710047
[112,] 186 0.007187253849 0.1685582585
[113,] 187 0.007318866558 0.1758771251
[114,] 188 0.007445304472 0.1833224295
[115,] 189 0.00756641921 0.1908888488
[116,] 190 0.007682079887 0.1985709286
[117,] 191 0.007792172895 0.2063631015
[118,] 192 0.007896601627 0.2142597032
[119,] 193 0.007995286127 0.2222549893
[120,] 194 0.008088162683 0.230343152
[121,] 195 0.008175183375 0.2385183353
[122,] 196 0.008256315567 0.2467746509
[123,] 197 0.008331541368 0.2551061923
[124,] 198 0.008400857051 0.2635070493
[125,] 199 0.008464272454 0.2719713218
[126,] 200 0.008521810344 0.2804931321
[127,] 201 0.008573505773 0.2890666379
[128,] 202 0.008619405417 0.2976860433
[129,] 203 0.008659566903 0.3063456102
[130,] 204 0.008694058136 0.3150396684
[131,] 205 0.008722956616 0.323762625
[132,] 206 0.008746348769 0.3325089737
[133,] 207 0.00876432927 0.341273303
[134,] 208 0.008777000386 0.3500503034
[135,] 209 0.00878447132 0.3588347747
[136,] 210 0.008786857574 0.3676216323
[137,] 211 0.008784280324 0.3764059126
[138,] 212 0.008776865814 0.3851827784
[139,] 213 0.008764744769 0.3939475232
[140,] 214 0.008748051821 0.402695575
[141,] 215 0.008726924967 0.4114225
[142,] 216 0.008701505041 0.420124005
[143,] 217 0.008671935207 0.4287959402
[144,] 218 0.008638360485 0.4374343007
[145,] 219 0.008600927288 0.446035228
[146,] 220 0.008559782991 0.454595011
[147,] 221 0.008515075522 0.4631100865
[148,] 222 0.008466952974 0.4715770395
[149,] 223 0.008415563246 0.4799926027
[150,] 224 0.008361053697 0.4883536564
[151,] 225 0.008303570837 0.4966572273
[152,] 226 0.008243260029 0.5049004873
[153,] 227 0.008180265217 0.5130807525
[154,] 228 0.008114728674 0.5211954812
[155,] 229 0.008046790778 0.529242272
[156,] 230 0.007976589795 0.5372188618
[157,] 231 0.007904261691 0.5451231235
[158,] 232 0.007829939962 0.5529530634
[159,] 233 0.007753755478 0.5607068189
[160,] 234 0.007675836346 0.5683826553
[161,] 235 0.007596307791 0.575978963
[162,] 236 0.00751529205 0.5834942551
[163,] 237 0.007432908282 0.5909271634
[164,] 238 0.00734927249 0.5982764359
[165,] 239 0.007264497462 0.6055409333
[166,] 240 0.007178692717 0.612719626
[167,] 241 0.00709196447 0.6198115905
[168,] 242 0.007004415597 0.6268160061
[169,] 243 0.006916145628 0.6337321517
[170,] 244 0.006827250727 0.6405594025
[171,] 245 0.006737823704 0.6472972262
[172,] 246 0.006647954016 0.6539451802
[173,] 247 0.006557727789 0.660502908
[174,] 248 0.006467227837 0.6669701358
[175,] 249 0.006376533697 0.6733466695
[176,] 250 0.006285721659 0.6796323912
[177,] 251 0.006194864813 0.685827256
[178,] 252 0.006104033092 0.6919312891
[179,] 253 0.006013293322 0.6979445824
[180,] 254 0.005922709276 0.7038672917
[181,] 255 0.005832341735 0.7096996334
[182,] 256 0.005742248541 0.7154418819
[183,] 257 0.005652484669 0.7210943666
[184,] 258 0.005563102286 0.7266574689
[185,] 259 0.00547415082 0.7321316197
[186,] 260 0.00538567703 0.7375172968
[187,] 261 0.005297725075 0.7428150218
[188,] 262 0.005210336583 0.7480253584
[189,] 263 0.005123550728 0.7531489091
[190,] 264 0.005037404297 0.7581863134
[191,] 265 0.004951931765 0.7631382452
[192,] 266 0.004867165368 0.7680054106
[193,] 267 0.004783135175 0.7727885457
[194,] 268 0.004699869157 0.7774884149
[195,] 269 0.004617393267 0.7821058082
[196,] 270 0.0045357315 0.7866415397
[197,] 271 0.004454905973 0.7910964456
[198,] 272 0.00437493699 0.7954713826
[199,] 273 0.00429584311 0.7997672257
[200,] 274 0.004217641216 0.803984867
[201,] 275 0.004140346583 0.8081252135
[202,] 276 0.004063972939 0.8121891865
[203,] 277 0.003988532533 0.816177719
[204,] 278 0.003914036196 0.8200917552
[205,] 279 0.003840493399 0.8239322486
[206,] 280 0.003767912319 0.8277001609
[207,] 281 0.003696299895 0.8313964608
[208,] 282 0.003625661879 0.8350221227
[209,] 283 0.003556002902 0.8385781256
[210,] 284 0.003487326519 0.8420654521
[211,] 285 0.003419635266 0.8454850874
[212,] 286 0.003352930707 0.8488380181
[213,] 287 0.003287213488 0.8521252316
[214,] 288 0.003222483383 0.855347715
[215,] 289 0.003158739337 0.8585064543
[216,] 290 0.003095979514 0.8616024338
[217,] 291 0.003034201342 0.8646366352
[218,] 292 0.002973401549 0.8676100367
[219,] 293 0.002913576209 0.8705236129
[220,] 294 0.002854720778 0.8733783337
[221,] 295 0.002796830131 0.8761751638
[222,] 296 0.002739898601 0.8789150624
[223,] 297 0.002683920011 0.8815989824
[224,] 298 0.002628887706 0.8842278701
[225,] 299 0.002574794592 0.8868026647
[226,] 300 0.002521633158 0.8893242979
[227,] 301 0.002469395511 0.8917936934
[228,] 302 0.002418073403 0.8942117668
[229,] 303 0.002367658259 0.8965794251
[230,] 304 0.002318141201 0.8988975663
[231,] 305 0.002269513074 0.9011670793
[232,] 306 0.002221764471 0.9033888438
[233,] 307 0.002174885753 0.9055637296
[234,] 308 0.002128867072 0.9076925966
[235,] 309 0.002083698394 0.909776295
[236,] 310 0.002039369515 0.9118156645
[237,] 311 0.001995870081 0.9138115346
[238,] 312 0.001953189607 0.9157647242
[239,] 313 0.001911317494 0.9176760417
[240,] 314 0.001870243043 0.9195462848
[241,] 315 0.001829955471 0.9213762402
[242,] 316 0.00179044393 0.9231666842
[243,] 317 0.001751697513 0.9249183817
[244,] 318 0.001713705273 0.926632087
[245,] 319 0.001676456233 0.9283085432
[246,] 320 0.0016399394 0.9299484826
[247,] 321 0.001604143771 0.9315526264
[248,] 322 0.001569058349 0.9331216847
[249,] 323 0.001534672151 0.9346563569
[250,] 324 0.001500974214 0.9361573311
[251,] 325 0.001467953607 0.9376252847
[252,] 326 0.001435599441 0.9390608841
[253,] 327 0.001403900872 0.940464785
[254,] 328 0.001372847109 0.9418376321
[255,] 329 0.001342427424 0.9431800595
[256,] 330 0.001312631155 0.9444926907
[257,] 331 0.001283447714 0.9457761384
[258,] 332 0.00125486659 0.947031005
[259,] 333 0.001226877356 0.9482578823
[260,] 334 0.001199469671 0.949457352
[261,] 335 0.00117263329 0.9506299853
[262,] 336 0.00114635806 0.9517763434
[263,] 337 0.001120633931 0.9528969773
[264,] 338 0.001095450952 0.9539924282
[265,] 339 0.001070799283 0.9550632275
[266,] 340 0.001046669188 0.9561098967
[267,] 341 0.001023051045 0.9571329478
[268,] 342 0.0009999353442 0.9581328831
[269,] 343 0.0009773126913 0.9591101958
[270,] 344 0.0009551738092 0.9600653696
[271,] 345 0.0009335095392 0.9609988791
[272,] 346 0.0009123108424 0.96191119
[273,] 347 0.0008915688013 0.9628027588
[274,] 348 0.0008712746199 0.9636740334
[275,] 349 0.0008514196251 0.964525453
[276,] 350 0.0008319952673 0.9653574483
[277,] 351 0.0008129931206 0.9661704414
[278,] 352 0.000794404883 0.9669648463
[279,] 353 0.0007762223771 0.9677410687
[280,] 354 0.0007584375496 0.9684995062
[281,] 355 0.0007410424716 0.9692405487
[282,] 356 0.0007240293383 0.969964578
[283,] 357 0.0007073904684 0.9706719685
[284,] 358 0.0006911183043 0.9713630868
[285,] 359 0.0006752054111 0.9720382922
[286,] 360 0.0006596444764 0.9726979367
[287,] 361 0.0006444283092 0.973342365
[288,] 362 0.0006295498398 0.9739719149
[289,] 363 0.0006150021182 0.974586917
[290,] 364 0.0006007783141 0.9751876953
[291,] 365 0.0005868717153 0.975774567
[292,] 366 0.0005732757271 0.9763478427
[293,] 367 0.0005599838709 0.9769078266
[294,] 368 0.0005469897836 0.9774548164
[295,] 369 0.0005342872162 0.9779891036
[296,] 370 0.0005218700326 0.9785109736
[297,] 371 0.0005097322084 0.9790207058
[298,] 372 0.00049786783 0.9795185737
[299,] 373 0.0004862710928 0.9800048448
[300,] 374 0.0004749363003 0.9804797811
[301,] 375 0.0004638578628 0.9809436389
[302,] 376 0.0004530302958 0.9813966692
[303,] 377 0.0004424482188 0.9818391174
[304,] 378 0.0004321063542 0.9822712238
[305,] 379 0.0004219995253 0.9826932233
[306,] 380 0.0004121226555 0.983105346
[307,] 381 0.0004024707666 0.9835078167
[308,] 382 0.0003930389775 0.9839008557
[309,] 383 0.0003838225028 0.9842846782
[310,] 384 0.0003748166514 0.9846594949
[311,] 385 0.0003660168248 0.9850255117
[312,] 386 0.0003574185161 0.9853829302
[313,] 387 0.0003490173084 0.9857319475
[314,] 388 0.0003408088733 0.9860727564
[315,] 389 0.0003327889696 0.9864055454
[316,] 390 0.000324953442 0.9867304988
[317,] 391 0.0003172982194 0.987047797
[318,] 392 0.0003098193137 0.9873576163
[319,] 393 0.0003025128184 0.9876601292
[320,] 394 0.0002953749073 0.9879555041
[321,] 395 0.000288401833 0.9882439059
[322,] 396 0.0002815899255 0.9885254958
[323,] 397 0.000274935591 0.9888004314
[324,] 398 0.0002684353105 0.9890688667
[325,] 399 0.0002620856384 0.9893309524
[326,] 400 0.0002558832014 0.9895868356

at least I have a few photos to share
at least 1 of 38


at least 2 of 38


will update
https://sites.google.com/view/krapstuff/coupon-collecting/coupon-collecting-at-least-2
for those that want it

Sally
Last edited by: mustangsally on Jul 6, 2018
I Heart Vi Hart
Ace
Ace
  • Threads: 6
  • Posts: 43
Joined: Aug 15, 2013
July 6th, 2018 at 11:01:58 AM permalink
Quote: mustangsally

I can only think of fun dice games to play with the distribution data
other than that, hard to imagine what good knowing the mean for at least 2 is.

True, there probably isn't much of a practical use for knowing the mean of 2 or more. However, these problems are still useful since you sometimes learn things that are applicable for other scenarios.
Ace2
Ace2
  • Threads: 32
  • Posts: 2672
Joined: Oct 2, 2017
September 23rd, 2018 at 7:49:33 PM permalink
Quote: Ace2

Can someone run the number for 1000 coupons, getting at least 2 of each ? I’d be interested to know if there’s a limit. .

Sure Ace, it would be my pleasure.

The answer of 9,862.97 is given by the integral from zero to infinity of :

(1 - ((x/1000) + 1) / e^(x/1000))^999 * (x/1000) / e^(x/1000) * x dx

I could probably give a few more digits but I’m very confident up to those (and can’t imagine any need for more). I had to do this in excel, and couldn’t really space more than 0.1, which requires about 300,000 lines. Unfortunately when I plug the equation into an online integral site it times out.

This is very close to the number given by ThatDonGuy.
Last edited by: Ace2 on Sep 23, 2018
It’s all about making that GTA
Ace2
Ace2
  • Threads: 32
  • Posts: 2672
Joined: Oct 2, 2017
February 8th, 2020 at 9:16:53 AM permalink
Quote: Ace

I just found this old thread while searching for something else.

In case you didn't know the answer is closely approximated by 38 x (ln 38 + γ) = 160.16, where γ is the Euler constant .57721...

This is a version of the coupon collectors problem.

I just learned that the formula for the Nth harmonic number can be further refined by adding the term 1/2n - 1/12n^2 + 1/120n^4.

So the formula for the expected number of roulette spins to get all 38 numbers becomes:

38 * ( Ln(38) + γ + 1/(2*38) - 1/(12*38^2) + 1/(120*38^4) ) = 160.6602765.

This is accurate to at least 10 digits which is as far as my iPhone calculator goes.
It’s all about making that GTA
Ace2
Ace2
  • Threads: 32
  • Posts: 2672
Joined: Oct 2, 2017
March 23rd, 2020 at 8:38:22 AM permalink
The exact answer for expected spins to get all 38 roulette numbers is the integral from zero to infinity of:

1-(1-1/e^(x/38))^38 dx

2053580969474233 / 12782132672400 = 160.66
It’s all about making that GTA
  • Jump to: