An efficient generation method for uniformly distributed random numbers (Q1812336): Difference between revisions

The generation of uniformly distributed random numbers from nonuniformly distributed ones with a given arbitrarily small error is discussed. A Bernoulli source is considered which generates a sequence of symbols \(x_1, x_2, \ldots\), \(x_i \in A\) with a given input alphabet \(A\). The problem is to transform the input sequence into a sequence of binary digits \(0\) and \(1\) in such a way that the generated distribution \(\widetilde U\) on set \(\{0,1 \}^n\) (\(n \geq 1\)) differs from the uniform one \(U\) no more than by a prescribed error \(\rho \geq 0\) in the sense of some metric \(d\), i.~e., \(\lim\limits_{n \to \infty} d(\widetilde U^n,U^n) \leq \rho\). For three different metrics, the existence of transformations has been proven such that the complexity of the method as a function of the error \(\rho\) is given by the equalities \[ T=O \left( \log \frac{1}{\rho} \log \log \frac{1}{\rho} \log \log \log \frac{1}{\rho} \right), \] where \(T\) is the processing time per input symbol, and \(S=O \left( \log \frac{1}{\rho} \right)\), where \(S\) is the required memory size. The specific methods which fulfil these requirements are shown to be the arithmetic coding in the case of known source statistics and the arithmetic coding with application of imaginary sliding window in the case of unknown statistics of the Bernoulli source. Not imaginary sliding window requires \(S=O \left( \frac{1}{\rho} \right)\) memory in this case. Complexity of the proposed methods is lower in order than that of the known ones.