Finite-precision source resolvability

Yossef Steinberg, Sergio Verdu

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
Number of pages1
DOIs
StatePublished - Dec 1 1994
Event1994 IEEE International Symposium on Information Theory, ISIT 1994 - Trondheim, Norway
Duration: Jun 27 1994Jul 1 1994

Other

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

All Science Journal Classification (ASJC) codes

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

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

  • Cite this

    Steinberg, Y., & Verdu, S. (1994). Finite-precision source resolvability. In Proceedings - 1994 IEEE International Symposium on Information Theory, ISIT 1994 [394722] https://doi.org/10.1109/ISIT.1994.394722