Using your Head is Permitted

December 2014 solution

Part 1:

The answer is that every point in [0,1] is a casino. We have already shown last month that the n-sided dice for any n≥2 can be simulated by some biased coin with probability q. To solve this riddle, we show that any q-coin can be simulated by some coin in any neighbourhood of any length ε in [0,1] (and, in particular, by some coin in any neighbourhood of p).

The first step is to see that any q in (0,1) can be simulated by q1/k for any natural k. This is simple to do: throw the coin k times. The probability of getting "heads" in all throws is (q1/k)k=q, so we can take this event as one throw of the simulated coin.

This means that we can simulate any coin by a coin whose "heads" probability is arbitrarily close to 1. This is also true for coins whose "heads" probability is arbitrarily close to 0, because we can switch "heads" for "tails", so we can assume our q is arbitrarily close to 0.

Next, consider all q1/k (the coins that can simulate q by the procedure described above, and therefore, by transitivity, also the n-sided dice), when q is close to 0. What is the maximal difference between two consecutive values q1/k? A simple upper bound can be given by differentiating by k:

d(q1/k)/dk=-q1/k ln(q)/k2.    (1)

By the mean value theorem, for a given q, the maximal difference between two consecutive points is no more than the maximum of this differential over all k (not necessarily integer). Differentiating this again by k and equating to zero in order to find the k that yields the maximal value gives the equation k=-ln(q)/2. Substituting this back into Equation (1), we get that this upper bound is -4/(e2 ln q), where e is Euler's constant. By choosing an arbitrarily low q, this bound can be made as small as required, and specifically smaller than any ε.

Part 2:

Let us use a slightly different method to simulate an n-sided dice than was used in the October solution. We assume that n is not a power of 2. We will use one fair coin and one coin with probability 2k/n of falling on "heads", where k is the largest integer for which this is a valid probability. Simulating the n-sided dice is performed as follows:

First, throw the biased coin once. If it falls on "heads", throw the unbiased coin k times. The probability space has just been segmented to 2k segments of probability 1/n each and one segment with the remainder. Join to this remainder as many of the smaller segments as are needed in order to complete it to 2k/n, then, using an additional k unbiased coin throws (if needed), reduce this segment to 2k segments of probability 1/n each. The probability space now consists of n segments of equal probability and we are done.

(An alternative method of using the same coins is simply to throw the 2k/n coin once and the unbiased coin k times in order to simulate a 1/n coin [the probability of all k+1 tosses resulting in "heads" is 1/n], after which the method described in last month's solution can be used as-is.)

Next, consider that by simulating an nt-dice for any natural t, we are also simulating an n-dice. We want to show that by enumerating over t, the probability chosen for the biased coin covers the segment [1/2,1] densely. Specifically, consider the log2 of this probability. This is the fractional part of -t log2 n, minus 1. If n is not a power of 2, log2 n is irrational, so the sequence is known to cover [-1,0] densely, and the original probabilities cover [1/2,1] densely as required. This proves that for simulating an n-dice for an n value that is not a power of 2, any point in {1/2}×[1/2,1] provides a rational casino. If n is a power of 2 the same also holds, because one only needs the unbiased coin, and any probability can be chosen for the (subsequently ignored) biased coin.

By flipping "heads" and "tails", we see that all of {1/2}×[0,1] is a strip of casinos. Radu-Alexandru Todor and Lorenzo Gianferrari Pini, who sent this solution to me, dubbed this the "Lorenzo Strip".

As for the bonus question, the answer is that any point in [0,1]2 is a rational casino. Rudu and Lorenzo's original proof of this fact appears, untouched, here.

Back to riddle

Back to main page