An efficient generation method for uniformly distributed random numbers
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.
- Efficient conversion of random sequences into equiprobable and independent sequences
- Fast and efficient construction of an unbiased random sequence
- Algorithms for almost-uniform generation with an unbiased binary source
- Source code with cost as a nonuniform random number generator
- Generating Uniformly Distributed Random Numbers without Floating Point Operations
- Present random computations in a uniform way
- Bit-parallel random number generation for discrete uniform distributions
- Watermelon uniform random generation with applications
- scientific article; zbMATH DE number 3890431 (Why is no real title available?)
- Generating Uniformly Distributed Random Numbers without Floating Point Operations
- A system of high-dimensional, efficient, long-cycle and portable uniform random number generators
- Algorithms for almost-uniform generation with an unbiased binary source
- scientific article; zbMATH DE number 1286145 (Why is no real title available?)
- Source codes as random number generators
- Source code with cost as a nonuniform random number generator
- scientific article; zbMATH DE number 1512196 (Why is no real title available?)
- scientific article; zbMATH DE number 3994872 (Why is no real title available?)
- On precise achievable conditions in resolvability problem based on the asymptotic normality
- A Random Version of Shepp's Urn Scheme
- Generation of uniform distribution robust to nonequiprobability of the initial digits
- Optimized random number generation in an interval
This page was built for publication: An efficient generation method for uniformly distributed random numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1812336)