Iterating von Neumann's procedure for extracting random bits (Q1192995): Difference between revisions

Let \(\{X_ i\}_{i=1,2,\dots,n}\) be a sequence of independent random variables with \(p=P(X_ i=0)\neq 1/2\) and \(q=1-p=P(X_ i=1)\), where \(p\) is unknown. The \(X_ i\)'s are so-called random biased bits. Without assuming prior knowledge of \(p\) the first consideration is to extract from the \(X_ i\)'s as many as possible independent unbiased bits by the help of a simple procedure by von Neumann (1951). Given \(n\) biased bits, this procedure extracts approximately \(np(1-p)\) unbiased bits. The aim of this paper is to show that the number of unbiased bits produced by iterating this procedure is arbitrarily close to the entropy bound. The proof is based on a functional equation satisfied by the entropy function. In the last section an extension to exchangeable processes and a discussion on the relationship to the Keane-Smorodinsky finitary codes are given.