Optimal Coin Flipping

In this talk I will show how to simulate a coin of arbitrary real bias q with a coin of arbitrary real bias p with negligible loss of entropy. I will develop a coalgebraic model and use it to derive an information-theoretic lower bound that is strictly larger than the Shannon entropy. There are efficient protocols that approximate the lower bound to within any desired accuracy and achieve it exactly for p=1/2. It is an open question whether there are optimal computable protocols for any given rational p and q.  

hosted by