Roll a ten-sided die. You succeed if you roll a 1.
Otherwise roll again, this time you succeed if you roll a 1 or a 2.
Otherwise roll again, this time you succeed if you roll a 1, 2 or 3.
Otherwise continue the pattern until you eventually win.
Let x = number of tries to success.
What is the expected value of x?
Extend to an n-sided die and give a formula for E(n,x).
For any value of n there is a maximum k such that P(x≤k)≤1/2. Find a formula for this k in terms of n.
This might make an interesting casino game but I've never seen it before.
The probability of succeeding on the first try with a 10-sided die is 1/10.
The probability of succeeding on the second try (if there is a second try) is 2/10. Since this is indeed a conditional probability, its absolute probability is (9/10)*(2/10). The probability of succeeding on either the first or second try is therefore 1/10 + (9/10)*(2/10). The probability of continuing on to a third try is therefore 1 minus this value.
The result is tabulated in:
conditional absolute cumulative
roll prob probability probability
#
1 1//10 1//10 1//10
2 1//5 9//50 7//25
3 3//10 27//125 62//125
4 2//5 126//625 436//625
5 1//2 189//1250 1061//1250
6 3//5 567//6250 2936//3125
7 7//10 1323//31250 30683//31250
8 4//5 1134//78125 155683//156250
9 9//10 5103//1562500 1561933//1562500
10 1 567//1562500 1
The expected number of tries is the sum of the column 1 entries multiplied by the column 3 entries. That comes out to 5719087/1562500 or 3.66021568.
For the above:
4 kill "progprob.txt":open "progprob.txt" for output as #2
5 Overprob=0
10 for Turn=1 to 10
20 Pc=Turn//10
30 Probthisturn=(1-Overprob)*Pc
40 Overprob=Overprob+Probthisturn
45 Expect=Expect+Turn*Probthisturn
50 print Turn,Pc,Probthisturn,Overprob
55 print #2,Turn,Pc,Probthisturn,Overprob
60 next
70 print #2,Expect
170 close #2
For a formula for any n, I think I'd have to have a Sigma within a Sigma. Instead, I show a table of these values:
The values for n = 2 to 25 are (each line showing n, rational exp. value, decimal exp. value):
2 3//2 1.5
3 17//9 1.8888888888888888888
4 71//32 2.21875
5 1569//625 2.5104
6 899//324 2.774691358024691358
7 355081//117649 3.0181387007114382612
8 425331//131072 3.24501800537109375
9 16541017//4782969 3.4583157448856557506
10 5719087//1562500 3.66021568
11 99920609601//25937424601 3.8523720507373591728
12 144619817//35831808 4.0360736750989511888
13 98139640241473//23298085122481 4.2123479129525201437
14 485223422289//110730297608 4.382029424383519083
15 21844512889051//4805419921875 4.5458072851472283696
16 2648261961071387//562949953421312 4.7042582470726781451
17 236389784118231290049//48661191875666868481 4.857870820801627336
18 458182173298217//91507169819844 5.0070630989928926843
19 536484538620663729658993//104127350297911241532841 5.1521962009574483822
20 3387894135040576041//640000000000000000 5.293584586000900064
21 4700454869700411483409//865405750887126927009 5.4315040833527833121
22 29957278636692290181797//5381999959460480073608 5.5661982278601438413
23 5172803056875215165371121461737//907846434775996175406740561329 5.6978833189465163465
24 31377903334268753950903//5385144351531158470656 5.8267525039225870515
25 33838768480593780243940600998001//5684341886080801486968994140625 5.9529791062452591332
from
4 kill "progprb2.txt":open "progprb2.txt" for output as #2
5 for N=2 to 25
6 Overprob=0:Expect=0
10 for Turn=1 to N
20 Pc=Turn//N
30 Probthisturn=(1-Overprob)*Pc
40 Overprob=Overprob+Probthisturn
45 Expect=Expect+Turn*Probthisturn
50 ' print Turn,Pc,Probthisturn,Overprob
55 ' print #2,Turn,Pc,Probthisturn,Overprob
60 next
70 print #2,N,Expect,Expect/1
80 next N
170 close #2
For maximum k:
Listed are n, the max k asked for, the prob. that P <= k, then max k + 1 and its probability.
The probability in each case is given in rational and decimal form.
UBASIC uses a double slash ( // ) as the separator of numerator and denominator.
2 1 1//2 0.5 2 1 1.0
3 1 1//3 0.3333333333333333333 2 7//9 0.7777777777777777777
4 1 1//4 0.25 2 5//8 0.625
5 1 1//5 0.2 2 13//25 0.52
6 2 4//9 0.4444444444444444444 3 13//18 0.7222222222222222221
7 2 19//49 0.3877551020408163264 3 223//343 0.6501457725947521865
8 2 11//32 0.34375 3 151//256 0.58984375
9 2 25//81 0.3086419753086419753 3 131//243 0.5390946502057613168
10 3 62//125 0.496 4 436//625 0.6976
11 3 611//1331 0.4590533433508640119 4 9601//14641 0.6557612184960043712
12 3 41//96 0.4270833333333333333 4 89//144 0.6180555555555555555
13 3 877//2197 0.3991807009558488848 4 16681//28561 0.5840481775848184586
14 3 257//686 0.3746355685131195334 4 2657//4802 0.5533111203665139524
15 3 397//1125 0.3528888888888888888 4 8867//16875 0.5254518518518518518
16 3 683//2048 0.33349609375 4 4097//8192 0.5001220703125
17 4 39841//83521 0.4770177560134576932 5 895697//1419857 0.6308360630683230775
18 4 997//2187 0.4558756287151348879 5 11948//19683 0.6070212874053751968
19 4 56881//130321 0.4364684126119351447 5 1447939//2476099 0.5847661987666890539
20 4 2093//5000 0.4186 5 11279//20000 0.56395
21 4 8689//21609 0.4021009764449997685 5 247069//453789 0.5444578868152379189
22 4 11327//29282 0.3868246704460077863 5 338969//644204 0.5261826998900969257
23 4 104281//279841 0.3726437512730443358 5 3276263//6436343 0.5090255444745564367
24 5 163531//331776 0.4928958092206790122 6 274123//442368 0.6196718569155092592
25 5 933029//1953125 0.477710848 6 29446301//48828125 0.60306024448
26 5 344111//742586 0.4633954855060558641 6 2834434//4826809 0.5872272965431198955
27 5 2151769//4782969 0.4498814439315830815 6 24628321//43046721 0.5721300119467868412
28 5 470173//1075648 0.4371067486761468435 6 8398847//15059072 0.5577267311026868056
29 5 8717549//20511149 0.4250151466404929338 6 323570521//594823321 0.5439775300941840509
30 5 1861//4500 0.4135555555555555555 6 2986//5625 0.5308444444444444444
31 5 11528431//28629151 0.4026815534976919154 6 459985681//887503681 0.5182915754013644479
32 5 1645639//4194304 0.3923509120941162109 6 33976219//67108864 0.5062851160764694213
33 6 7889009//15944049 0.4947933238288467377 7 316722577//526153617 0.60195837635000046
34 6 11677429//24137569 0.4837864575343109324 7 242126783//410338673 0.5900657162772469169
35 6 173986949//367653125 0.4732366928745675695 7 1063600921//1838265625 0.5785893542996540556
36 6 875093//1889568 0.4631180248607089027 7 38604673//68024448 0.5675117422489043938
37 6 1163316169//2565726409 0.4534061640085024357 7 52859569933//94931877133 0.5568158086555425154
38 6 20892061//47045881 0.4440784305856659374 7 488487529//893871739 0.5464850354777801068
39 6 56705683//130323843 0.4351136499251330395 7 2726848757//5082629877 0.5365035076308783913
40 6 21836393//51200000 0.42649205078125 7 1079000969//2048000000 0.5268559418945312499
41 6 1986470641//4750104241 0.4181951679826303836 7 100790731481//194754273881 0.5175277002782788547
42 6 1303028//3176523 0.4102057501236414784 7 9691663//19059138 0.5085047917697012319
43 7 135847837987//271818611107 0.4997738654971060697 8 6929223218401//11688200277601 0.5928391928464816846
44 7 4902133597//9977431552 0.4913221976468839422 8 64074065477//109751747072 0.5838090708019959527
45 7 4011862009//8303765625 0.4831376739393460421 8 214869019333//373669453125 0.5750243096834623013
46 7 3236005819//6809650894 0.475208769050297808 8 88722714137//156621970562 0.5664768092154634066
47 7 236858733263//506623120463 0.4675245240417297681 8 13290475560961//23811286661761 0.558158647609094914
48 7 625220341//1358954496 0.4600745226130073452 8 4485056201//8153726976 0.550062102177506121
49 7 43876078567//96889010407 0.4528488667877864704 8 2574031304503//4747561509943 0.5421796640469233732
50 7 544236026//1220703125 0.4458381524992 8 16311769046//30517578125 0.534504048099328
from
4 kill "progprb3.txt":open "progprb3.txt" for output as #2
5 for N=2 to 50
6 Overprob=0:Expect=0
10 for Turn=1 to N
20 Pc=Turn//N
30 Probthisturn=(1-Overprob)*Pc
35 PrevO=Overprob
40 Overprob=Overprob+Probthisturn
45 if Overprob>1//2 then cancel for:goto 70
50 ' print Turn,Pc,Probthisturn,Overprob
55 ' print #2,Turn,Pc,Probthisturn,Overprob
60 next
70 print #2,N,Turn-1,PrevO,PrevO/1,Turn,Overprob,Overprob/1
80 next N
170 close #2
|
|
Posted by Charlie
on 2016-06-15 15:57:28 |
computer exploration - solution for first part only
