[seqfan] On simulating dice by coins

Jens Voß jens at voss-ahrensburg.de
Sun Dec 21 22:26:40 CET 2014


If you have looked at the October, November and December riddles of 
Michael Brand's site "Using your Head is Permitted" 
(http://www.brand.site.co.il/riddles/usingyourhead.html), you are aware 
of the question about how a fair n-sided die D_n can be simulated by a 
finite number of throws with a (possibly biased) coin C_p which will 
show "heads" with a probability p € [0,1].

The solution of the November riddle shows that this is possible for all 
n, so for a given n, I would like to find the smallest number k such 
there exists a C_p such that D_n can be simulated by k throws of C_p.

Obviously, if n = 2^k, then k throws of a fair coin can simulate a D_n, 
and there is no way of doing so with fewer throws, so for powers of 2, 
the problem is trivial.

For other n, the November riddle solution shows that p is necessarily 
irrational, and k is bounded by the smallest number j such that n * 
sum(i=0..k, binomial(j,i) mod (n-1) ) < 2^n, a sequence that I recently 
submitted as http://oeis.org/A251738.

My feeling is that it is very likely that, for n not a power of 2, 
A251738(n) is in fact equal to the smallest k for which a C_p simulates 
a D_n, but that a proof would be quite difficult - just try it out for n=3!

Does anyone know of any results that could yield a proof for my hypothesis?

Best regards,
Jens




More information about the SeqFan mailing list