Unbiased tosses from a biased coin

This is a very handy algorithm that I came across today, which is, according to this paper, due to John von Neumann.

Suppose you have a coin which you suspect to be biased. You're not sure whether it's biased to heads or to tails, you just know it's biased. Actually, according to the wikipedia article on coin flipping, coins tend to be slightly biased naturally and it's possible to train yourself to flip a coin slightly more predictably than pure chance. So there you are with a biased coin. Nevertheless, can you use it to produce unbiased tosses?

Von Neumann came up with a remarkable idea: use tosses in pairs. If the first toss of a pair comes up heads and the second tails, call the result of the pair heads. If the first comes up tails and the second heads, call it tails. If both tosses produce the same result (heads/heads or tails/tails), ignore that pair, and start over.

In mathematical terms, we assume that all the individual flips are independent. So if the probability of getting heads is p and the probability of getting tails is q, where p + q = 1, then the probability of heads followed by tails is exactly the same as the reverse result, namely pq. Since we ignore all other pairs of tosses, it means that the overall "coin pair toss" is unbiased. Note that the algorithm doesn't require you to know what the probabilities are (though obviously if it's a two-headed coin, you'll never get any unbiased tosses!).

  Loading links to posts on similar topics...

1 Response

#1 Eber Irigoyen said...

29-Jan-10 6:02 PM

I have the strange ability to be able to toss (or have someone else do it) a coin and predict with 90% accuracy (closer to 100% if I train for a while) the result, I do that by looking at the coin while in the air

Leave a response

Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.

•  Emphasize with italics: surround word with underscores _emphasis_
•  Emphasize strongly: surround word with double-asterisks **strong**
•  Link: surround text with square brackets, url with parentheses [text](url)
•  Inline code: surround text with backticks `IEnumerable`
•  Unordered list: start each line with an asterisk, space * an item
•  Ordered list: start each line with a digit, period, space 1. an item
•  Insert code block: start each line with four spaces
•  Insert blockquote: start each line with right-angle-bracket, space > Now is the time...

Name (required) Mail (will not be published) (required) Website Response Submit

Preview of response