Using your Head is Permitted

November 2014 solution

Part 1:

Only dice where n=2^k for an integer k can be simulated using a single rational coin. Ignoring the degenerate case n=1, this can furthermore only be done using the fair coin. Using the fair coin, this can be done trivially by k flips of the coin, and, also trivially, cannot be done with less.

To show that no n-sided dice can be simulated by a single, rational, biased coin, consider a coin whose odds are p:q of falling on 'heads' vs. 'tails' (by which we mean that the probability of falling on 'heads' is p/(p+q)). Without loss of generality, let us assume that p>q. Furthermore, the odds are given here in fully reduced form, so p and q are known to be co-prime.

Suppose to the contrary that one was able to simulate an n-sided dice using such a coin by tossing it a times for some a. There are 2^a possible outcomes for the coin tosses, and we need to group these into sets so that the total probability in each set equals 1/n. In particular, the total probability in every set must be equal.

Each of the possible coin-toss outcomes occurs at probability pⁱq^(a-i)/(p+q)^a, where i is the number of times the coin falls on 'heads' in the outcome. Let us multiply all probabilities by (p+q)^a to obtain integers, and then consider the result modulo p. For all events, the result is zero, except for the event where i=0 (the coin fell a times on 'tails'), where the result is q^a≠0 (mod p).

Whichever way we sum these events, the result in modulo p will continue to be zero for all subsets, except for the one subset that includes the 'all-tails' event, which will have q^a≠0 (mod p) as its sum.

In particular, it cannot be true that all sets have the same sum.

For completion, we add that using the fair coin one cannot simulate any dice where n is not a power of two, because the probability sum of any set of possible outcomes when tossing the fair coin is a rational with a lowest denominator that is a power of 2. In particular, it cannot be 1/n.

Part 2:

Every n can be simulated using a single irrational coin. We will show how a single coin with probability p=p(n) of landing on 'heads' can simulate any n-sided dice. To see that p is necessarily irrational, we refer to Part 1, noting that p will never be 1/2 in our construction.

We will assume n>2. For n=2, merely choose p=sqrt(1/2), and simulate the dice (which is the fair coin in this case) by tossing it twice and checking if both outcomes are 'heads'.

Suppose that we toss the coin a times. This results in 2^a distinct possible outcomes, which we will now collate into sets.

For every i between 0 and a, there are exactly c_i=a-choose-i of the possible outcome events whose probability is pⁱ(1-p)^(a-i), these corresponding to the events where 'heads' appeared exactly i times. Let us label, within each one of these subgroups, exactly c_i div (n-1) of the events with each of the labels between 1 and n-1, this leaving c_i mod (n-1) to be labelled n. This labelling will form the dice's output.

Clearly, each output between 1 and n-1 has the same probability. We will show that with an appropriate choice of a and p, the probability of an n output can be made equal to the other probabilities.

First, note that it is always possible, by choosing a sufficiently large a, to make the number of events labelled n be smaller than 2^a/n. To see this, consider that for each of the a+1 possible i values, at most n-2 events will be labelled n, for a total of (a+1)(n-2). For this to be smaller than 2^a/n we need

2^a/(a+1)>n²-2n.

This means that asymptotically an a value on the order of 2 ceil(log₂n) should work, but let's use a=4 ceil(log₂n), instead. Let us verify that this value of a does, indeed, meet the condition of the equation.

We have 2^a≥n⁴, and n²>n²-2n, so a sufficient condition is

n⁴/(a+1)≥n²

a<n².

This means our chosen a works for all n values, given our assumption that n is greater than 2.

Under this choice of a, we have that the number of events labelled n is, in total, less than 1/n of the total number of possible outcome events. In other words, if we choose p=1/2, using the fair coin, a label of n will be output at too low a probability (because when using a fair coin, each outcome is of equal probability). However, suppose that we choose p=0, instead. Then, at probability 1, the output will be all-tails, which is a possibility labelled n, so n will be output at too high a probability.

The probability of outputting n is clearly a continuous function of p, so there must exist a value of p between 0 and 1/2 for which every label is output with equal probability, thus concluding our construction.

As for the bonus question:

Regardless of how many coins we use or what their probabilities are (including whether they are rational or irrational), a coin tosses result in exactly 2^a possible outcomes. For some grouping of these outcomes to yield n sets with a total probability of 1/n each, the original number of outcomes must be at least n. Hence we have a≥ceil(log₂ n) as an absolute lower bound for any strategy. Our construction is within a factor of 4 from this optimum (and asymptotically 2).