# How to choose between an odd number of options with a fair coin

It is possible to choose between three equally desirable outcomes by tossing a fair coin as follows:

Choose option 1 if the first head appears on an even toss

Choose option 2 if the first tail appears on an even toss

Choose option 3 if the first head and the first tail both appear on an odd toss

Note that option 1 and option 2 are mutually exclusive, because we must have a head or a tail on the first toss.

This works because the binary expansion $$\frac 13 =0.010101010101 \dots$$ has a $1$ in all the even places. Or equivalently because $$\frac 13=\frac 14+\frac1{16}+ \dots +\frac 1{4^n}+\dots$$

This is quite a simple procedure (though perhaps not as well known as it might be). I was pondering in the bath what might be the most convenient set of options if there were five or seven possibilities.

For example I can pick off two fifths using the binary expansion of $\frac 15$ with heads and tails, and use my procedure for thirds to do the remaining three fifths - so it is possible. But can one do fifths or sevenths without resort to this kind of recursive procedure?

-
Ah, my mistake. So, can't you just let your sequence of heads and tails correspond to a number written in base 2, and as soon as the number is forced to be between $k/5$ and $(k+1)/5$, select the $k$th option? –  Gerry Myerson Feb 7 '14 at 10:05
Another alternative would be to flip the coin three times, once for each option. If the coin lands on heads, select that option for the next round, if it lands on tails, reject that option altogether. If all three land on tails, start that round over again. Continue until you have one option. –  Jonathan Landrum Feb 7 '14 at 14:21
@JonathanLandrum I like that idea - I'm now interested in the expected number of tosses to make a decision. Yours could be made more efficient by taking the odd one out if the three tosses are not the same, and tossing again if they are. More generally it would be possible to select from $n$ odd by using $n$ tosses to partition as heads and tails and choosing the odd set for the next round - or choose the smallest set and tie break equals by using heads. I think Gerry Myerson's suggestion is more efficient, though it requires a little more computation. –  Mark Bennet Feb 7 '14 at 14:36
–  ShreevatsaR Feb 7 '14 at 15:12
It's worth noting that the "flip the coin once for each option" approach has a major advantage: it will work even if the coin is unfair, because each option has the same chance to be accepted or rejected at each round. It can be pretty inefficient, of course. –  DSM Feb 7 '14 at 16:03

Elevated from a comment, at request of OP:

To choose with equal probability among $q$ alternatives, interpret your sequence of heads and tails as a sequence of zeros and ones in the binary expansion of some number $x$ between zero and one; when you have enough of the binary expansion to be sure that $x$ lies between $(p-1)/q$ and $p/q$, choose the $p$th of the $q$ alternatives.

-

I'll leave the details (coin=fair coin):

1) By tossing a coin $n$ times, you can simulate a uniform distribution on $\{1,2,3,\dots,2^n\}$ (by taking the binary representation of these numbers minus $1$ and associating $0$ to Tail and $1$ to Head).

2) If you have a uniform low on $\{1,\dots,N\}$, you can simulate a uniform law on $\{1,\dots,n\}$ for $n<N$ by the rejection sampling method (cf. wikipedia): you toss your coin until obtaining a number between $1$ and $n$. The probability the procedure will never stop is $0$.

It can take a while, for example, for a uniform law on $\{1,\dots,2^n+1\}$ for large $n$ but it will work. Maybe there is a simpler, or faster method. Actually, a computation shows that the average number of toss to obtain one result uniformly in $\{1,\dots,n\}$ is $\tfrac1n\lceil\log_2 n\rceil 2^{\lceil\log_2 n\rceil}$.

Even if rejection sampling is not the best method for this specific problem, it is an efficient tool and is, as far as I know, used in statistics software, so it is worth knowing it.

-