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

Home > Probability
Progressive probability (Posted on 2016-06-15) Difficulty: 4 of 5
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.)
Some Thoughts 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       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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information