^{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:

- Assign the players the numbers 0, 1, 2.
- Flip two coins.
- 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).
- If the result is 3, go to step 2.
- 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.