# [seqfan] Re: On simulating dice by coins

Jens Voß jens at voss-ahrensburg.de
Sun Jan 25 15:34:33 CET 2015

```----------------------------------------------------------------------
NOTE: This message has become quite long, and I won't resent anyone who
decides to skip reading it, but at the end, I am asking for help in
choosing an algorithm for finding zeros of polynomials - if you can give
me a hint there, I would really appreciate it (even if you don't read my
whole posting)!!
----------------------------------------------------------------------

Since there have been no answers to my December posting so far, I have
spent some more time on the subject myself and have been making some
progress.

One possible reason why nobody has been able to help me prove my
hypothesis could simply be that it is about as false as possible: For
all n other than 3 or powers of 2, the number of biased coin throws
necessary to simulate a fair n-sided die is (or, to be more exact:
appears to be (I have only been able to verify it for n < 20)) strictly
less than A251738(n).

Recall that in order to simulate a fair n-sided die D_n by k throws of a
biased coin C_p which has a probability of p € (0,1) of landing on
heads, we need to find non-negative integer coefficients a_(i,j) (for i
€ {1, ..., n}, j € {0, ..., k}) such that

(*) For all j € {0, ..., k}, Sum_(i=1)^n a_(i,j) = (k choose j)
(**) For all i € {1, ..., n}, Sum_(j=0)^k a_(i,j) p^j (1-p)^(k-j) = 1/n

Clearly, if n is not a power of 2 and k >= A251738(n), then we can find
a p € (0, 1/2) such that (*) and (**) are satisfied for

a_(1,j) := (k choose j) mod (n-1)   for all j € {0, ..., k}
a_(i,j) := (k choose j) div (n-1)   for all i € {2, ..., n}, j € {0,
..., k}

My 2014 hypothesis was that for k smaller than A251738(n), there is no
such choice of a_(i,j). But this turned out to be completely wrong as
can already be seen for n = 5:

Choose p := 1/2 - sqrt(5)/10 and q := 1 - p. Then it is easy to verify that

5 p^3 q^2 + 5 p^2 q^3
= p^4 q + 3 p^3 q^2 + 3 p^2 q^3 + p q^4
= 2 p^4 q + p^3 q^2 + p^2 q^3 + 2 p q^4
= p^5 + q^5
= 1/5,

so if A = (a_(i,j))_(i=1..n,j=0..k) is the matrix

/ 0 0 5 5 0 0 \
| 0 1 3 3 1 0 |
| 0 2 1 1 2 0 |
| 0 2 1 1 2 0 |
\ 1 0 0 0 0 1 /

then (*) and (**) are satisfied, which shows that the number of coin
throws necessary to simulate a D_5 is <= 5
which is strictly less than A251738(5) = 6.

I have written a Java program to help me find the real minimal values
(which I plan to submit as A253676). This program involves determining
whether or not a certain polynomial with rational coefficients has a
zero within the interval (0, 1). I have been checking this in an
extremely naive manner - tested whether one of the values f(0), f(.01),
f(.02), ... , f(0.99), f(1) yields a sign change. Of course, this can
become quite risky especially for higher degree polynomials, so I would
like to know whether there is an efficient algorithm to reliably test
whether a rational polynomial f(x) has a root in (0,1) (without actually
having to find that possible root).
Are there any experts around who can point me towards a description of
such an algorithm? Maybe even a Java implementation?

Best regards,
Jens

Am 21.12.2014 um 22:26 schrieb Jens Voß:
>
> If you have looked at the October, November and December riddles of
> 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
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/

```