Using two coins to select a person fairly.

Good evening, I would like to know if the solution to this problem, I know it can be solved because it is from a Hungarian Olympiad. The problem is as follows: You need to fairly select a person between $n$ persons using two unfair coins for which you get to decide the odds.

This is simple if you label the people $1$ through $n$ in binary and then flip $\lceil \log_2 n \rceil$ coins to get a number in binary. If the number corresponds to a person that person gets selected, otherwise repeat the process again.

The problem here is that we need to give a bound for the number of flips before hand. I don't really know how to solve the problem now.

Thank you very much in advance.

Regards.

Solution 1:

Trivial Cases

If $n=1$ we don't need any flips. If $n=2^k$ we only need to flip a fair coin $k=\log_2n$ times.

Using 1 Coin

Interestingly, you can simulate an $n$-sided die using only 1 coin and $\,3 \log n\,$ flips. The only caveat is that I can't give you the bias of the coin explicitly. Suppose we have a coin with bias $b$. We have $n$ numbered bins and we want to map each individual sequence of $f$ flips to a bin such that each bin has probability $1/n$. There are ${f \choose k}$ sequences that have $k$ heads. For each $k$, we map $\left\lfloor {f \choose k}(n-1)^{-1} \right\rfloor$ of these to the first $n-1$ bins, and put the remainder in the last bin. By construction, the first $n-1$ bins have the same probability, so it remains to show that the last bin is filled to $1/n$. Let $R(b)$ be the probability of the last bin. Then $$ \begin{align} R(b) &= \sum_{k=0}^f r_k \; b^k \; (1-b)^{f-k} \\ & \\ r_k &= \small{{f \choose k} \;\; (\text{mod } n-1)} \end{align} $$ We have $\,R(0) = 1\,$ and if we take $f$ large enough such that $\,R(1/2)<1/n$, then by continuity and the intermediate value theorem there must be a $b'$ such that $\,R(b') = 1/n$. Noting the bound $\,R(1/2) < 2^{-f} f n\,$ we find that $\,f-\log f > 2 \log n\,$ implies $\,R(1/2) < 1/n$. Choosing $\,f = 3\log n\,$ satisfies the inequality and we are done.

We can make this prettier if we don't care about minimizing $f$. Suppose $n$ is one more than an odd prime and let $f=n-1$. Then there are no remainders since $n-1 \choose k$ is always a multiple of $n-1$. Thus $R(b) = b^{n-1} + (1-b)^{n-1}$ which clearly has a solution $R(b) = 1/n$. For cases where $n$ is not one more than an odd prime, use Dirichlet's Theorem to get a multiple of $n$ that is.

Using 2 Coins

The best I can do with two coins is $\sim 2\log n$ flips. Let one coin be fair and one coin have bias $1/n$. Let $f$ be such that $2^f \geq (n-1)^2$. Flip the fair coin $f$ times and the $1/n$ coin once. There are $2^{f+1}$ total outcomes, half of which have probability $\tfrac{1}{ 2^fn}$ and the other half have probability $\tfrac{n-1}{2^f n}$. Label the former $L$ and the latter $H$. We want to group these outcomes into bins of probability $\tfrac{2^f}{2^fn}$.

Add as many $H$ outcomes as possible to the first bin and denote the number $h_1 \geq n-1$. Fill the remainder with $t_1 < n-1 $ of the $T$ outcomes. Repeat for the next bin, and then the next, and so on. Because $h_i>t_i$, we run out of $H$ outcomes first and can fill the remaining bins with $L$ outcomes.

Remarks

A few more interesting observations. Let $F(n)$ be the minimum number of flips needed using a mutable coin (you can change the bias every flip). If $n=ab$, then we can "roll" an $a$ and $b$-sided die and take the result $b (r_a -1) + r_b$. Also, if $n = a+b$, then we flip an $a/n$-biased coin and then roll either an $a$ or $b$-sided die depending on whether the coin flip came up heads or tails. So we get the recurrence relations

$$ \begin{align} F(ab) &\leq F(a) + F(b) \\ F(a+b) &\leq 1 + \text{max}\{F(a), F(b)\} \\ \end{align} $$

The second relation let's us simulate an $n=2^k + 2^{\ell}_{(k > \ell)}$-sided die using 2 coins and $k+1$ flips.

Solution 2:

Here's a quite straightforward method with two coins, bounded number of throws, and both coins having rational values. First coin is unbiased; second coin has the following probability for a Head: $$p = \frac{2^m}{n!}; m = \lfloor{\log_2(n!)}\rfloor$$ With the unbiased coin you can emulate a biased coin which has $\frac{k}{2^m}$ probability for a Head ($k$ is less than $2^m$). So, using the two coins we can emulate a coin which has probability $\frac{1}{r}$ for a Head with $1\leq r \leq n$ (just emulate with the unbiased coin a biased coin with probability $\frac{n!}{r\cdot 2^m}$ for a Head). That would be enough to select uniformly from the set of $n$ people.

Example (simplified): $n=7$. Second coin $p=\frac{8}{21}$. With $3$ throws of the unbiased coin emulate a coin of $\frac{3}{8}$; using that and one additional throw of the biased coin we emulate a coin of: $$\frac{3}{8} \cdot \frac{8}{21} = \frac{1}{7}$$ Similarly, with 3 throws of the unbiased coin and a single throw of the biased coin we can emulate a coin of: $$\frac{7}{8} \cdot \frac{8}{21} = \frac{1}{3}$$ So, we actually have the following 'coins' to use: $$\frac{1}{2}, \frac{1}{3}, \frac{1}{7}$$ And these are enough to choose uniformly from a set of size $7$.