Interval Algorithm for Random Number Generation: Information Spectrum Approach

DOI10.1109/TIT.2019.2946235MaRDI QIDQ5123813zbMATH OpenOpenAlexFDO

Authors Shun Watanabe, Te Sun Han

Publication date 29 September 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.09782

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Measures of information, entropy (94A17) Stationary stochastic processes (60G10) Combinatorial probability (60C05)

Abstract: The problem of exactly generating a general random process (target process) by using another general random process (coin process) is studied. The performance of the interval algorithm, introduced by Han and Hoshi, is analyzed from the perspective of information spectrum approach. When either the coin process or the target process has one point spectrum, the asymptotic optimality of the interval algorithm among any random number generation algorithms is proved, which demonstrates utility of the interval algorithm beyond the ergodic process. Furthermore, the feasibility condition of exact random number generation is also elucidated. Finally, the obtained general results are illustrated by the case of generating a Markov process from another Markov process.

Recommendations

• Interval algorithm for random number generation
• Optimized random number generation in an interval
• Performance Analysis of the Interval Algorithm for Random Number Generation Based on Number Systems
• scientific article; zbMATH DE number 1504812
• Algorithmic Randomness
• Algorithms for generating random variables with a rational probability-generating function
• Randomized algorithms and pseudorandom numbers
• A Natural Algorithm for Generation of Pseudo-Random Numbers and its Applications
• On an algorithm to generate weakly correlated random numbers

Cited in

(3)

• Optimized random number generation in an interval
• Channel simulation: theory and applications to lossy compression and differential privacy
• Constructions of plateaued correctors with high correction order and good nonlinearity via Walsh spectral neutralization technique

This page was built for publication: Interval Algorithm for Random Number Generation: Information Spectrum Approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5123813)