My Photo
Name: Tyler
Location: Mountain View, California, United States

thinking := [life, games, movies, philosophy, math, coding, pizza, &c.]

Friday, October 31, 2008

fairness is contageous

Here is a trick to simulate a coin toss between two people if both of you are caught coinless: each person secretly chooses a number, either 0 or 1, and both announce their choice simultaneously. If both numbers match, this is heads; otherwise tails.

This idea can give surprisingly fair (i.e. close to 50/50) results.

Suppose you choose fairly, but your so-called friend is nefarious, and chooses their number in any non-50/50 manner. For example, they could always choose 1, or always choose 0, or always try to predict your answer and choose the same number as you.

As long as you choose fairly, though, the ultimate answer will also be exactly fair. Why? No matter what your friend chooses, you'll choose either the same or the different number with 50/50 probability. If you're really choosing your number fairly, then there's no way for your friend to make any kind of prediction (by the way, this unpredictable property is one way to think about probabilistic independence).

Of course, the situation is symmetric: if your friend plays fair, then the ultimate outcome is fair, too, no matter how nefarious you are. Fairness trumps nefarness.

Even cooler: even if you both play unfairly, though still independently, then the ultimate outcome will still be more fair than either of you would have been acting on your own. The math on this is pretty simple.

Suppose you choose 0 with probability 1/2 + b1, and your friend chooses 0 with probability 1/2 + b2. I'm writing the probabilities this way because it makes the calculations easier. We can think of the b's as the "bias" of each person's randomness. A bias closer to 0 means a more fair result -- closer to 50/50.

Using b1 and b2, what is the probability that the outcome will be a match? It's Prob(both heads) + Prob(both tails) =

(1/2 + b1)(1/2 + b2) + (1/2 - b1)(1/2 - b2) =
1/2 + 2b1b2.

In other words, the combined bias is 2b1b2. Notice that each individual bias is in the range [0, 1/2], so the combined bias is also in that range. Also notice that, if both biases are < 1/2, then the combined bias is less than either individual bias. This is what I meant by saying that the combined outcome is more fair than either player alone.

In fact, things are a lot more fair since this is a multiplicative effect. Suppose you're sitting around with the unshakable urge to produce fair random binary digits. Alas, you empirically discover that you seem to choose 0 with probability 60%, and 1 the other 40% of the time. What are you to do??

Just write down a few random 0/1's in a row, and take the XOR of this list of numbers. This is just a slight generalization from the above 2-player version. (By the way, this is the same as giving an ultimate outcome of 1 if there are an odd number of 1's in your sequence; 0 otherwise.) If you started with bias b, then taking the XOR of n bits in a row will give you an ultimate answer with bias (2b)n/2.

Why? We can confirm this formula by repeated application of the above derivation that 2 players end up with combined bias 2b1b2. The sequence of biases for a single player looks like this:

b → 2b2 → 4b3 → ... → (2b)n/2.

To get an idea of how incredibly useful this convergence is, suppose that your personal bias is b=60%, and that you want to be within 1 millionth of perfect fairness. How many times n must you perform a single (60%-biased) choice in order to arrive at an XOR which is this close to perfect fairness? Only nine times! This works because (2*.1)9/2 < 1/1,000,000. If you ask me, this is a pretty small price to pay to go from a 10% bias down to 0.0001%.