You're playing a game. You start with a box with one black marble and one white marble, and you sample twice with replacement. If you select the white marble both times, you win. If you select the black marble either time, you add another black marble and try again. On each round, you sample twice with replacement, winning if you select the white marble twice, otherwise adding another black marble and moving on to the next round.

What is the probability that you eventually win? Equivalently, if P(n) is the probability that you win on or before round n, what is the limit of P(n) as n -> infinity?

For the first few n:

   n prob(exactly n) P(n) -- on or before n
   1 0.250000000000 0.250000000000
   2 0.083333333333 0.333333333333
   3 0.041666666667 0.375000000000
   4 0.025000000000 0.400000000000
   5 0.016666666667 0.416666666667
   6 0.011904761905 0.428571428571
   7 0.008928571429 0.437500000000
   8 0.006944444444 0.444444444444
   9 0.005555555556 0.450000000000
  10 0.004545454545 0.454545454545
  11 0.003787878788 0.458333333333
  12 0.003205128205 0.461538461538
  13 0.002747252747 0.464285714286
  14 0.002380952381 0.466666666667
  15 0.002083333333 0.468750000000
  16 0.001838235294 0.470588235294
  17 0.001633986928 0.472222222222
  18 0.001461988304 0.473684210526
  19 0.001315789474 0.475000000000
  20 0.001190476190 0.476190476190
  21 0.001082251082 0.477272727273
  22 0.000988142292 0.478260869565
  23 0.000905797101 0.479166666667
  24 0.000833333333 0.480000000000
  25 0.000769230769 0.480769230769
  26 0.000712250712 0.481481481481
  27 0.000661375661 0.482142857143
  28 0.000615763547 0.482758620690
  29 0.000574712644 0.483333333333
  30 0.000537634409 0.483870967742
  31 0.000504032258 0.484375000000
  32 0.000473484848 0.484848484848
  33 0.000445632799 0.485294117647
  34 0.000420168067 0.485714285714
  35 0.000396825397 0.486111111111
  36 0.000375375375 0.486486486486
  37 0.000355618777 0.486842105263
  38 0.000337381916 0.487179487179
  39 0.000320512821 0.487500000000
  40 0.000304878049 0.487804878049

continued on, it goes through...

152618 0.000000000021 0.499996723868
152619 0.000000000021 0.499996723889
152620 0.000000000021 0.499996723911
152621 0.000000000021 0.499996723932
152622 0.000000000021 0.499996723954
152623 0.000000000021 0.499996723975
152624 0.000000000021 0.499996723997

so it does look like .5 is the answer.  But most people will weary of the game before the probability gets this close to .5.

DEFDBL A-Z
CLS
black = 1
cLoss = 1
DO
 w = cLoss * 1 / ((black + 1) * (black + 1))
 cWin = cWin + w
 cLoss = cLoss - w
 PRINT USING "######"; ct + 1;
 PRINT USING " #.############"; w; cWin 
 black = black + 1
 ct = ct + 1
 ' IF ct MOD 40 = 0 THEN DO: LOOP UNTIL INKEY$ > ""
LOOP

Posted by Charlie on 2004-11-01 14:25:51