Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computing and Information Science
  4. Computing and Information Science Technical Reports
  5. Optimal Coin Flipping

Optimal Coin Flipping

File(s)
Coinflip.pdf (197.83 KB)
Permanent Link(s)
https://hdl.handle.net/1813/12869
Collections
Computing and Information Science Technical Reports
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
probability
•
entropy
•
randomness
Type
article

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance