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

arXiv:1704.09007

Entropy of Independent Experiments, Revisited

Maciej Skórski

Published Apr 28, 2017• 0 citations
arXivHTMLPDF

Abstract

The weak law of large numbers implies that, under mild assumptions on the source, the Renyi entropy per produced symbol converges (in probability) towards the Shannon entropy rate. This paper quantifies the speed of this convergence for sources with independent (but not iid) outputs, generalizing and improving the result of Holenstein and Renner (IEEE Trans. Inform. Theory, 2011). (a) we characterize sources with \emph{slowest convergence} (for given entropy): their outputs are mixtures of a uniform distribution and a unit mass. (b) based on the above characterization, we establish faster convergences in \emph{high-entropy} regimes. We discuss how these improved bounds may be used to better quantify security of outputs of random number generators. In turn, the characterization of "worst" distributions can be used to derive sharp "extremal" inequalities between Renyi and Shannon entropy. The main technique is \emph{non-convex programming}, used to characterize distributions of possibly large exponential moments under certain entropy.

DOI
10.48550/arxiv.1704.09007

Related papers

Equivocations, Exponents, and Second-Order Coding Rates Under Various Rényi Information Measures

Masahito Hayashi, Vincent Y. F. Tan

We evaluate the asymptotics of equivocations, their exponents as well as their second-order coding rates under various Rényi information measures. Specifically, we consider the effect of applying a hash function on a source and we quantify the level of non-uniformity and dependence of the compressed source from another correlated source when the number of copies of the sources is large. Unlike previous works that use Shannon information measures to quantify randomness, information, or uniformity, we define our security measures in terms of a more general class of information measures-the Rényi information measures and their Gallager-type counterparts. A special case of these Rényi information measure is the class of Shannon information measures. We prove tight asymptotic results for the security measures and their exponential rates of decay. We also prove bounds on the second-order asymptotics and show that these bounds match when the magnitudes of the second-order coding rates are large. We do so by establishing new classes non-asymptotic bounds on the equivocation and evaluating these bounds using various probabilistic limit theorems asymptotically.

arXiv:1504.02536•IEEE Transactions on Information Theory•Dec 6, 2016•37 citations

On the Conditional Smooth Rényi Entropy and its Applications in Guessing and Source Coding

Shigeaki Kuzuoka

A novel definition of the conditional smooth Rényi entropy, which is different from that of Renner and Wolf, is introduced. It is shown that our definition of the conditional smooth Rényi entropy is appropriate for providing lower and upper bounds on the optimal guessing moment in a guessing problem where the guesser is allowed to stop guessing and declare an error. Further a general formula for the optimal guessing exponent is presented. In particular, a single-letterized formula for a mixture of i.i.d. sources is obtained. It is also shown that our definition is appropriate to characterize the optimal exponential moment of the codeword length in the problem of source coding with common side-information available at the encoder and decoder under a constraint on the probability of a decoding error.

arXiv:1810.09070•IEEE Transactions on Information Theory•Aug 27, 2019•17 citations

On the Randomness of Independent Experiments

Thomas Holenstein, Renato Renner

Smooth entropies characterize basic information-theoretic properties of random variables, such as the number of bits required to store them or the amount of uniform randomness that can be extracted from them (possibly with respect to side information). In this paper, explicit and almost tight bounds on the smooth entropies of n-fold product distributions, Pn, are derived. These bounds are expressed in terms of the Shannon entropy of a single distribution, P . The results can be seen as an extension of the asymptotic equipartition property (AEP).

arXiv:cs/0608007•IEEE Transactions on Information Theory•Mar 15, 2011•69 citations

Optimum Achievable Rates in Two Random Number Generation Problems with f-Divergences Using Smooth Rényi Entropy

Ryo Nomura, Hideki Yagi

Two typical fixed-length random number generation problems in information theory are considered for general sources. One is the source resolvability problem and the other is the intrinsic randomness problem. In each of these problems, the optimum achievable rate with respect to the given approximation measure is one of our main concerns and has been characterized using two different information quantities: the information spectrum and the smooth Rényi entropy. Recently, optimum achievable rates with respect to f-divergences have been characterized using the information spectrum quantity. The f-divergence is a general non-negative measure between two probability distributions on the basis of a convex function f. The class of f-divergences includes several important measures such as the variational distance, the KL divergence, the Hellinger distance and so on. Hence, it is meaningful to consider the random number generation problems with respect to f-divergences. However, optimum achievable rates with respect to f-divergences using the smooth Rényi entropy have not been clarified yet in both problems. In this paper, we try to analyze the optimum achievable rates using the smooth Rényi entropy and to extend the class of f-divergence. To do so, we first derive general formulas of the first-order optimum achievable rates with respect to f-divergences in both problems under the same conditions as imposed by previous studies. Next, we relax the conditions on f-divergence and generalize the obtained general formulas. Then, we particularize our general formulas to several specified functions f. As a result, we reveal that it is easy to derive optimum achievable rates for several important measures from our general formulas. Furthermore, a kind of duality between the resolvability and the intrinsic randomness is revealed in terms of the smooth Rényi entropy. Second-order optimum achievable rates and optimistic achievable rates are also investigated.

arXiv:2404.11097•Entropy•Sep 6, 2024•4 citations

Rényi Extrapolation of Shannon Entropy

Karol Życzkowski

Relations between Shannon entropy and Rényi entropies of integer order are discussed. For any N-point discrete probability distribution for which the Rényi entropies of order two and three are known, we provide a lower and an upper bound for the Shannon entropy. The average of both bounds provide an explicit extrapolation for this quantity. These results imply relations between the von Neumann entropy of a mixed quantum state, its linear entropy and traces.

arXiv:quant-ph/0305062•Open Systems & Information Dynamics•Sep 1, 2003•185 citations

Non-asymptotic analysis of privacy amplification via Rényi entropy and inf-spectral entropy

Shun Watanabe, Masahito Hayashi

This paper investigates the privacy amplification problem, and compares the existing two bounds: the exponential bound derived by one of the authors and the min-entropy bound derived by Renner. It turns out that the exponential bound is better than the min-entropy bound when a security parameter is rather small for a block length, and that the min-entropy bound is better than the exponential bound when a security parameter is rather large for a block length. Furthermore, we present another bound that interpolates the exponential bound and the min-entropy bound by a hybrid use of the Rényi entropy and the inf-spectral entropy.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•37 citations
The weak law of large numbers implies that, under mild assumptions on the source, the Renyi entropy per produced symbol converges (in probability) towards the Shannon entropy rate. This paper quantifies the speed of this convergence for sources with independent (but not iid) outputs, generalizing and improving the result of Holenstein and Renner (IEEE Trans. Inform. Theory, 2011). (a) we characterize sources with \emph{slowest convergence} (for given entropy): their outputs are mixtures of a uniform distribution and a unit mass. (b) based on the above characterization, we establish faster convergences in \emph{high-entropy} regimes. We discuss how these improved bounds may be used to better quantify security of outputs of random number generators. In turn, the characterization of "worst" distributions can be used to derive sharp "extremal" inequalities between Renyi and Shannon entropy. The main technique is \emph{non-convex programming}, used to characterize distributions of possibly large exponential moments under certain entropy.
We evaluate the asymptotics of equivocations, their exponents as well as their second-order coding rates under various Rényi information measures. Specifically, we consider the effect of applying a hash function on a source and we quantify the level of non-uniformity and dependence of the compressed source from another correlated source when the number of copies of the sources is large. Unlike previous works that use Shannon information measures to quantify randomness, information, or uniformity, we define our security measures in terms of a more general class of information measures-the Rényi information measures and their Gallager-type counterparts. A special case of these Rényi information measure is the class of Shannon information measures. We prove tight asymptotic results for the security measures and their exponential rates of decay. We also prove bounds on the second-order asymptotics and show that these bounds match when the magnitudes of the second-order coding rates are large. We do so by establishing new classes non-asymptotic bounds on the equivocation and evaluating these bounds using various probabilistic limit theorems asymptotically.
A novel definition of the conditional smooth Rényi entropy, which is different from that of Renner and Wolf, is introduced. It is shown that our definition of the conditional smooth Rényi entropy is appropriate for providing lower and upper bounds on the optimal guessing moment in a guessing problem where the guesser is allowed to stop guessing and declare an error. Further a general formula for the optimal guessing exponent is presented. In particular, a single-letterized formula for a mixture of i.i.d. sources is obtained. It is also shown that our definition is appropriate to characterize the optimal exponential moment of the codeword length in the problem of source coding with common side-information available at the encoder and decoder under a constraint on the probability of a decoding error.
Smooth entropies characterize basic information-theoretic properties of random variables, such as the number of bits required to store them or the amount of uniform randomness that can be extracted from them (possibly with respect to side information). In this paper, explicit and almost tight bounds on the smooth entropies of n-fold product distributions, Pn, are derived. These bounds are expressed in terms of the Shannon entropy of a single distribution, P . The results can be seen as an extension of the asymptotic equipartition property (AEP).
Two typical fixed-length random number generation problems in information theory are considered for general sources. One is the source resolvability problem and the other is the intrinsic randomness problem. In each of these problems, the optimum achievable rate with respect to the given approximation measure is one of our main concerns and has been characterized using two different information quantities: the information spectrum and the smooth Rényi entropy. Recently, optimum achievable rates with respect to f-divergences have been characterized using the information spectrum quantity. The f-divergence is a general non-negative measure between two probability distributions on the basis of a convex function f. The class of f-divergences includes several important measures such as the variational distance, the KL divergence, the Hellinger distance and so on. Hence, it is meaningful to consider the random number generation problems with respect to f-divergences. However, optimum achievable rates with respect to f-divergences using the smooth Rényi entropy have not been clarified yet in both problems. In this paper, we try to analyze the optimum achievable rates using the smooth Rényi entropy and to extend the class of f-divergence. To do so, we first derive general formulas of the first-order optimum achievable rates with respect to f-divergences in both problems under the same conditions as imposed by previous studies. Next, we relax the conditions on f-divergence and generalize the obtained general formulas. Then, we particularize our general formulas to several specified functions f. As a result, we reveal that it is easy to derive optimum achievable rates for several important measures from our general formulas. Furthermore, a kind of duality between the resolvability and the intrinsic randomness is revealed in terms of the smooth Rényi entropy. Second-order optimum achievable rates and optimistic achievable rates are also investigated.
This paper investigates the privacy amplification problem, and compares the existing two bounds: the exponential bound derived by one of the authors and the min-entropy bound derived by Renner. It turns out that the exponential bound is better than the min-entropy bound when a security parameter is rather small for a block length, and that the min-entropy bound is better than the exponential bound when a security parameter is rather large for a block length. Furthermore, we present another bound that interpolates the exponential bound and the min-entropy bound by a hybrid use of the Rényi entropy and the inf-spectral entropy.