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 -