[seqfan] Re: On simulating dice by coins

[Jens Voß]

----------------------------------------------------------------------
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 
> 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
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/