(Reference: http://probabilitynet.com/nasty.htm . Or click here for Gary Fuller’s web site:
Note: to print set the orientation to landscape.
Introduction.
Imagine a fair coin is tossed an infinite number of times. In ‘Dr Stern’s Nasty Problem’ a method is described for mapping an infinite series of tosses to a point in the half closed unit interval [0 … 1); if T is a point in this interval, then 0 £ T < 1. An infinite series of tosses is mapped to this interval by representing the series as an infinite binary fraction e.g., .01010000…., where a ‘0’ represents tails and a ‘1’ represents heads; the binary fraction is then converted to a decimal fraction, see equation (3) below. Dr Stern’s Nasty Problem is to generalise the method so it can be used with a biased coin.
There are two problems with this formulation of ‘Dr Stern’s Nasty Problem’:
(1) Some binary numbers can represent two different infinite sequences of tosses e.g., the sequence of heads followed by an infinite number of tails can be represented by the number 0.10000…, while the sequence of tails followed by an infinite number of heads can be represented by 0.01111…. However 0.10000… and 0.01111… are the same number.
(2) The sequence of an infinite number of heads can be represented by 0.11111…., which is the same number as 1.00000… Therefore an infinite series of coin tosses should be represented by a point in the closed unit interval [0 … 1], which includes 1 rather than the half closed interval [0 … 1). If T is the number which represents an infinite series of tosses, then 0 £ T £ 1.
The Meaning of T.
Let 0 £ T £ 1 be the decimal number and B the sequence of digits in the binary number which represent a given infinite series of coin tosses.
Let S be the decimal number which represents a repeated infinite series of coin tosses and let Probability() be the objective chance function.
Then T = Probability(S < T).
Calculation of T.
Let L_{i} and U_{i} be the lower
and upper bounds of T after i tosses, such that L_{i}
£
T £ U_{i}.
Let the probability that the coin lands heads = h, where 0 £ h £ 1, and let p_{i}(T) represent the outcome of the ith toss.
Before the coin is tossed, let L_{0} = 0 and U_{0} = 1.
(1) After each toss two situations are possible:
Either:
p_{i}(T) = 0 
L_{i}_{ – 1} £ T £ L_{i}_{ – 1} + (U_{i}_{ – 1}  L_{i}_{ – 1} )(1 – h) 
L_{i} = L_{i }_{ 1} 
U_{i} = L_{i}_{ – 1} + (U_{i}_{ – 1}  L_{i}_{ – 1} )(1 – h) 
Or:
p_{i}(T) = 1 
L_{i}_{ – 1} + (U_{i}_{ – 1}  L_{i}_{ – 1} )(1 – h) £ T £ U_{i}_{ – 1} 
L_{i} = L_{i}_{ – 1} + (U_{i}_{ – 1}  L_{i}_{ – 1} )(1 – h) 
U_{i} = U_{i }_{ 1} 
For a given value of T, if T = L_{i}_{ – 1} + (U_{i}_{ – 1}  L_{i}_{ – 1} )(1 – h) then both situations are compatible with that value of T.
Providing 0 < h < 1, the quantity (U_{i}  L_{i}) will be reduced aafter each toss, since L_{i} £ T £ U_{i}; as i ® ¥, L_{i} ® T and U_{i} ® T.
If after the ith toss successive tosses are all ‘0’s then T = L_{i}.
If after the ith toss successive tosses are all ‘1’s then T = U_{i}.
If h = 0 or 1, (L_{i}  U_{i}) remains unchanged after each toss. However since only one sequence is possible T = L_{i} = 0.
The mean value of (L_{i}  U_{i})/(U_{i}_{ – 1}  L_{i}_{ – 1} ) = 1 – 2h + 2h^{2}. For h = 0 or 1, 1 – 2h + 2h^{2} = 1. The minimum value of 1 – 2h + 2h^{2} is 1/2 when h = 1/2. For h = 0, 1/2 or 1, but not for other values of h, all values of (L_{i}  U_{i})/(U_{i}_{ – 1}  L_{i}_{ – 1} ) are equal to 1 – 2h + 2h^{2}.
For a given value of T successive values of p_{i}(T) can be calculated from (1). For some given values of T there will be two possible sequences of successive values of p_{i}(T). If the set of values of p_{i}(T) is known the bounds of T after each toss can also be calculated from (1).
Equation (2) is another way of calculating T.
(2)

_{n}_{ = i } 
_{m}_{ = n} 
_{} 
_{} 
._{} 

L_{i} = 
S [ 
p_{n}(T)(1 – h) 
P 
((1 – p_{m}(T))(1 – h) + p_{m}(T)h) 
] 

(1 – p_{n}(T))(1
– h) + p_{n}(T)h 


^{n}^{ = 1} 
^{m}^{ = 1} 
^{} 
^{} 
As i ® ¥, L_{i} ® T.
If the coin is fair, h = 1/2 and equation (2) reduces to:

_{n}_{ = i} 
._{} 
L_{i} = 
S p_{n}(T) 1/2^{n} 


^{n}^{ = 1} 
As i ® ¥, L_{i} ® T.
Click here to see a table representing the mapping of coin tosses to the unit interval.