Wednesday, September 2, 2009

Getting a Fair Toss From a Biased Coin

A paper out of Stanford and UCSC, Dynamical Bias in the Coin Toss (PDF, 5MB), reveals a small but significant bias in the process of flipping a coin.

James Devlin of Coding the Wheel provides the following summary:
1. If the coin is tossed and caught, it has about a 51% chance of landing on the same face it was launched. (If it starts out as heads, there's a 51% chance it will end as heads).
2. If the coin is spun, rather than tossed, it can have a much-larger-than-50% chance of ending with the heavier side down. Spun coins can exhibit "huge bias" (some spun coins will fall tails-up 80% of the time).
3. If the coin is tossed and allowed to clatter to the floor, this probably adds randomness.
4. If the coin is tossed and allowed to clatter to the floor where it spins, as will sometimes happen, the above spinning bias probably comes into play.
5. A coin will land on its edge around 1 in 6000 throws, creating a flipistic singularity.
6. The same initial coin-flipping conditions produce the same coin flip result. That is, there's a certain amount of determinism to the coin flip.
7. A more robust coin toss (more revolutions) decreases the bias.

The article goes on to suggest a coin-flipping strategy that tries to take advantage of the small bias, but what about getting a completely fair toss from a biased coin?

It turns out to be fairly easy. Just follow these steps:
  1. Flip the coin twice.
  2. If both tosses are the same (heads-heads or tails-tails), repeat step 1.
  3. If the tosses come up heads-tails, count the toss as heads. If the tosses come up tails-heads, count it as tails.
To see why this method makes even a biased coin fair, let's pretend we have a weighted coin that comes up heads 60% of the time. If you toss it twice and throw out the result when both tosses are the same, you're left with two possible outcomes. The probabilities of the two remaining outcomes are the same.

P(HT) = P(TH)
P(H) * P(T) = P(T) * P(H)
0.6 * 0.4 = 0.6 * 0.4 = 0.24

Since both outcomes have exactly the same probability, the bias is removed. This method will work no matter how biased the coin you use, as long as there's some possibility of it coming up either heads or tails (so no two-headed coins allowed).

Note: This method for simulating a fair coin using a biased coin was introduced by John von Neumann in Various techniques used in connection with random digits (1951).

12 comments:

Jakob said...

Agreed. Obviously you need to pay attention to the initial conditions before for each toss, to avoid bias introduced by:

1. If the coin is tossed and caught, it has about a 51% chance of landing on the same face it was launched. (If it starts out as heads, there's a 51% chance it will end as heads).

Bill the Lizard said...

Jakob,
Yes, that's a good point. You need to make sure the initial conditions are the same for both tosses. Otherwise, the tosser could give himself a slight advantage by influencing the outcome towards either HT or TH.

Anonymous said...

Can bias be introduced for rolling dice?

Colin said...

"Can bias be introduced for rolling dice"

I once watched a documentary about a new technique for manipulating dice in a Casino. Essentially the person rolling the dice at a craps table was spinning the dice (around the vertical axis) as oppose to rolling them as anyone else would. After lots of practice they could ensure with high probability what number would come up. They did this by throwing and spinning in such a way to make the dice stop dead when they hit the wall of the table. The number they had face up in their hand would be the number that was face up on the table. The documentary showed them doing this with quite high regularity though it didn't go in depth into the actual probability.

More alarming (or perhaps more revealing) is that the Casino refused to accept it as a form as cheating as they didn't believe it were possible.

I'm sure there's more information out there on the web.

Bill the Lizard said...

Anon,
Beyond Colin's information about affecting the outcome of a roll of the dice, I don't know if you can do it with fair dice.

Some cheap dice aren't fair, though. If you look at the face of some 6-sided dice, you'll see that the dots (or "pips") are small holes filled with paint. This means that more of the dice material is removed from the side with six pips than from the side with only one pip (and all the others). This causes a very slight imbalance.

Casino dice don't have this problem. The pips on casino dice are filled with material of the same density as the material the dice are made from so that each side weighs as exactly the same as all the others as possible.

There are methods you can use to throw off the balance of a die, just like most coins aren't perfectly balanced. An off-center weight can make one side more likely to come up than others. Shaving the edges of a face so that it rolls more freely away from that face is another way, but it is easily detected by visually inspecting the die. You can also shave an entire face down by a tiny amount so the die is no longer cubical.

Aruni RC said...

Changing the initial conditions change the whole probabilistic situation.
Just a thought - how many of us saw this in the movie "21"? :D

Bill the Lizard said...

Aruni RC,
I never watched 21. I guess I have to rent it now.

Troy said...

If you have unfair dice, you can do something similar to remove the bias. However, it's going to take a lot longer than with a coin.

If you have an N-sided die (N is 6 for most dice), roll it N times. Repeat until you get a set of N rolls with each possible result present once. Use the first result rolled.

You could speed it up some by using a sliding window. If you roll 1,2,3,2, throw out the 1 and first 2, since they can't form a set of unique results. Continue rolling with 3,2 as a partial set. Since the rolls are independent, the initial 1 and 2 won't have an effect on the next four rolls.

The proof that it works is similar to the proof in the main article. Each roll is independent of the others, so all the orderings have the same probability. Picking the first roll (or any predetermined) roll gives a random result.

The bad news is it will take a while to get an acceptable set of rolls. With a fair coin, you need to flip twice on average. With a fair, six-sided die, you need to roll about 65 times on average. I recommend not trying this technique with a 20-sided die. :-)

Bill the Lizard said...

Troy,
I know I have a 100-sided die around here somewhere. :)

Pradeepg said...

I was just wondering whether performing this experiment on the Moon or in Universe will have any impact on results?

Bill the Lizard said...

Pradeepg,
That's a good question. I think the results would change in a different spot in the universe. The reason a coin toss isn't a perfect 50/50 proposition is because of a slight wobble in the spin of the coin introduced by imperfections in it's own balance. This wobble causes one side of the coin to be pointing up for a longer duration than the other side during the coin's spin. If you flip a coin on the moon, the wobble should change, meaning the difference in the durations should increase or decrease (I don't know which) due to the change in gravity. So if a coin has a 51/49 bias on Earth, it might have a 52/48 bias (or it could be higher or lower) on the moon, but I would expect it to be different.

Klintbørre said...

I also find this question interesting, and I would very much like to hear the lizards physical justification for why gravity should change the probabilities.

My take at the problem is that in a uniform gravitational field, forces from gravity are equal at all points on the coin, and therefore the only thing that changes is the duration of the toss, which in the limit of a very high toss (many revolutions) shouldn't change the probability.

Would this probability-altering effect have something to do with the ratio between sentripetal and gravitational forces?

If such an effect exists I agree that saying whether it increases or decreases randomness would be hard to answer without some deep-space experiments to nail down some bounds.