The Chow-Robbins Problem

Summary

Theoretical analysis produced no useful additional data or insight. Prior analysis by others had suggested EV(0,0)=0.79295350640… [1]. Machine calculation to higher precision was performed and for a larger maximum number of tosses n; the results confirmed previous calculation, but suggest only EV(0,0)=0.7929535064… with uncertainty over the next digit, as the ratio of deltas between successive EV(0,0) estimates with increasing n does not as yet seem to be converging sufficiently.

Introduction

The Chow-Robbins problem came to my attention from here [1]. The problem is interesting because while being very simple to describe, there is intruiging complexity in determining the solution.

Note that this case is a subset of the more general optimal stopping problem, where each step could have many possible outcomes each with different probabilities themselves, such as rolling a weighted die.

Limited game solution

The following table shows the final score S(h,t) achieved if the player decides to stop at any number of tosses up to six, where the tosses have generated h heads and t tails:

Final score on stopping at any position up to 6 tosses

The player must therefore decide at any time whether to continue tossing or stop, by considering whether they would on average improve their final score by continuing, or be better off stopping at this point. For a game with limited maximum number of tosses n, the expected value EV(h,t) at each position can then therefore be determined:

Using this rule, the expected values for all positions in our limited game from above become:

Expected Value EV(h,t) for all positions with optimal stopping for a maximum of 6 tosses

Full problem solution

To consider a game with an unlimited number of tosses, the following assumption is made: that EV(h,t) for any position is a mininum of 0.5, based on the justification that at any such position the player could decide to continue tossing forever until this value was achieved with probability 1.

In the full problem there is no limit on the number of tosses. In order to estimate EV(h,t), the following assumption is made: that in any case where EV(h,t)<0.5 the player would continue to toss until h/(h+t)=0.5 which will occur with probability 1; EV(h,t) can therefore be assumed to have a minimum value of 0.5 in any position.

In order to make an estimation for EV(0,0) for the unlimited game, we can therefore consider the position for up to n tosses; Using n=6 as above, the previous table now becomes:

Expected Value EV(h,t) with optimal stopping for unlimited n, calculated to maximum of N=6

Thus it can be determined that EV(0,0)>=0.777 for the unlimited case by calculation for n=6. As n increases, the estimate for EV(0,0) appears to tend to a limit [1].

Note that while this example suggests a simple rule of "stop when h>t", when the maximum number of tosses is increased it is found that this is no longer sufficient.

Analysis

Initial theoretical examination of the problem suggested a possible solution in the form of a summation based on factors from increasing series of binomial expansion coefficients; However on further examination of the pseudo-chaotic determination of stopping points, this seemed less viable so the analysis was re-focussed on creation of a multiple-precision fixed point implementation for large numbers of tosses. Specifically, the primary goal became to enable higher accuracy result calculation; this would then also facilitate further examination of whether the ratio of the difference between successive EV(0,0) estimates tends towards a constant.

Computation

Implementions of the Chow-Robbins computation were created in C while examining the problem; initially starting with a basic double-precision floating point implementation. Subsequently a multiple-precision fixed point implementation was created and optimised, with several goals:

• to validate and compare with existing results from [1]
• to validate the apparent convergence using higher-accuracy results
• to take this further for higher n and see if the trend continues

In order to achieve this, the following optimisations were implemented:

Implementation steps:

1. Double-precision floating point implementation
2. Fixed-point arbitrary-precision model for maximum n=2ⁱ tosses
3. Optimisations:
1. inline calculation functions for speed
2. fixed precision function calculations optimised for this application
3. compiler optimisation (for speed, calculations validated against previous to i=20)
4. modified calculation from diagonals to vertical method (calculation by column, with decreasing t)
5. reduced range of each column calculated to none below machine precision
6. reduced range of each column calculated to avoid calculation where h is greater than the known stop point from columns with greater t
7. dual (ping-pong) column segment buffers to (dramatically) reduce memory requirement
8. ability to save/resume calculation

In particular, memory optimisation was performed to limit the buffer sizes required for the calculation; By examination of the column buffer sizes required for calculation where i<=20, it was determined that a buffer size of 11*1.41ⁱ values was sufficient for calculation to 28 decimal places of accuracy for i<20, and for all i>=20 with an increasing spare margin. Using a pair of buffers, and with each value requiring 16 bytes, this becomes a total of 352*1.41ⁱ; For i=28 the memory required is only just over 5MB and therefore easily manageable.

In addition, with high i runs taking several days, the ability to automatically save current state and to resume from previous saved state was added to facilitate restart following any power-cut or interruption for other cause (e.g. machine needed for other purposes).

Results

The following results show the estimate for EV(0,0) as calculated using U32.96 bit precision (i.e. 96 bits of precision after the decimal point), which is equivalent to 28 decimal places. The rounding stratgies implemented should provide accuracy to this last bit, so at least 27 decimal places of calculation accuracy.

The PARI/GP calculation engine [3] was then used to calculate at high precision the difference between successive estimates, the ratio between successive differences, and thereby the estimated limit, where Limit=EV+Diff/(1/Ratio–1) as the final result provided that successive values of Ratio continue to tend towards a constant limit.

Machine calculation of EV(0,0) and limit estimation up to i=29

From the above, the following points are noted:

1. Agreement to the stated 14 digits of accuracy with [1] for calculation of EV(0,0), plus extension of these results to 28 digit accuracy (note when comparing that n is used on this page to represent the maximum number of tosses, while on [1] it is defined as the maximum number of heads where calculation starts at h=t, and is therefore half the value for the same test case).
2. The results suggest EV(0,0)=0.7929535064… Note that this is one less digit of precision than in the conjecture from [1] ("the expected value ≈0.79295350640…, with the next digit probably being not more than 1 different from 7") as despite the increased precision and larger n computation, the ratio of deltas between successive EV(0,0) estimates with increasing n does not as yet seem to be converging sufficiently.
3. Additional precision on calculation has not provided increase accuracy over the current estimate from [1]. The additional precision would likely be useful for longer runs for much higher i as would be required for increase accuracy of calculation.
4. Calculation for i=29 at 28 digit precision will likely be the last result provided as the calculation at this precision took 32 days, and for each increment to i the calculation time increases by a factor of approximately 2.8.

Phil W.
Sep 2013.

References

[1] "The expected value of sn/n ≈0.79295350640…", J. D. A. Wiseman
(http://www.jdawiseman.com/papers/easymath/coin-stopping.html)

[2] "On optimal stopping rules for S_{n}/n", Y. S. Chow and Herbert Robbins, Illinois J. Math. Volume 9, Issue 3 (1965)

[3] PARI/GP calculation engine
(http://pari.math.u-bordeaux.fr/)