Is there a possibility to choose fairly from three items when every choice can only have 2 options

Me and my wife are often not knowing which DVD to watch. If we have two options we have a simple solution, I put one DVD in one hand behind my back and the other DVD in the other hand. She will randomly choose a hand and the DVD I have in that hand will be the one to watch.

This procedure is easy to expand to any power of 2. If we have 4 DVD's I hold 2 in one hand, 2 in the other. When a pair of DVD's is chosen, I split them out to two hands and she choses again.

The question is, what can we do when we have 3 DVD's. The assumptions we make are:

• I am not impartial. If I can influence the result somehow I will try to do that
• My wife really choses randomly a side every-time, independent of what she chose earlier.
• I don't have any other place to hide the DVD's, so every DVD is either visible or in one of the two hands.

As requirement we have that it must be a procedure with a predetermined number of steps. Not more, not less. If this is not possible, a solution that guarantees to finish with an upperbound, this is a good second choice. Off course the DVD we choose must be really random!

Solution 1:

Nice question. Firstly, there's no solution which will always take a fixed number of steps each time: after n independent random trials (choosing a hand), there are 2ⁿ possible choices, and 2ⁿ is never divisible by 3. (Equivalently: 1/3 does not have a terminating representation in base 2.)

But you can come up with solutions that terminate within a fixed number of steps with high probability. Note that you need at least 2 trials, since log₂(3) > 1. Here's one simple method:

1. Hold 2 DVDs in one hand and 1 DVD in other (your wife doesn't know which is which).

2. If the hand with 2 DVDs is chosen: play them against each other.
   Else: If the 1 DVD is chosen: play it against an empty hand.

Each of the 3 DVDs has equal probability 1/4 of being chosen, and with probability 1/4, you have to repeat from scratch. This solution takes 2 trials with probabilty 3/4, 4 trials with probability (1/4)(3/4), 6 trials with probability (1/4)²(3/4) and so on, so takes an expected number of 8/3 (≈ 2.66) trials. (See geometric distribution.)

I believe this is optimal (famous last words?) if you just have to choose out of 3 DVDs once. Probably, if you're going to choose from 3 DVDs many times, you can do better in the long run (amortised) and achieve the lower bound of log₂ 3 ≈ 1.58 trials on average, by "caching" some random choices from last time. (But will you remember them? :-)) At least you can do something similar when generating random numbers (see also this mildly related Stack Overflow thread), but in this case with game-theoretic fairness complications I'm not so sure.

Solution 2:

In 1976, Knuth and Yao proved a result that may help you choose a DVD out of 5, 6, etc. (I couldn't find a good reference online.) Consider the following problem: You have a fair coin and you must write an algorithm that outputs 1 with probability p1, outputs 2 with probability p2, ..., and outputs n with probability pn. (p1+p2+...+pn=1) Note that any possible algorithm can be described in terms of certain (possibly infinite) binary trees: A node that has two children means "throw a coin and pick one of the children according to the result"; a leaf is tagged with one of the numbers 1, 2, ..., n and means "output that number".

An optimal tree that solves the problem has one leaf k on level m if and only if the m-th bit of pk is 1. Otherwise there are zero such leafs.

"Optimal" here means not only that the average runtime is as good as possible, but the stronger guarantee that the probability of running more than m steps is not worse than that of any other algorithm that solves the problem correctly.

In your case, p1=p2=p3=0.01010101... The digit just before dot corresponds to the root (level 0) and and the subsequent digits to subsequent levels. So a tree that has no leaf on levels 0 and 1, has leafs (1, 2, and 3) on level 2, has no leaf on level 3, ... is optimal. This is exactly the solution given by ShreevatsaR. Such a tree is fairly easy to find once you know what leafs you need to put on each level.

As another example, if p1=...=p6=1/6=0.00101010101..., then you should have leafs (one of each 1, 2, 3, 4, 5, 6) on levels 3, 5, 7, and so on. If you draw a symmetric tree that obeys this you'll find how to choose one DVD out of 6: First grab three with each hand, then do what ShreevatsaR said for three. You are also guaranteed that it's optimal.

Now you can mock me and my friends for using a suboptimal algorithm for allocating hotel rooms.

Solution 3:

There is no such procedure which has an upperbound on number of steps. Here is proof. Let there is such procedure with no more then $N$ steps. On each step you basicly generate random integer between $1$ and $2$. Consider all possible sequences of no more than $N$ generated numbers. Every such sequence has probability of form $\frac{x}{2^N}$.

Consider sequences for which the procedure says "1" (the result is equal to $1$). The sum of theirs probabilities is $\frac{x_1}{2_N}$. It also must be equal to $\frac{1}{3}$. But $\frac{x_1}{2_N}$ can't be equal to $\frac{1}{3}$.

Solution 4:

I will answer to the letter of your question. DVDs A, B, C.

1. Hold A & B behind back. Wife chooses (say A). Drop B.
2. Hold chosen (A) & C behind back. Wife chooses.
3. If it is the other (C), a) then hold C and B behind back. Wife gets to pick (as always): Voila. b) else go bed.

All conditions met. 3 steps.