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 2a 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 piq(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 qa≠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 qa≠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.
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 2a distinct possible outcomes, which we will now collate into sets.
For every i between 0 and a, there are exactly ci=a-choose-i of the possible outcome events whose probability is pi(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 ci div (n-1) of the events with each of the labels between 1 and n-1, this leaving ci 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 2a/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 2a/n we need
This means that asymptotically an a value on the order of 2 ceil(log2n) should work, but let's use a=4 ceil(log2n), instead. Let us verify that this value of a does, indeed, meet the condition of the equation.
We have 2a≥n4, and n2>n2-2n, so a sufficient condition is
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 2a 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(log2 n) as an absolute lower bound for any strategy. Our construction is within a factor of 4 from this optimum (and asymptotically 2).
When I published the October riddle, I said that it was a "classic" riddle, meaning that it's been around for so long that its origin has been lost. Turns out, I was wrong about this: the origin was not lost. Amir Sarid sent me the following link to what appears to be the origin of this riddle, and where many of its natural follow-ups are discussed, such as the one featured as this month's riddle.
Back to riddle
Back to main page