Generating Random Bits from an Arbitrary Source: Fundamental Limits

Sridhar Vembu, Sergio Verdú

Research output: Contribution to journalArticle

70 Scopus citations

Abstract

Suppose we are given a random source and want to use it as a random number generator; at what rate can we generate fair bits from it? We address this question in an information-theoretic setting by allowing for some arbitrarily small but nonzero deviation from “ideal” random bits. We prove our results with three different measures of approximation between the ideal and the obtained probability distributions: the variational distance, the d-bar distance, and the normalized divergence. Two different contexts are studied: fixed-length and variable-length random number generation. The fixed-length results of this paper provide an operational characterization of the inf-entropy rate of a source, defined in Han and Verdú [1] and the variable-length results characterize the liminf of the entropy rate, thereby establishing a pleasing duality with the fundamental limits of source coding. A feature of our results is that we do not restrict ourselves to ergodic or to stationary sources.

Original languageEnglish (US)
Pages (from-to)1322-1332
Number of pages11
JournalIEEE Transactions on Information Theory
Volume41
Issue number5
DOIs
StatePublished - Sep 1995

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Shannon theory
  • approximation theory
  • entropy
  • fixed-length source coding
  • random number generation
  • variable-length source coding

Fingerprint Dive into the research topics of 'Generating Random Bits from an Arbitrary Source: Fundamental Limits'. Together they form a unique fingerprint.

  • Cite this