Iterating von Neumann's procedure for extracting random bits
type: Item
instance of: scholarly article
title: Iterating von Neumann's procedure for extracting random bits
zbMATH Open document ID: 0754.60040
author: Yuval Peres
published in: The Annals of Statistics
publication date: 1992-09-27T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 60G35
Mathematics Subject Classification ID: 94A17
Mathematics Subject Classification ID: 60G09
zbMATH DE Number: 61860
zbMATH Keywords: exchangeability
zbMATH Keywords: random biased bits
zbMATH Keywords: number of unbiased bits
zbMATH Keywords: exchangeable processes
zbMATH Keywords: Keane-Smorodinsky finitary codes
Wikidata QID: Q55924085
reviewed by: Ludwig Paditz
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aos/1176348543
OpenAlex ID: W1987434335
DOI: 10.1214/AOS/1176348543
description: scientific article; zbMATH DE number 61860