Faculty of Computing and Information Science >
Computing and Information Science >
Computing and Information Science Technical Reports >
Please use this identifier to cite or link to this item:
|Title: ||Optimal Coin Flipping|
|Authors: ||Kozen, Dexter|
|Issue Date: ||2-Jun-2009|
|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.|
|Appears in Collections:||Computing and Information Science Technical Reports|
Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.