Nasty Problem.

(Reference:  http://probabilitynet.com/nasty.htm .  Or click here for Gary Fuller’s web site:

# Doug Clark.  13th February 2004.  [email protected]   Last revised 24th February 2004.

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 Li and Ui be the lower and upper bounds of T after i tosses, such that Li £ T £  Ui.

Let the probability that the coin lands heads = h, where 0 £ h £ 1, and let pi(T) represent the outcome of the ith toss.

Before the coin is tossed, let L0 = 0 and U0 = 1.

(1) After each toss two situations are possible:

Either:

 pi(T) = 0 Li – 1 £ T £  Li – 1 + (Ui – 1 - Li – 1 )(1 – h) Li = Li - 1 Ui = Li – 1 + (Ui – 1 - Li – 1 )(1 – h)

Or:

 pi(T) = 1 Li – 1 + (Ui – 1 - Li – 1 )(1 – h) £ T £  Ui – 1 Li = Li – 1 + (Ui – 1 - Li – 1 )(1 – h) Ui = Ui - 1

For a given value of T, if T = Li – 1 + (Ui – 1 - Li – 1 )(1 – h) then both situations are compatible with that value of T.

Providing 0 < h < 1, the quantity (Ui - Li) will be reduced aafter each toss, since Li £ T £  Ui; as i ® ¥,  Li ® T and Ui ® T.

If after the ith toss successive tosses are all ‘0’s then T = Li.

If after the ith toss successive tosses are all ‘1’s then T = Ui.

If h = 0 or 1, (Li - Ui) remains unchanged after each toss.  However since only one sequence is possible T = Li = 0.

The mean value of (Li - Ui)/(Ui – 1 - Li – 1 ) = 1 – 2h + 2h2.   For h = 0 or 1, 1 – 2h + 2h2 = 1.  The minimum value of 1 – 2h + 2h2 is 1/2 when h = 1/2.  For h = 0, 1/2 or 1, but not for other values of h, all values of (Li - Ui)/(Ui – 1 - Li – 1 ) are equal to 1 – 2h + 2h2.

For a given value of T successive values of pi(T) can be calculated  from (1).  For some given values of T there will be two possible sequences of successive values of pi(T).  If the set of values of pi(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 . Li = S [ pn(T)(1 – h) P ((1 – pm(T))(1 – h) + pm(T)h) ] (1 – pn(T))(1 – h) + pn(T)h n = 1 m = 1

As i ® ¥, Li ® T.

If the coin is fair, h = 1/2 and equation (2) reduces to:

 n = i . Li = S pn(T) 1/2n n = 1

As i ® ¥, Li ® T.

Click here to see a table representing the mapping of coin tosses to the unit interval.

Home.

Hosted by www.Geocities.ws