Flipping Coins
Here's an interview question.
Suppose you have a biased coin. Assume that the coin comes up tails 1/3 of the time, and heads 2/3 of the time. Question: how can you use this biased coin to simulate a fair coin?
I'll walk you through my thought process, and then give the 'right' answer (I don't know if there is a best answer).
First, let's formalize the problem (because for some reason I have trouble wrapping my head around some problems unless I first over-formalize them). Let \(X\) be a Bernoulli random variable taking the values 0 (for heads) and 1 (for tails). Since we have a biased coin, \(P(X = 0) = 1/3\) and \(P(X = 1) = 1 - P(X = 0) = 2/3.\) Our goal is to do something with \(X\) that gives us a random variable \(U\) such that \(P(U = 0) = P(U = 1) = 1/2.\)
My first thought was to apply the cumulative distribution function to \(X\). This method works for continuous random variables. Let \(X\) be a continuous random variable with cumulative distribution function \(F_{X}(x)\). Then the new variable \(U = F_{X}(X)\) (that is, the random variable you get by applying the CDF of \(X\) to itself) is uniform on \([0, 1]\). (I'll leave the proof of this to the reader. Basically, consider \(P(U \leq u)\), substitute for \(U\), and then notice some nice things about \(F_{X}(x)\) in the continuous case.) But as I said, this applies to continuous random variables.
The next most obvious approach is to flip the coin more than once. If we assume independence between flips, then for two flips \(P(X_{1} = x_{1}, X_{2} = x_{2}) = P(X_{1} = x_{1}) P(X_{2} = x_{2})\). We can spell out the associated joint probability mass function, but you'll basically see that the sequences and their associated probability mass are
00 -- 1/9
01 -- 2/9
10 -- 2/9
11 -- 4/9
(Important note: the sum of all of these is 1.)
At this point, an 'obvious' (though it didn't immediately jump out at me) solution to our problem presents itself. Notice that the probabilities of getting a 01 and a 10 are the same. The leap we then have to make is to throw out some tosses. If we just ignore the 00 and 11 tosses (pretend they don't happen, if you'd like), then we can call 01 heads and 10 tails, and we have ourselves a fair coin.
Of course, we have to flip our biased coin more frequently to generate a sequence of 0s and 1s we could generate with an unbiased coin: we have to flip twice to get an outcome, and then we throw out 5/9 of those outcomes! Which leaves me wondering if a more efficient method exists.
One nice property of this method (beyond the fact that it solves the interview question and hopefully gets us the job1) is that it will work for any biased coin. In fact, this method is important enough that it has been named the von Neumann extractor: given any uncorrelated (no need for independence) sequence of 0s and 1s generated by a (stationary) stochastic process, this method will produce a fair coin flip.
Good on von Neumann.
Aside: I think I'll start collecting these sorts of questions on this blog. Presumably someone else has had this idea before me. (A quick google search reveals yes, they have.) But it can't hurt for another person to do it.
It's worth noting that this question did not come from an interview I did. I've only done one interview in my life. In it, I expounded on the virtues of multidimensional Newton's method, and learned that I should know how to talk intelligently about pointers and binary trees. (This was during my last semester of undergrad, and my only computer science course at that point had used Java, which was conspicuously pointer free!)↩