6
$\begingroup$

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...

$\endgroup$
4
  • $\begingroup$ Can you only 'bend' the coin up front once or can you bend it after each flip? $\endgroup$
    – Ivo
    Jan 18, 2016 at 10:45
  • 5
    $\begingroup$ 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. $\endgroup$ Jan 18, 2016 at 10:56
  • 1
    $\begingroup$ Just one 'bend'! (or it will break...) - edited the question. $\endgroup$
    – MDman
    Jan 18, 2016 at 12:48
  • $\begingroup$ Do you know solution? It feels like the answer is No and the proof is complex... $\endgroup$
    – klm123
    Jan 18, 2016 at 18:17

4 Answers 4

7
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I think few clarifying words on 'remaining cases' are needed. However, my solution has similar structure so I understand what you're saying. $\endgroup$
    – MDman
    Jan 19, 2016 at 0:00
  • $\begingroup$ Explain the very last sentences please. What do you combine? (And why the chosen p is enough to chose between all N=M*k) $\endgroup$
    – klm123
    Jan 19, 2016 at 12:11
  • $\begingroup$ 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? $\endgroup$
    – MDman
    Jan 19, 2016 at 14:20
  • $\begingroup$ @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. $\endgroup$
    – f''
    Jan 19, 2016 at 19:05
  • 1
    $\begingroup$ @MDman For $M\ge5$, $2^{M-2}>M$. $\endgroup$
    – f''
    Jan 19, 2016 at 19:07
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.