Richard_Kennaway comments on Tricksy probability problem

[Richard_Kennaway]

I know that all of these sequences will eventually terminate.

Are you sure? I wrote a little program to compute the number of ways of stopping after n bits, and so find the probabilities, and I got this result. Columns are string length, number of ways of stopping at that length, probability of stopping at that length, and probability of stopping at at most that length. Expected length conditional on terminating appears to top out at about 1.4743 (sum of product of first and third column).

(ETA: Table edited to fix an error and add the second column.)

       1               1   0.500000   0.500000
       2               1   0.250000   0.750000
       4               1   0.062500   0.812500
       6               1   0.015625   0.828125
       8               2   0.007812   0.835938
      10               3   0.002930   0.838867
      12               6   0.001465   0.840332
      14              11   0.000671   0.841003
      16              22   0.000336   0.841339
      18              42   0.000160   0.841499
      20              84   0.000080   0.841579
      22             165   0.000039   0.841619
      24             330   0.000020   0.841638
      26             654   0.000010   0.841648
      28            1308   0.000005   0.841653
      30            2605   0.000002   0.841655
      32            5210   0.000001   0.841657
      34           10398   0.000001   0.841657
      36           20796   0.000000   0.841658
      38           41550   0.000000   0.841658
      40           83100   0.000000   0.841658
      42          166116   0.000000   0.841658
      44          332232   0.000000   0.841658
      46          664299   0.000000   0.841658
      48         1328598   0.000000   0.841658
      50         2656866   0.000000   0.841658
      52         5313732   0.000000   0.841658
      54        10626810   0.000000   0.841658
      56        21253620   0.000000   0.841658
      58        42505932   0.000000   0.841658
      60        85011864   0.000000   0.841658
      62       170021123   0.000000   0.841658
      64       340042246   0.000000   0.841658
      66       680079282   0.000000   0.841658
      68      1360158564   0.000000   0.841658
      70    2.720307e+09   0.000000   0.841658
      72    5.440613e+09   0.000000   0.841658
      74    1.088121e+10   0.000000   0.841658
      76    2.176241e+10   0.000000   0.841658
      78    4.352478e+10   0.000000   0.841658
      80    8.704957e+10   0.000000   0.841658
      82    1.740990e+11   0.000000   0.841658
      84    3.481981e+11   0.000000   0.841658
      86    6.963960e+11   0.000000   0.841658
      88    1.392792e+12   0.000000   0.841658
      90    2.785584e+12   0.000000   0.841658
      92    5.571168e+12   0.000000   0.841658
      94    1.114233e+13   0.000000   0.841658
      96    2.228467e+13   0.000000   0.841658
      98    4.456934e+13   0.000000   0.841658
     100    8.913867e+13   0.000000   0.841658

Eyeballing a plot of the fourth column doesn’t suggest it’s going to reach 1, but it might be some extraordinarily slow-growing thing.

The recurrence for computing the number of ways of stopping is a sort of generalised Fibonacci: each value is the sum of approximately the last half of the preceding values.

What prompts asking the question here?

[prase]

I have repeated the calculation and confirm the results.

What is interesting, the sequence in the second column satisfies a recurrence relation

• T(4n+2) = 2T(4n) - T(2n)

• T(4n) = 2T(4n-2)

• (and trivially T(2n+1) = T(2n), not included in the table).