Skip to main content


eCommons@Cornell

eCommons@Cornell >
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: http://hdl.handle.net/1813/12869
Title: Optimal Coin Flipping
Authors: Kozen, Dexter
Keywords: probability
entropy
randomness
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.
URI: http://hdl.handle.net/1813/12869
Appears in Collections:Computing and Information Science Technical Reports

Files in This Item:

File Description SizeFormat
Coinflip.pdf197.83 kBAdobe PDFView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us