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

 Progressive probability (Posted on 2016-06-15)
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.

 No Solution Yet Submitted by Jer No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer exploration - solution for first part only Comment 1 of 1
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       cumulativeroll     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

 Search: Search body:
Forums (0)