Iterating von Neumann's procedure for extracting random bits

DOI10.1214/AOS/1176348543MaRDI QIDQ1192995zbMATH OpenOpenAlexWikidataFDO

Authors Yuval Peres

Publication date 27 September 1992

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1214/aos/1176348543

zbMATH Keywords

exchangeabilityexchangeable processesKeane-Smorodinsky finitary codesnumber of unbiased bitsrandom biased bits

Mathematics Subject Classification ID

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

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.

Recommendations

• Extraction of optimally unbiased bits from a biased source
• Fast and efficient construction of an unbiased random sequence
• Von Neumann's biased coin revisited
• Blind-friendly von Neumann's heads or tails
• Independent unbiased coin flips from a correlated biased source - a finite state Markov chain

Cited in

(27)

• Fast simulation of new coins from old
• An asymptotically optimal Bernoulli factory for certain functions that can be expressed as power series
• Von Neumann's biased coin revisited
• An introduction to randomness extractors
• Quantum Random Number Generation
• Universal finitary codes with exponential tails
• Bounds on Fixed Input/Output Length Post-processing Functions for Biased Physical Random Number Generators
• Extraction of optimally unbiased bits from a biased source
• Fast and efficient construction of an unbiased random sequence
• Non-contextual chocolate balls versus value indefinite quantum cryptography
• Some factors of nonsingular Bernoulli shifts
• ASYMPTOTIC ANALYSIS OF PERES’ ALGORITHM FOR RANDOM NUMBER GENERATION
• Heat-Bath Algorithmic Cooling with Correlated-Qubits Relaxation
• Simulating events of unknown probabilities via reverse time martingales
• Proved random numbers obtained from hardware devices
• Optimal coin flipping
• A quantum random number generator certified by value indefiniteness
• Randomness extraction in computability theory
• Coalgebraic tools for randomness-conserving protocols
• Extraction rates of random continuous functionals
• New coins from old, smoothly
• Sinai factors of nonsingular systems: Bernoulli shifts and Anosov flows
• On the extraction of random bit sequences in quantum random number generators with several independent Markov sources
• Simulating a coin with irrational bias using rational arithmetic
• Channel simulation: theory and applications to lossy compression and differential privacy
• A quantum-inspired post-processing method using collaborative mapping operators for random numbers and its application in image encryption
• Modular aggregation as a debiasing method for non-stationary discrete sources: convergence and numerical validation

This page was built for publication: Iterating von Neumann's procedure for extracting random bits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1192995)