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...
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.
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.
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$?".
