Efficient generation of random bits with a biased coin

Abstract

In his seminal work, von Neumann (1951) raised the question of simulating a fair coin with a biased one. The simple but inefficient procedure proposed by him was later shown by Peres (1992) to attain the entropy bound asymptotically if properly iterated. We investigate the second-order efficiency of Peres’ procedure when the number of (biased) coin tosses is large. Building on the work of Zhao and Bruck (2012) and Pae (2020), we also discuss the streaming version of Peres’ procedure and its generalization when the biased coin is replaced by a loaded die. (This talk is based on joint work with Zhaoging Lim.)

Please click here for participating the talk online

Download