Lauren Ipsum and the Unfair Coin
Fair Coins are the currency of Userland. A Fair Coin flips fifty-fifty with mathematical exactness. In the real world most coins are pretty fair, but you never know whether there might be a small bias to one side or another. This presents Lauren Ipsum, a girl who's lost in Userland, with a problem. No one wants her "Quarter Dollars". They might be biased. How can she negotiate an exchange rate?
A story about computer science
and other improbable things.
I sometimes no longer ask this in job interviews, to see how candidates deal with probability. The answer relies on a simple but powerful idea: as long as the bias is constant, you can use it against itself. The same idea is used in bimetallic springs in mechanical clocks. The two different rates of expansion to keep the overall tension constant in the face of changing temperature.
Here are the four possible outcomes of two flips of a coin. You can click and drag the bias to see how the probabilities change. No matter the bias, the odds of getting a Heads then Tails is always exactly the same as getting Tails then Heads.
Suppose Heads comes up % of the time.
You'll need an average of flips to get a Fair flip.
Heads × Heads = Heads × Tails = Tails × Heads = Tails × Tails =
The answer is to flip twice. If you get HH or TT, throw the result away and start over. If you get HT or TH, return the first flip as your result. This algorithm almost magically transmutes an unfair coin into a perfect, though inefficient, Fair Coin. This algorithm was first described by John von Neumann in 1951, and it's very likely happening inside your computer right now.
Like what you read? Lauren Ipsum is a children's story about computer science. Buy a copy and help us translate it into Spanish, Portuguese, and other languages.