Drawing uniformly using a single biased coin

Your task is to draw uniformly from a set of size $N$. You are given a single coin which you can ‘bend’ to control the probability $p\in[0,1]$ of throwing a Head, but you are only allowed a bounded number of throws; can it be done?

Note that if the number of throws is not bounded then this can be done (more or less trivially) by an unbiased coin (how?).

Edit: your are only allowed to bend once or otherwise your coin will break...

• Can you only 'bend' the coin up front once or can you bend it after each flip? – Ivo Beckers Jan 18 '16 at 10:45
• Answer to the second question: flip $\lceil \log_2 N \rceil$ times, and then interpret the flips as binary. If $N < bin(flips)$, re-run. If N is a power of 2, the procedure is bounded. – Carl Löndahl Jan 18 '16 at 10:56
• Just one 'bend'! (or it will break...) - edited the question. – MDman Jan 18 '16 at 12:48
• Do you know solution? It feels like the answer is No and the proof is complex... – klm123 Jan 18 '16 at 18:17

It is:

possible!

because:

Let $M\ge5$ be some multiple of $N$ such that $M-1$ is prime. (This is possible by Dirichlet's theorem.)

Consider the polynomial $x^{M-1}+(1-x)^{M-1}-\frac{1}{M}$. The value of this polynomial is positive for $x=0$ and negative for $x=\frac{1}{2}$, so it must have a real root in the interval $(0,\frac{1}{2})$. Choose $p$ as such a root.

Now flip the coin $M-1$ times. The probability that it comes up all heads or all tails is $p^{M-1}+(1-p)^{M-1}=\frac{1}{M}$.
Otherwise, there are $j$ heads for some $0<j<M-1$. For every $j$, there are $M-1\choose j$ equally likely ways to get $j$ heads. Because $M-1$ is prime, it divides $M-1\choose j$, so these cases can be divided into $M-1$ equal groups (one way to do this is to sum the indices of the flips that came up heads and reducing mod $M-1$). By putting together one group from each $j$, we can make $M-1$ equal sets of results, which must each have probability $\frac{1}{M}$.

We have now chosen equally from $M$ items. Because $M$ is a multiple of $N$, we can combine probabilities if necessary to choose equally from $N$ items.

• I think few clarifying words on 'remaining cases' are needed. However, my solution has similar structure so I understand what you're saying. – MDman Jan 19 '16 at 0:00
• Explain the very last sentences please. What do you combine? (And why the chosen p is enough to chose between all N=M*k) – klm123 Jan 19 '16 at 12:11
• I'm following your argument regarding the polynomial root; for $x=\frac{1}{2}$ you get $(\frac{1}{2})^{M-2}-\frac{1}{M}$ - why is this negative? – MDman Jan 19 '16 at 14:20
• @klm123 $M$ is a multiple of $N$, not the other way around. So $M=Nk$, and you can combine $k$ of the $\frac{1}{M}$ probabilities to get a $\frac{1}{N}$ probability. – f'' Jan 19 '16 at 19:05
• @MDman For $M\ge5$, $2^{M-2}>M$. – f'' Jan 19 '16 at 19:07

It is

possible!

This is not my own work, I got this answer from here.

Let's say we flip the coin $F$ times. For each $k$, we will take the $\binom{F}k$ coin flip sequences which have exactly $k$ heads and divide these as evenly as possible among the first $N-1$ outcomes. Since $\binom{F}k$ may not be divisible by $N-1$, there might be some remainder $r_k$ left over; these remaining $r_k$ sequences will be assigned to the last outcome.

By construction, the first $N-1$ outcomes are all equally likely. Let's say the coin is biased so that $P($heads$)=b$. The probability of the last outcome, let's call it $R(b)$, is given by adding up all the probabilities of the leftover sequences: $$R(b)=\sum_{k=0}^Fr_kb^k(1-b)^{F-k}$$ Note that $R(0)=1$, and $$R(1/2)=\sum_{k=0}^F r_k(1/2)^F\le FN(1/2)^F$$ since the remainders $r_k$ are all at most $N$. This means that we can choose $F$ large enough so $R(1/2)<\frac1N$. Then, by the Intermediate Value Theorem, we can choose a value $b$ between $0$ and $1/2$ for which $R(b)=\frac1N$.

Let's start with the algorithm: throw the coin $N-1$ times and choose the $i$-th element ($1\leq i\leq N-1$) if and only if the $i$-th throw was a Head and the rest were a Tail. Repeat, if no one was chosen. If after $k$ repeats no one was chosen we choose the $N$-th element.

We need to show that we can choose $p$ (the probability for a Head) and $k$ such that the probability to choose the $N$-th element is $\frac{1}{N}$ (clearly then, the probability to choose any other element is also $\frac{1}{N}$). Now, if we work out the details, the probability to choose the $N$-th element is: $$\left[1 - (N-1)p(1-p)^{N-2}\right]^k$$ Consider it as a polynomial in $p$. We look to fix $k$ such that there will be two points that evaluate to values above and below $\frac{1}{N}$ (so we can apply the intermediate value theorem). For $p=0$ it evaluates to $1$ (irrespective of $k$). For $p=\frac{1}{N-1}$ the value within the square brackets is less than $1$ so by taking $k$ large enough we can bring it below $\frac{1}{N}$ as needed.

• Wow. This is nice and straightforward! No use of hardly proven theorems is needed. Accept it. – klm123 Jan 31 '16 at 14:14
• Thanks. I waited for someone to comment before I accept my own solution... (encouraged by you I will now do it) – MDman Feb 1 '16 at 8:48

Since you are allowed to bend the coin many times to control the probability $p$ it should be simple:

Just reject each outcome one by one, each time bending coin according to a current number of the non-rejected outcomes:
1) Bend to make $p=\frac{1}{N}$. Throw. If it is Head then you got outcome-1 (with probability of $\frac{1}{N}$). Otherwise proceed to step 2.
...
k) Bend to make p=1/(N-k+1). Throw. If it is Head then you got outcome-k (with probability of $\frac{N-1}{N}*\frac{N-2}{N-1}*...*\frac{N-k+1}{N-k+2}*\frac{1}{N-k+1}=\frac{1}{N}$). Otherwise proceed to step k+1.
...
N) Here p must be $\frac{1}{1}$, so no need to throw. You got outcome-N.

More interesting question is "Can it be done if you can bend the coin only once to chose the probability $p$?".