Extended coin flips

| Comments (3) |
Everyone knows how to decide fairly simple questions with a coin flip: you flip, I call it in the air.1 Unfortunately, this simple technique doesn't work when we are trying to draw one winner out of a group of three (or one loser, the concept is the same).

A non-deterministic process
It's relatively easy to convince yourself that there's no process that's both fair and guaranteed to require a finite number of flips (Note: we're assuming here that the flips are i.i.d. with a .5 probability of heads or tails. If not, we need a different analysis.) Consider any number of flips n: the total number of possible outcomes is 2^{n} which is never evenly divisible by 3. Thus, any assignment of outcomes to winners must either be unfair (give more outcomes to some winner) or have some set of outcomes which is invalid, in the sense that the process fails and must be run again.

At Least One Solution
The above should tell you the general shape of the solution: we start by flipping a coin n times. For some subset of possible outcomes m we declare the process finished and declare a winner. For the remaining n-m outcomes we flip some additional number of times and we repeat until we have declared a winner. I don't have an optimal solution for the general case of any number of players, but for three there is an obvious solution that I also believe is optimal:

  1. Assign the players the numbers 0, 1, 2.
  2. Flip two coins.
  3. Interpret the results of the flip as a binary number with the first coin being the high digit. E.g., HT is binary 10 (i.e., 2).
  4. If the result is 3, go to step 2.
  5. The winner is the matching player. Exit.

This algorithm has a .75 chance of terminating after two flips and on average requires 2.667 flips. There are other equivalent two-flip algorithms, but obviously no algorithm that starts with three flips can be more efficient. I don't have an algorithm that sometimes terminates after a single flip, but my intuition is that there isn't one (I'll make an argument for this shortly).

Generalizing to N > 3
Obviously N = 4 is easy. We can just flip a coin twice. N = 5 is more complicated, as is any non power of 2. This feels like a coding theory problem at this point and my coding theory is rather rusty, but let's consider at least one avenue. Clearly, we need at least 3 bits to cover all possible winners, so we could just say that we use 3 bits and values 0-4 correspond to winners with values 5-7 discarded. This algorithm has a .625 chance of terminating after 3 flips, and on average requires 4.8 flips. This is obviously suboptimal since (unlike the N=3 case) we're discarding information contained in the difference between those three values. We can get a more efficient packing by always doing 4 flips, using the first 15 values and discarding the 16th. Now we're not throwing away information, and we have a .9375 probability of terminating after one round, and on average requires 4.267 flips.

There's a better solution, though. Build a prefix-free code, where we encode as many values as possible in the first three (values 0-4) but then instead of discarding values 5-7 we use them in combination with another bit. I.e. the following bit patterns:

Pattern   Winner
000            1 
001            2
010            3
011            4
100            5
1010           1
1011           2
1100           3
1101           4
1110           5
1111           Continue

This is really just the 4-coin mapping (with 16 values) but arranged in such a way that we ignore the final bit (coin) for some of the prefixes because both suffixes produce the same value, so we don't need to read the next bit.

This algorithm has a .625 probability of terminating after 3 coin flips and (same as before) a .9375 probability of terminating after 4 coin flips. Each round takes on average 3.333 flips, so unless I'm screwing up somewhere (and this is certainly possible) this algorithm uses you an average of 3.556 flips, which is far better.

It seems like one ought to be able to use a generalization of this strategy for any number of players that isn't evenly divisible, construct a minimal-length prefix-free code with a symbol set that's some multiple of the number of players, but my coding theory isn't really up to giving a more general algorithm.

1. It's interesting to note that this isn't actually fair. Say that coins are in general biased in favor of heads, then the person calling will always ask for heads and gain an advantage. The "call it in the air" technique is designed to deal only with the threat that the flipper is able to bias the result. To deal with biased coins you need to flip multiple coins. But if the coins are flipped sequentially you now need to deal with the possibility that the flipper can bias the coins. You could both flip one, in which case it's a little like rock/paper/scissors in terms of psychology.


I now you'll accuse me of having "hammer/nail" syndrome here, but this is actually similar a subset of the FPE problem, in that if you have a random permutation from 0...n-1, then f(0) can be your choice of winner (and FPE assumes that you are building this premutation from binary PRFs, which are essentially your coinflips.) Black and Rogaway's 2002 paper describes your 3 case as something they call cycle walking. Granboulan and Pornin (FSE 2007) describe this generator with your five-case optimization also (page 454), and use it as part of a method to build perfect permutations from 0...n-1.

Don't know of anything more economical.

I'm not even sure you can guarantee termination. I was thinking of a method where we evaluate each person in turn, using a lot more flips, but with N=3 I can still only get an approximation of 1/3 from 1000 coin flips.

None of these methods guarantee termination for a non evenly divisible
number of players. You can either have bias or you can have an unbounded
(but with small expected value) number of rounds.

Leave a comment