Optimal Coin Flipping
Dexter Kozen ( Joseph Newton Pew, Jr. Professor in Engineering, Computer Science Department, Cornell University )
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 derive an information-theoretic lower bound that is strictly larger than the Shannon entropy. As a function of q, it is an everywhere discontinuous fractal. There are efficient protocols that achieve the lower bound to within any desired accuracy, and achieve it exactly for p=1/2. It is an open question whether there is a computable protocol that always achieves the lower bound for all rational p and q.