TY - GEN

T1 - Finite-precision source resolvability

AU - Steinberg, Yossef

AU - Verdú, Sergio

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84894318438&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84894318438&partnerID=8YFLogxK

U2 - 10.1109/ISIT.1994.394722

DO - 10.1109/ISIT.1994.394722

M3 - Conference contribution

AN - SCOPUS:84894318438

SN - 0780320158

SN - 9780780320154

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 296

BT - Proceedings - 1994 IEEE International Symposium on Information Theory, ISIT 1994

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 1994 IEEE International Symposium on Information Theory, ISIT 1994

Y2 - 27 June 1994 through 1 July 1994

ER -