Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
3  
A similar question is asked on SO, but it uses rejection method so there's an infinitesimal chance that the procedure won't end. –  KennyTM Aug 1 '10 at 8:39
add comment

3 Answers

up vote 10 down vote accepted

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 2n possible choices, and 2n 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 log2(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)2(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 log2 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.

share|improve this answer
1  
Note that the protocol above is the same as the OP's 4-DVD protocol, with 3 "real" DVDs and one "null" DVD. It's optimal among such variants of power-of-2 protocols, and the following messy argument proves it's optimal (w.r.t expectation) among all (I think): in any protocol, it's impossible to have decided after 1 trial, as that would mean some DVD has probability 1/2 > 1/3. After 2 trials, of the 4 outcomes either 3 terminate or ≤1 (as 1/4 < 1/3 < 2/4). If ≤1, then need at least 3 trials with probability at least 3/4, so expectation is at least (1/4)2 + (3/4)3 > 8/3. –  ShreevatsaR Aug 1 '10 at 9:52
    
Also, "random" does not mean "uniformly distributed" (though it's commonly used in that sense), so if you're willing to accept probabilities like (3/8, 3/8, 2/8) or (5/16, 5/16, 6/16) as being "close enough", then of course you can do it in a fixed predetermined number of steps. –  ShreevatsaR Aug 1 '10 at 11:02
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
Wow, nice result! It's always nice to know that such a natural algorithm is also optimal. –  ShreevatsaR Aug 1 '10 at 22:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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