Sun Sep 15 14:50:13 UTC 2024: ## Turning Biased Coins into Fair Ones: A Journey into Randomness Extraction
A recent article by Marton Trencseni dives into the fascinating world of randomness extraction, exploring how to generate truly random output from a stream of potentially biased and correlated input bits.
Building upon his previous work on creating fair coins from biased ones, Trencseni demonstrates that this is a specific case of a broader problem known as deterministic randomness extraction. Using the concept of entropy, he explains that the goal is to convert an input bit stream with less than one bit of entropy per bit into an output stream with near-perfect randomness, i.e., close to one bit of entropy per bit.
The article explores various approaches to randomness extraction, starting with the classic **Von Neumann rule**, which effectively generates a fair coin toss from an input bit stream with independent and identically distributed (iid) bits. However, Trencseni points out that this method fails when dealing with input streams where individual bits have varying biases.
To address this, he introduces the **ParityExtractor**, which leverages the parity of N-bit blocks to reduce bias and produce a more uniform output stream as N increases.
Further, the article delves into the scenario where the input bits are generated by a **Markov Chain process**, demonstrating how to utilize the internal state information to effectively apply the Von Neumann rule.
Finally, Trencseni acknowledges that creating perfectly uniform bits from an unknown input stream with correlated bits is impossible. He emphasizes the need for further analysis, suggesting future exploration of statistical tests to assess the randomness of the generated output streams.
Overall, this article provides a clear and insightful introduction to the fundamental concepts and techniques of randomness extraction, showcasing its practical implications in various scenarios. The Python code examples and accessible explanations make this a valuable resource for anyone interested in exploring the intriguing world of randomness and its manipulation.
First Piper 