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

Question

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?

Answer 1

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.

Answer 2

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.