Optimal Coin Flipping
Author
Kozen, Dexter
Abstract
This paper studies the problem of simulating a coin of arbitrary real bias q with a coin of arbitrary real bias p with minimum loss of entropy. We establish a lower bound that is strictly greater than the information-theoretic bound. We show that as a function of q, it is an everywhere-discontinuous self-similar fractal. We provide efficient protocols that achieve the lower bound to within any desired accuracy for (3-sqrt(5))/2 < p < 1/2 and achieve it exactly for p=1/2.
Sponsorship
NSF CCF-0635028
Date Issued
2009-06-02T20:54:14Z
Keywords
Type
article