Finite-precision source resolvability

Yossef Steinberg, Sergio Verdú

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The paper studies the minimum randomness necessary for finite precision simulation of a random source. In random process simulation, the objective of the simulator is to approximate a set of desired statistics. To this end, the simulator has access to a source of pure random bits-a random number generator-and the approximation is achieved by properly mapping the output of the random number generator to the alphabet of the approximated process. An important question that arises is what is the number of pure random bits per source output that the most efficient simulation scheme needs in order to produce every sample path of the approximating process. The answer to this question depends on the statistics of the approximated source and on the sense of approximation. If the objective was to produce-with the aid of only pure random bits-exactly the same statistics (distributions) as that of the desired process, then one could only simulate finite alphabet random processes whose statistics admit finite binary representations. For example, an exact simulation of a binary process with irrational probabilities is not feasible, since the number of fair bits per source output required for accurate simulation is infinite.

Original languageEnglish (US)
Title of host publicationProceedings - 1994 IEEE International Symposium on Information Theory, ISIT 1994
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages296
Number of pages1
ISBN (Print)0780320158, 9780780320154
DOIs
StatePublished - 1994
Event1994 IEEE International Symposium on Information Theory, ISIT 1994 - Trondheim, Norway
Duration: Jun 27 1994Jul 1 1994

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095

Other

Other1994 IEEE International Symposium on Information Theory, ISIT 1994
Country/TerritoryNorway
CityTrondheim
Period6/27/947/1/94

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Applied Mathematics
  • Modeling and Simulation

Fingerprint

Dive into the research topics of 'Finite-precision source resolvability'. Together they form a unique fingerprint.

Cite this