Simulation of Individual Sequences Using Training Data

Simulation of random process is one of classic problems in information theory. The simulation problem finds its wide applications in generative AI's, as well as generation of noise for the purpose of simulating various physical systems. We revisit a simulation problem for individual sequences, and propose universal simulation schemes for a given training sequence <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$x^{n}$</tex> with its length <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex>. Our goal is to find a good deterministic mapping which generates sequences <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$y^{n}$</tex> simulating <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$x^{n}$</tex> from uniform random numbers. As criteria of good simulation schemes, we deal with the following two conditions: 1) <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$y^{n}$</tex> is statistically similar to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$x^{n}$</tex>, 2) If <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$y^{n}$</tex> satisfies condition 1), there is as much uncertainty as possible in the choice of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$y^{n}$</tex>. We propose two simulation schemes based on the interval algorithm which can be executed with the computational complexity of the order <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(n)$</tex>. Both schemes satisfy the condition 1), and their output entropy rates are clarified. Further, any simulation scheme which satisfies the condition 1) cannot provide significantly larger output entropy rate than our proposed schemes. This reveals the asymptotical optimality of the proposed simulation schemes.