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$
  • $\begingroup$ Can you only 'bend' the coin up front once or can you bend it after each flip? $\endgroup$ – Ivo Beckers Jan 18 '16 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$ – Carl Löndahl Jan 18 '16 at 10:56
  • 1
    $\begingroup$ Just one 'bend'! (or it will break...) - edited the question. $\endgroup$ – MDman Jan 18 '16 at 12:48
  • $\begingroup$ Do you know solution? It feels like the answer is No and the proof is complex... $\endgroup$ – klm123 Jan 18 '16 at 18:17
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$
  • $\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 '16 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 '16 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 '16 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 '16 at 19:05
  • $\begingroup$ @MDman For $M\ge5$, $2^{M-2}>M$. $\endgroup$ – f'' Jan 19 '16 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$
  • $\begingroup$ Wow. This is nice and straightforward! No use of hardly proven theorems is needed. Accept it. $\endgroup$ – klm123 Jan 31 '16 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 '16 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, privacy policy and cookie policy

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