Affine Mess

This post contains a problem set that was used at the recent Julia Robinson Math Festival. I created this set after hearing about these problems from colleagues at Google. Enjoy!

In this problem set we will be flipping coins and using them to make various kinds of decisions. A bit of terminology:

• A fair coin is a coin you can flip and it comes up Heads (H) or Tail (T) with equal probability.
• A biased coin with bias is a coin which comes up H with probability , and T with probability .

Problems:

1. How can you use a fair coin to choose between 4 alternatives, uniformly at random? By “uniformly” we mean that you should give no special preference to any of the options. By “at random” we mean that you actually rely on the randomness provided by the coin to ensure that nobody can guess what your choice would be.
2. How about 8 alternatives? 16?
3. Suppose now you have a fair die, which comes up 1, 2, 3, 4, 5 or 6 with equal probabilities. It’s easy to use a die to choose between 6 alternatives, but how can you use it to choose uniformly between five alternatives?
4. Back to the coin, how would you use a fair coin to choose uniformly between three alternatives?
5. How many flips does your method take, on average? How many flips does it require in the worst case?

If you’ve solved the last part correctly, the next question will make sense.

1. Is it possible to fix this worst case behavior? Can you choose among 3 alternatives with a fair coin using 1,000 flips in the worst case?
2. Let’s say you only need to choose between two alternatives, uniformly at random, however the coin you have may be biased, and you don’t even know what the bias is. What would you do? Again, what’s the worst case behavior?

From now on, we will insist on having methods that only require a specific, finite number of flips. You get to choose how many flips you need but once you did, the method must always work and take no more than this number.

1. Once again you need to choose between 3 alternatives. You may now use two coins rather than just one, and you are free to pick what biases you’d like each of the coins to have (they can be differently biased). In addition, there must be some specific number such that your method never requires the coins to be flipped more than times.
2. Now try to tackle 5 alternatives, again using a fixed number of flips and two coins – you can choose what biases you’d like them to have.
3. How about 7 alternatives? 9? Again, you choose the coins, and you decide how many flips you need – but you can never take longer than that.
4. How about 15?
5. Can you do this in general? For every integer , find a pair of biased coins such that you can choose between alternatives, uniformly at random, using a fixed number of flips of the two coins.

Now we’re going to raise the stakes…

1. Let’s go back to the 3 alternatives. Can you uniformly choose between them with a single coin, and a fixed number of flips? Again, you get to choose which coin you want. (Hint: consider a general coin with bias $p$, and fix some small number of flips. What are the possible outcomes? Some of them have the same probability, and since you’re free to choose $p$ you can dictate a value for that probability. Which useful value would allow you to simulate the two coins you’ve used before?)
2. How about 5 alternatives?
3. How about the general case? Think of ways to simulate the two coins you used above with a single coin.
4. In fact, show that given any finite distribution with rational values, there is a single coin with which you can simulate that distribution in a fixed number of flips.

If you solved these problems correctly, the biases you used were irrational numbers. This has to be the case:

1. Suppose you have a p-coin with which you can choose between 2 alternatives in a fixed number of flips. Suppose that . Prove that p must be irrational.

Send article as PDF to