An Unfair Coin 3: Return of the Golden Inequality

[EventHorizon]

The golden ratio is (1+sqrt(5))/2. The reciprocal of this happens to be (sqrt(5)-1)/2 which is about .618.

I happened to have a biased coin that would come up heads with exactly that probability. This was my lucky coin, and I used it to bias my decisions slightly towards the ones I favored. It was quite a tragedy when I lost this coin (not only for it's decision making qualities, but it was, coincidentally, made of gold).

How can I simulate a coin toss from my missing lucky coin using a fair coin instead?

[bonanova]

Create a binary representation of the desired probability (as precisely as you desire) with a series of coin flips.

.618 (dec) = .100111100011 ... (bin) = HTTHHHHTTTHH ... (coin flips)

You get a coin-flip string that evaluates to a smaller value with probability of .618.

It won't take many flips.

After n flips the probability of needing another flip is only 2^-n.

An initial T Is already a favorable outcome, and HH is already unfavorable.

[EventHorizon]

Yup, that's essentially what I got.

What's interesting is combining the last puzzle and this one you can show that with any biased (or fair) coin you can emulate any other biased (or fair) coin or any die of any number of sides. I didn't include emulating a biased die, but that's not much of a stretch. (this does assume both heads and tails can and do occur)

I thought I'd include it even though it's similar to what bonanova posted.

Take the binary representation of the probability of a head coming up that you are trying to emulate. If you let heads be 0 and tails 1, start flipping the coin and once you have a different outcome than in the binary representations stop. If you got a heads instead of a tails, the emulated outcome is heads. If you got a tails instead of heads, the emulated outcome is tails.

You can actually extend this directly to emulating any biased (or fair) coin or die with any other biased (or fair) coin (or die, as you can emulate a biased coin by trivially rerolling if one of two selected outcomes don't come up) that you know the outcome probabilities for. If you don't know it's probabilities, emulate a fair coin first, but then it's not quite direct.

You just need to partition the space on a number line from 0 to 1, giving each outcome to be emulated the space corresponding to the probability it should occur. Start with the whole space, [0,1]. Subdivide the space according to the probability heads comes up in the coin you are using. So the ratio of the length representing heads to the length representing tails is the ratio of heads to tails in the probability of the biased coin you are using. If heads comes up, repeat using the portion currently representing heads. Similarly for tails. Once you have subdivided small enough that the whole length is within the partition representing one emulated outcome, that is the outcome to use.

[bushindo]

Yup, that's essentially what I got.

What's interesting is combining the last puzzle and this one you can show that with any biased (or fair) coin you can emulate any other biased (or fair) coin or any die of any number of sides. I didn't include emulating a biased die, but that's not much of a stretch. (this does assume both heads and tails can and do occur)

I thought I'd include it even though it's similar to what bonanova posted.

Take the binary representation of the probability of a head coming up that you are trying to emulate. If you let heads be 0 and tails 1, start flipping the coin and once you have a different outcome than in the binary representations stop. If you got a heads instead of a tails, the emulated outcome is heads. If you got a tails instead of heads, the emulated outcome is tails.

You can actually extend this directly to emulating any biased (or fair) coin or die with any other biased (or fair) coin (or die, as you can emulate a biased coin by trivially rerolling if one of two selected outcomes don't come up) that you know the outcome probabilities for. If you don't know it's probabilities, emulate a fair coin first, but then it's not quite direct.

You just need to partition the space on a number line from 0 to 1, giving each outcome to be emulated the space corresponding to the probability it should occur. Start with the whole space, [0,1]. Subdivide the space according to the probability heads comes up in the coin you are using. So the ratio of the length representing heads to the length representing tails is the ratio of heads to tails in the probability of the biased coin you are using. If heads comes up, repeat using the portion currently representing heads. Similarly for tails. Once you have subdivided small enough that the whole length is within the partition representing one emulated outcome, that is the outcome to use.

Great puzzle. I'd just note that there's equivalent way to do this that may be more intuitive for some people.

Let p be the probability (in decimal notation) you want to simulate. Cast the fair coin N times and then treat the N-digit outcomes as a binary number. Convert that binary number into decimal number, call it O.

If O > p, call it a Failure. If O < p, call it a Success.

Another note is that in general this scheme does not precisely equate to p for any finite N. Asymptotically, it should converge to p though.

[bonanova]

Another note is that in general this scheme does not precisely equate to p for any finite N. Asymptotically, it should converge to p though.

I thought about the point you're making, but I didn't come to precisely that conclusion. A fair coin requires ony a single flip to give a p=0.5 outcome. By comparison, this scheme can take an arbitrarily long sequence of flips. But only in a vanishingly small fraction of cases. That's the only "finite N" limitation that I see. Almost every "finite N" sequence of flips is sufficient to produce the desired result.

As to whether the scheme produces the exact bias of p, I think it does.

You'd have to run the scheme an arbitrarily large number of times to reconstruct [verify?] the value of p that defines its bias, just as you'd have to do with a fair coin to prove that it's fair. But the bias produced by the scheme, each time it's run, is precisely p.

[bushindo]

I thought about the point you're making, but I didn't come to precisely that conclusion. A fair coin requires ony a single flip to give a p=0.5 outcome. By comparison, this scheme can take an arbitrarily long sequence of flips. But only in a vanishingly small fraction of cases. That's the only "finite N" limitation that I see. Almost every "finite N" sequence of flips is sufficient to produce the desired result.

As to whether the scheme produces the exact bias of p, I think it does.

You'd have to run the scheme an arbitrarily large number of times to reconstruct [verify?] the value of p that defines its bias, just as you'd have to do with a fair coin to prove that it's fair. But the bias produced by the scheme, each time it's run, is precisely p.

You're right in that your scheme, which calls for consecutive flips until the outcome differs from the binary representation, returns a probability that is precisely p. I made a mistake earlier in saying that my scheme (flip the coin for a fixed number of time N) is 'equivalent', which it assuredly is not. While that scheme may be more intuitive, it sufferers from approximation error due to the fixed finite N, plus the fact that it is not as computationally efficient. Good point!

[bushindo]

I thought I'd include it even though it's similar to what bonanova posted.

Take the binary representation of the probability of a head coming up that you are trying to emulate. If you let heads be 0 and tails 1, start flipping the coin and once you have a different outcome than in the binary representations stop. If you got a heads instead of a tails, the emulated outcome is heads. If you got a tails instead of heads, the emulated outcome is tails.

Now that bonanova and EventHorizon have posted solutions to the original problem, allow me to pose an extension. What is the average number of coin flip required for bonanova's and EventHorizon's approach to sampling the probability p? Extra bonus for putting the answer in closed form (i.e., without requiring an infinite sum).

[bonanova]

Now that bonanova and EventHorizon have posted solutions to the original problem, allow me to pose an extension. What is the average number of coin flip required for bonanova's and EventHorizon's approach to sampling the probability p? Extra bonus for putting the answer in closed form (i.e., without requiring an infinite sum).

It involves the number e.

[EventHorizon]

Now that bonanova and EventHorizon have posted solutions to the original problem, allow me to pose an extension. What is the average number of coin flip required for bonanova's and EventHorizon's approach to sampling the probability p? Extra bonus for putting the answer in closed form (i.e., without requiring an infinite sum).

that for each digit in the binary representation, if your coin flip is not the outcome representing the digit, you stop. So 50% chance of needing another coin flip at any point in the process.

So there's a 50% chance of it taking only 1 flip.

There's a 25% chance of it taking 2 flips.

There's a 12.5% chance of it taking 3 flips.

etc.

So the infinite sum for the average flips needed is the sum from i=1 to infinity of i/(2^i).

f(y) = sum x=1 to inf xy^-x

f(y)/y = sum x=1 to inf xy^-(x+1)

integrate (f(y)/y) + c = sum x=1 to inf -y^-x

-integrate (f(y)/y) + c = (1/y)/(1-(1/y))

-integrate (f(y)/y) + c = (1/y)/((y-1)/y)

-integrate (f(y)/y) + c = 1/(y-1)

integrate (f(y)/y) + c = -1/(y-1)

f(y)/y = d(-1/(y-1))/dy

f(y)/y = d(-(y-1)^-1)/dy

f(y)/y = (y-1)^-2

f(y) = y(y-1)^-2

Plugging in 2 for y gives f(y)=2.

So it takes 2 flips on average.

Of course, it would be easier to formulate it this way...

All need at least 1 flip.

50% need at least an additional 1 flip.

25% need at least an additional 1 flip.

etc.

So 1 + .5 + .25 + .125 + ... = 2.

[bonanova]

that for each digit in the binary representation, if your coin flip is not the outcome representing the digit, you stop. So 50% chance of needing another coin flip at any point in the process.

So there's a 50% chance of it taking only 1 flip.

There's a 25% chance of it taking 2 flips.

There's a 12.5% chance of it taking 3 flips.

etc.

So the infinite sum for the average flips needed is the sum from i=1 to infinity of i/(2^i).

f(y) = sum x=1 to inf xy^-x

f(y)/y = sum x=1 to inf xy^-(x+1)

integrate (f(y)/y) + c = sum x=1 to inf -y^-x

-integrate (f(y)/y) + c = (1/y)/(1-(1/y))

-integrate (f(y)/y) + c = (1/y)/((y-1)/y)

-integrate (f(y)/y) + c = 1/(y-1)

integrate (f(y)/y) + c = -1/(y-1)

f(y)/y = d(-1/(y-1))/dy

f(y)/y = d(-(y-1)^-1)/dy

f(y)/y = (y-1)^-2

f(y) = y(y-1)^-2

Plugging in 2 for y gives f(y)=2.

So it takes 2 flips on average.

Of course, it would be easier to formulate it this way...

All need at least 1 flip.

50% need at least an additional 1 flip.

25% need at least an additional 1 flip.

etc.

So 1 + .5 + .25 + .125 + ... = 2.

What he said.

[bushindo]

that for each digit in the binary representation, if your coin flip is not the outcome representing the digit, you stop. So 50% chance of needing another coin flip at any point in the process.

So there's a 50% chance of it taking only 1 flip.

There's a 25% chance of it taking 2 flips.

There's a 12.5% chance of it taking 3 flips.

etc.

So the infinite sum for the average flips needed is the sum from i=1 to infinity of i/(2^i).

f(y) = sum x=1 to inf xy^-x

f(y)/y = sum x=1 to inf xy^-(x+1)

integrate (f(y)/y) + c = sum x=1 to inf -y^-x

-integrate (f(y)/y) + c = (1/y)/(1-(1/y))

-integrate (f(y)/y) + c = (1/y)/((y-1)/y)

-integrate (f(y)/y) + c = 1/(y-1)

integrate (f(y)/y) + c = -1/(y-1)

f(y)/y = d(-1/(y-1))/dy

f(y)/y = d(-(y-1)^-1)/dy

f(y)/y = (y-1)^-2

f(y) = y(y-1)^-2

Plugging in 2 for y gives f(y)=2.

So it takes 2 flips on average.

Of course, it would be easier to formulate it this way...

All need at least 1 flip.

50% need at least an additional 1 flip.

25% need at least an additional 1 flip.

etc.

So 1 + .5 + .25 + .125 + ... = 2.

Great solve. It is indeed surprising how efficient bonanova's and your algorithm is.