Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE-IMS Workshop on Information Theory and Statistics

Finite-precision intrinsic randomness and source resolvability

Yossef Steinberg, Sergio Verdú

Published Dec 17, 2002• 1 citation
Publisher

Abstract

Random number generators are important devices in randomized algorithms, Monte-Carlo methods, and in simulation studies of random systems. A random number generator is usually modeled as a random source emitting independent, equally likely random bits. In practice, the random source one has at hand can deviate from this idealized model, and the random number generator operates by applying a deterministic mapping on the output of the (nonideal) random source. The deterministic mapping is chosen so that the resulting process approximates, in some sense, a sequence of independent, equally likely random bits. A prime measure of the intrinsic randomness of a given source X is the maximal rate at which random bits can be extracted from X by suitably mapping its output. This maximal rate depends on the statistics of the source X and on the sense of approximation. We study the problem of finite-precision random bit generation, where the accuracy measure is the variational distance. The relevant information theory is addressed.

DOI
10.1109/wits.1994.513868

Related papers

Generating random bits from an arbitrary source: fundamental limits

Shankar Vembu, Sergio Verdú

Suppose we are given a random source and want to use it as a random number generator; at what rate can we generate fair bits from it? We address this question in an information-theoretic setting by allowing for some arbitrarily small but nonzero deviation from "ideal" random bits. We prove our results with three different measures of approximation between the ideal and the obtained probability distributions: the variational distance, the d-bar distance, and the normalized divergence. Two different contexts are studied: fixed-length and variable-length random number generation. The fixed-length results of this paper provide an operational characterization of the inf-entropy rate of a source, defined in Han and Verdu (see ibid., vol.39, no.3, p.752-772, 1993) and the variable-length results characterize the liminf of the entropy rate, thereby establishing a pleasing duality with the fundamental limits of source coding. A feature of our results is that we do not restrict ourselves to ergodic or to stationary sources.>

IEEE Transactions on Information Theory•Jan 1, 1995•106 citations

Quantum random number generators, extraction of provably random bit sequences from Markov chain trajectories

Igor M. Arbekov, S. N. Molotkov

One of the main problems in the construction of quantum random number generators Ð obtainment of a provably random output sequence from physical measurements, i.e., from an initial sequence generated by a physical random number generator Ð is investigated.The conceptual feasibility and the conditions under which randomness can be `reached,' as well as the meaning of the `provable randomness' term, are discussed.We consider the methods of extracting provably random bit sequences from stationary Markov chains of finite order, i.e., under the assumption of the finite depth of the dependence of the results of physical measurements on the prehistory, which is an adequate approximation of the real situation.The extraction of the output provably random bit sequence from the initial sequence of the results of physical measurements using V F Babkin's effective arithmetic coding method is demonstrated.It is shown that random bit sequences can be provably obtained even from primary sequences of the results of physical measurements, which are dependent on (correlated to) any finite depth (prehistory).We aim to reveal the connection of various approximations employed in the development and description of methods for obtaining random bit sequences with the basic physical limitations of Nature.The mathematical proofs are detailed to the level of practical algorithms applied in real random number generators.The necessary mathematical propositions are presented at an intuitive level for physicists, do not require prior knowledge in this area, and are comprehensible to undergraduate university students.

Physics-Uspekhi•Feb 1, 2024•4 citations

Approximation Theory of Output Statistics

Te Sun Han, S. Verdu

Given a channel and an input process we study the minimum randomness of those input processes whose output statistics approximate the original output statistics with arbitrary accuracy. We introduce the notion of resolvability of a channel, defined as the number of random bits required per channel use in order to generate an input that achieves arbitrarily accurate approximation of the output statistics for any given input process. We obtain a general formula for resolvability which holds regardless of the channel memory structure. We show that, for most channels, resolvability is equal to Shannon capacity. By-products of our analysis are a general formula for the minimum achievable (fixed-length) source coding rate of any finite-alphabet source, and a strong converse of the identification coding theorem, which holds for any channel that satisfies the strong converse of the channel coding theorem.

IEEE International Symposium on Information Theory (ISIT)•Aug 24, 2005•1 citation

Source-Independent Quantum Random Number Generation

Zhu Cao, Hongyi Zhou, Xiao Yuan +1 more

Quantum random number generators can provide genuine randomness by appealing to the fundamental principles of quantum mechanics.In general, a physical generator contains two parts-a randomness source and its readout.The source is essential to the quality of the resulting random numbers; hence, it needs to be carefully calibrated and modeled to achieve information-theoretical provable randomness.However, in practice, the source is a complicated physical system, such as a light source or an atomic ensemble, and any deviations in the real-life implementation from the theoretical model may affect the randomness of the output.To close this gap, we propose a source-independent scheme for quantum random number generation in which output randomness can be certified, even when the source is uncharacterized and untrusted.In our randomness analysis, we make no assumptions about the dimension of the source.For instance, multiphoton emissions are allowed in optical implementations.Our analysis takes into account the finite-key effect with the composable security definition.In the limit of large data size, the length of the input random seed is exponentially small compared to that of the output random bit.In addition, by modifying a quantum key distribution system, we experimentally demonstrate our scheme and achieve a randomness generation rate of over 5 × 10 3 bit=s.

arXiv:1508.04880•Physical Review X•Feb 25, 2016•153 citations

Channel intrinsic randomness

Matthieu R. Bloch

We study channel intrinsic randomness, defined as the maximum random bit rate that can be extracted from a channel output independently of an input with known statistics. Independence and uniformity of the extracted process are measured by means of the variational distance between distributions. We obtain an expression for channel intrinsic randomness in terms of the statistics of the channel and its input process, which holds for arbitrary discrete channels and arbitrary discrete inputs. We discuss the connection between channel intrinsic randomness and secret-key distillation, and show that channel intrinsic randomness appears as the natural operation behind key distillation. As a supporting result, we obtain achievable secret-key rates for compound sources.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•30 citations

Harnessing Nature’s Randomness: Physical Random Number Generator

Geraldo A. Barbosa

Random number generators are indispensable for a multi- tude of tasks; from electronic games to secure communications. Most gen- erators have been made either in software or determinist hardwired de- vices such as the Linear-Feedback-Shift-Registers; while gaining in costs or speed, the “random” sequences generated are actually deterministic, obeying clear generating algorithms, despite all randomness appearance of their outputs. From the other side, Nature presents a multitude of sources of true randomness that can be explored. Commercial random generators exist based on physical processes as the source of randomness. Difficulties are always present to extract Nature’s randomness. This paper presents guidelines for construction of a fast (telecommunication speed) Physical Random Number Generator. It discusses the fundamental physical ele- ments involved, technicalities of signal recording and its limitations, and the final bit extraction. The need for randomness tests is emphasized and the impossibility of guaranteeing true randomness of a finite sequence is discussed.

Journal of Information Security and Cryptography (Enigma)•Dec 7, 2015•0 citations
Random number generators are important devices in randomized algorithms, Monte-Carlo methods, and in simulation studies of random systems. A random number generator is usually modeled as a random source emitting independent, equally likely random bits. In practice, the random source one has at hand can deviate from this idealized model, and the random number generator operates by applying a deterministic mapping on the output of the (nonideal) random source. The deterministic mapping is chosen so that the resulting process approximates, in some sense, a sequence of independent, equally likely random bits. A prime measure of the intrinsic randomness of a given source X is the maximal rate at which random bits can be extracted from X by suitably mapping its output. This maximal rate depends on the statistics of the source X and on the sense of approximation. We study the problem of finite-precision random bit generation, where the accuracy measure is the variational distance. The relevant information theory is addressed.
Suppose we are given a random source and want to use it as a random number generator; at what rate can we generate fair bits from it? We address this question in an information-theoretic setting by allowing for some arbitrarily small but nonzero deviation from "ideal" random bits. We prove our results with three different measures of approximation between the ideal and the obtained probability distributions: the variational distance, the d-bar distance, and the normalized divergence. Two different contexts are studied: fixed-length and variable-length random number generation. The fixed-length results of this paper provide an operational characterization of the inf-entropy rate of a source, defined in Han and Verdu (see ibid., vol.39, no.3, p.752-772, 1993) and the variable-length results characterize the liminf of the entropy rate, thereby establishing a pleasing duality with the fundamental limits of source coding. A feature of our results is that we do not restrict ourselves to ergodic or to stationary sources.>
One of the main problems in the construction of quantum random number generators Ð obtainment of a provably random output sequence from physical measurements, i.e., from an initial sequence generated by a physical random number generator Ð is investigated.The conceptual feasibility and the conditions under which randomness can be `reached,' as well as the meaning of the `provable randomness' term, are discussed.We consider the methods of extracting provably random bit sequences from stationary Markov chains of finite order, i.e., under the assumption of the finite depth of the dependence of the results of physical measurements on the prehistory, which is an adequate approximation of the real situation.The extraction of the output provably random bit sequence from the initial sequence of the results of physical measurements using V F Babkin's effective arithmetic coding method is demonstrated.It is shown that random bit sequences can be provably obtained even from primary sequences of the results of physical measurements, which are dependent on (correlated to) any finite depth (prehistory).We aim to reveal the connection of various approximations employed in the development and description of methods for obtaining random bit sequences with the basic physical limitations of Nature.The mathematical proofs are detailed to the level of practical algorithms applied in real random number generators.The necessary mathematical propositions are presented at an intuitive level for physicists, do not require prior knowledge in this area, and are comprehensible to undergraduate university students.
Given a channel and an input process we study the minimum randomness of those input processes whose output statistics approximate the original output statistics with arbitrary accuracy. We introduce the notion of resolvability of a channel, defined as the number of random bits required per channel use in order to generate an input that achieves arbitrarily accurate approximation of the output statistics for any given input process. We obtain a general formula for resolvability which holds regardless of the channel memory structure. We show that, for most channels, resolvability is equal to Shannon capacity. By-products of our analysis are a general formula for the minimum achievable (fixed-length) source coding rate of any finite-alphabet source, and a strong converse of the identification coding theorem, which holds for any channel that satisfies the strong converse of the channel coding theorem.
Quantum random number generators can provide genuine randomness by appealing to the fundamental principles of quantum mechanics.In general, a physical generator contains two parts-a randomness source and its readout.The source is essential to the quality of the resulting random numbers; hence, it needs to be carefully calibrated and modeled to achieve information-theoretical provable randomness.However, in practice, the source is a complicated physical system, such as a light source or an atomic ensemble, and any deviations in the real-life implementation from the theoretical model may affect the randomness of the output.To close this gap, we propose a source-independent scheme for quantum random number generation in which output randomness can be certified, even when the source is uncharacterized and untrusted.In our randomness analysis, we make no assumptions about the dimension of the source.For instance, multiphoton emissions are allowed in optical implementations.Our analysis takes into account the finite-key effect with the composable security definition.In the limit of large data size, the length of the input random seed is exponentially small compared to that of the output random bit.In addition, by modifying a quantum key distribution system, we experimentally demonstrate our scheme and achieve a randomness generation rate of over 5 × 10 3 bit=s.
We study channel intrinsic randomness, defined as the maximum random bit rate that can be extracted from a channel output independently of an input with known statistics. Independence and uniformity of the extracted process are measured by means of the variational distance between distributions. We obtain an expression for channel intrinsic randomness in terms of the statistics of the channel and its input process, which holds for arbitrary discrete channels and arbitrary discrete inputs. We discuss the connection between channel intrinsic randomness and secret-key distillation, and show that channel intrinsic randomness appears as the natural operation behind key distillation. As a supporting result, we obtain achievable secret-key rates for compound sources.
Random number generators are indispensable for a multi- tude of tasks; from electronic games to secure communications. Most gen- erators have been made either in software or determinist hardwired de- vices such as the Linear-Feedback-Shift-Registers; while gaining in costs or speed, the “random” sequences generated are actually deterministic, obeying clear generating algorithms, despite all randomness appearance of their outputs. From the other side, Nature presents a multitude of sources of true randomness that can be explored. Commercial random generators exist based on physical processes as the source of randomness. Difficulties are always present to extract Nature’s randomness. This paper presents guidelines for construction of a fast (telecommunication speed) Physical Random Number Generator. It discusses the fundamental physical ele- ments involved, technicalities of signal recording and its limitations, and the final bit extraction. The need for randomness tests is emphasized and the impossibility of guaranteeing true randomness of a finite sequence is discussed.