Fog Creek Software
Discussion Board

flipping coins

Can someone please elucidate the answer posted for the "flipping coins" teaser? As in, how do you justify delta h being zero (or, as is claimed later, "remember that a flip to a tail results in no change to the number of tails ")???Thanks!

Kunal Kunde
Tuesday, September 7, 2004

Imagine having 99 coins. Now:

33 show head and
66 show tail.

When the robot is finished with all of them (we're in statistics, so we can say something like this...), he has turned the heads to tails and also has thrown all the tails. The likelihood that flipping a tail turns into a tail again is 50%. So we have

33 tails (the former 33 heads)
33 tails (half of the 66 tails)
33 heads (other half of the 66 tails)

which again leads to 33 heads and 66 tails like in the beginning.

Tuesday, September 7, 2004

As for the solution given. If I understand you right, you are wondering why delta_h should become zero.

Given the question if there will be "a convergence in distribution of heads vs. tails", this can be expressed as "will there be the same number of heads and tails after each round" - in other words:

1) NoH(T1) = NoH(T0)

where NoH means "Number of Heads" and T0 and T1 are points in time.

We also know that the number of tails is

2) NoT(T) = N - NoH(T)

where N is the total number of coins and NoT are the number of tails.

Applying the robot's rules there is:

3)    NoH(T1) = NoT(T0) * 0.5
<=> 0 = 0.5 NoT(T0) - NoH(T1)

Apply 1):
3a)  0 = 0.5 NoT(T0) - NoH(T0)
This is the formular the given solution starts with, except all is divided by N already. It also subsitutes NoH with NoT now, but I will proceed using heads.

Apply 2):
3b)  0 = 0.5 (N - NoH(T0)) - NoH(T0)
<=>  0 = 0.5 N - 1.5 NoH(T0)
<=>  0 = 1/2 - 3/2 NoH(T0)/N
<=>  1/2 = 3/2 NoH(T0)/N
<=>  N/3 = NoH(T0)

Tuesday, September 7, 2004

Thank you very much Dagobert!!! You have provided a truly "idiot-proof" explanation. :-)

Kunal Kunde
Wednesday, September 8, 2004

*  Recent Topics

*  Fog Creek Home