Iterating von Neumann’s procedure for extracting random bits. (English) Zbl 0754.60040

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.
Reviewer: L.Paditz (Dresden)


60G35 Signal detection and filtering (aspects of stochastic processes)
94A17 Measures of information, entropy
60G09 Exchangeability for stochastic processes
Full Text: DOI