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:2003.05545

Asymptotic Expansions of Smooth Rényi Entropies and Their Applications

Yuta Sakai, Vincent Y. F. Tan

Published Mar 11, 2020• 2 citations
arXivHTMLPDF

Abstract

This study considers the unconditional smooth Rényi entropy, the smooth conditional Rényi entropy proposed by Kuzuoka [\emph{IEEE Trans.\ Inf.\ Theory}, vol.~66, no.~3, pp.~1674--1690, 2020], and a new quantity which we term the conditional smooth Rényi entropy. In particular, we examine asymptotic expansions of these entropies when the underlying source with its side-information is stationary and memoryless. Using these smooth Rényi entropies, we establish one-shot coding theorems of several information-theoretic problems: Campbell's source coding, guessing problems, and task encoding problems, all allowing errors. In each problem, we consider two error formalisms: the average and maximum error criteria, where the averaging and maximization are taken with respect to the side-information of the source. Applying our asymptotic expansions to the derived one-shot coding theorems, we derive various asymptotic fundamental limits for these problems when their error probabilities are allowed to be non-vanishing. We show that, in non-degenerate settings, the first-order fundamental limits differ under the average and maximum error criteria. This is in contrast to a different but related setting considered by the present authors (for variable-length conditional source coding allowing errors) in which the first-order terms are identical but the second-order terms are different under these criteria.

DOI
10.48550/arxiv.2003.05545

Related papers

On Smooth Rényi Entropies: A Novel Information Measure, One-Shot Coding Theorems, and Asymptotic Expansions

Yuta Sakai, Vincent Y. F. Tan

This study considers the unconditional smooth Rényi entropy proposed by Renner and Wolf [ASIACRYPT, 2005], the smooth conditional Rényi entropy proposed by Kuzuoka [IEEE Trans. Inf. Th., 66(3), 1674–1690, 2020], and a novel quantity which we term theconditional smooth-⋆entropy.The latter two quantities can be specialized to the first in the absence of side-information. We explore the operational roles of these smooth Rényi entropies by establishing one-shot coding theorems for several information-theoretic problems, including Campbell’s source coding problem, the Arıkan–Massey guessing problem, and the Bunte–Lapidoth task encoding problem. We consider these problems in cases where the errors are non-vanishing and for each problem, we consider two error formalisms: the average and maximum error criteria, where the averaging and maximization are taken with respect to the side-information. Using the one-shot coding theorems, we conclude that Kuzuoka’s smooth conditional Rényi entropy and the conditional smooth-⋆ entropy are the solutions to the problems involving the average and maximum error criteria, respectively. Furthermore, we examine asymptotic expansions of these entropies when the underlying source with its side-information is stationary and memoryless. Applying our asymptotic expansions to the one-shot coding theorems, we derive various fundamental limits for these problems. We show that, under non-degenerate settings, the first-order fundamental limits differ under the average and maximum error criteria. This is in contrast to a different but related setting considered by the present authors [IEEE Trans. Inf. Th., 66(12), 7565–7587, 2020], for variable-length conditional source coding allowing errors, in which the first-order terms are identical but the second-order terms are different under these error criteria.

IEEE Transactions on Information Theory•Dec 3, 2021•6 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

Rethinking quantum smooth entropies: Tight one-shot analysis of quantum privacy amplification

Bartosz Regula, Marco Tomamichel

We introduce an improved one-shot characterisation of randomness extraction against quantum side information (privacy amplification), strengthening known one-shot bounds and providing a unified derivation of the tightest known asymptotic constraints. Our main tool is a new class of smooth conditional entropies defined by lifting classical smooth divergences through measurements. A key role is played by the measured smooth Rényi relative entropy of order 2, which we show to admit an equivalent variational form: it can be understood as allowing for smoothing over not only states, but also non-positive Hermitian operators. Building on this, we establish a tightened leftover hash lemma, significantly improving over all known smooth min-entropy bounds on extractable randomness and recovering the sharpest classical achievability results. We extend these methods to decoupling, the coherent analogue of privacy amplification, obtaining a corresponding improved one-shot bound. Relaxing our smooth entropy bounds leads to one-shot achievability results in terms of measured Rényi divergences, tightening the bounds of [Dupuis, arXiv:2105.05342] and recovering state-of-the-art asymptotic i.i.d. error exponents. We show an approximate optimality of our results by giving a matching one-shot converse bound up to additive logarithmic terms. This yields an optimal second-order asymptotic expansion of privacy amplification under trace distance, establishing a significantly tighter one-shot achievability result than previously shown in [Shen et al., arXiv:2202.11590] and proving its optimality for all hash functions.

quant-pharXiv:2603.04493•Mar 6, 2026•0 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•3 citations

Relative entropies and their use in quantum information theory

Felix Leditzky

This dissertation investigates relative entropies, also called generalized divergences, and how they can be used to characterize information-theoretic tasks in quantum information theory. The main goal is to further refine characterizations of the optimal rates for quantum source coding, state redistribution, and measurement compression with quantum side information via second order asymptotic expansions and strong converse theorems. The dissertation consists of a mathematical and an information-theoretic part. In the mathematical part, we focus on the $α$-sandwiched Rényi divergence ($α$-SRD). We first investigate the limit $α\to 0$ to determine whether this recovers the well-known $0$-Rényi relative divergence. We then prove various new results for entropic quantities derived from the $α$-SRD, including dimension bounds and useful bounds in terms of the fidelity between two quantum states. Furthermore, we derive a necessary and sufficient algebraic condition for equality in the data processing inequality (viz. monotonicity under quantum operations) for the $α$-SRD, and give applications to entropic bounds. In the information-theoretic part, we first derive the second order asymptotics of visible quantum source coding using a mixed source. For the achievability part, we develop universal quantum source codes achieving a given second order rate for a memoryless source. As a corollary of the main result, we obtain the second order asymptotics of quantum source coding using a single memoryless source. We then prove strong converse theorems for state redistribution (with or without feedback) and measurement compression with quantum side information. The key ingredients in proving these theorems are the aforementioned fidelity bounds on Rényi entropic quantities derived from the $α$-SRD.

arXiv:1611.08802•Nov 27, 2016•18 citations

One-shot bounds for various information theoretic problems using smooth min and max Rényi divergences

Naqueeb Ahmad Warsi

One-shot analogues for various information theory results known in the asymptotic case are proven using smooth min and max Rényi divergences. In particular, we prove that smooth min Rényi divergence can be used to prove one-shot analogue of the Stein's lemma. Using smooth min Rényi divergence we prove a special case of packing lemma in the one-shot setting. Furthermore, we prove a one-shot analogue of covering lemma using smooth max Rényi divergence. We also propose one-shot achievable rate for source coding under maximum distortion criterion. This achievable rate is quantified in terms of smooth max Rényi divergence.

IEEE Information Theory Workshop (ITW)•Sep 1, 2013•10 citations
This study considers the unconditional smooth Rényi entropy, the smooth conditional Rényi entropy proposed by Kuzuoka [\emph{IEEE Trans.\ Inf.\ Theory}, vol.~66, no.~3, pp.~1674--1690, 2020], and a new quantity which we term the conditional smooth Rényi entropy. In particular, we examine asymptotic expansions of these entropies when the underlying source with its side-information is stationary and memoryless. Using these smooth Rényi entropies, we establish one-shot coding theorems of several information-theoretic problems: Campbell's source coding, guessing problems, and task encoding problems, all allowing errors. In each problem, we consider two error formalisms: the average and maximum error criteria, where the averaging and maximization are taken with respect to the side-information of the source. Applying our asymptotic expansions to the derived one-shot coding theorems, we derive various asymptotic fundamental limits for these problems when their error probabilities are allowed to be non-vanishing. We show that, in non-degenerate settings, the first-order fundamental limits differ under the average and maximum error criteria. This is in contrast to a different but related setting considered by the present authors (for variable-length conditional source coding allowing errors) in which the first-order terms are identical but the second-order terms are different under these criteria.
This study considers the unconditional smooth Rényi entropy proposed by Renner and Wolf [ASIACRYPT, 2005], the smooth conditional Rényi entropy proposed by Kuzuoka [IEEE Trans. Inf. Th., 66(3), 1674–1690, 2020], and a novel quantity which we term theconditional smooth-⋆entropy.The latter two quantities can be specialized to the first in the absence of side-information. We explore the operational roles of these smooth Rényi entropies by establishing one-shot coding theorems for several information-theoretic problems, including Campbell’s source coding problem, the Arıkan–Massey guessing problem, and the Bunte–Lapidoth task encoding problem. We consider these problems in cases where the errors are non-vanishing and for each problem, we consider two error formalisms: the average and maximum error criteria, where the averaging and maximization are taken with respect to the side-information. Using the one-shot coding theorems, we conclude that Kuzuoka’s smooth conditional Rényi entropy and the conditional smooth-⋆ entropy are the solutions to the problems involving the average and maximum error criteria, respectively. Furthermore, we examine asymptotic expansions of these entropies when the underlying source with its side-information is stationary and memoryless. Applying our asymptotic expansions to the one-shot coding theorems, we derive various fundamental limits for these problems. We show that, under non-degenerate settings, the first-order fundamental limits differ under the average and maximum error criteria. This is in contrast to a different but related setting considered by the present authors [IEEE Trans. Inf. Th., 66(12), 7565–7587, 2020], for variable-length conditional source coding allowing errors, in which the first-order terms are identical but the second-order terms are different under these error criteria.
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.
We introduce an improved one-shot characterisation of randomness extraction against quantum side information (privacy amplification), strengthening known one-shot bounds and providing a unified derivation of the tightest known asymptotic constraints. Our main tool is a new class of smooth conditional entropies defined by lifting classical smooth divergences through measurements. A key role is played by the measured smooth Rényi relative entropy of order 2, which we show to admit an equivalent variational form: it can be understood as allowing for smoothing over not only states, but also non-positive Hermitian operators. Building on this, we establish a tightened leftover hash lemma, significantly improving over all known smooth min-entropy bounds on extractable randomness and recovering the sharpest classical achievability results. We extend these methods to decoupling, the coherent analogue of privacy amplification, obtaining a corresponding improved one-shot bound. Relaxing our smooth entropy bounds leads to one-shot achievability results in terms of measured Rényi divergences, tightening the bounds of [Dupuis, arXiv:2105.05342] and recovering state-of-the-art asymptotic i.i.d. error exponents. We show an approximate optimality of our results by giving a matching one-shot converse bound up to additive logarithmic terms. This yields an optimal second-order asymptotic expansion of privacy amplification under trace distance, establishing a significantly tighter one-shot achievability result than previously shown in [Shen et al., arXiv:2202.11590] and proving its optimality for all hash functions.
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 dissertation investigates relative entropies, also called generalized divergences, and how they can be used to characterize information-theoretic tasks in quantum information theory. The main goal is to further refine characterizations of the optimal rates for quantum source coding, state redistribution, and measurement compression with quantum side information via second order asymptotic expansions and strong converse theorems. The dissertation consists of a mathematical and an information-theoretic part. In the mathematical part, we focus on the ααα-sandwiched Rényi divergence (ααα-SRD). We first investigate the limit α→0α\to 0α→0 to determine whether this recovers the well-known 000-Rényi relative divergence. We then prove various new results for entropic quantities derived from the ααα-SRD, including dimension bounds and useful bounds in terms of the fidelity between two quantum states. Furthermore, we derive a necessary and sufficient algebraic condition for equality in the data processing inequality (viz. monotonicity under quantum operations) for the ααα-SRD, and give applications to entropic bounds. In the information-theoretic part, we first derive the second order asymptotics of visible quantum source coding using a mixed source. For the achievability part, we develop universal quantum source codes achieving a given second order rate for a memoryless source. As a corollary of the main result, we obtain the second order asymptotics of quantum source coding using a single memoryless source. We then prove strong converse theorems for state redistribution (with or without feedback) and measurement compression with quantum side information. The key ingredients in proving these theorems are the aforementioned fidelity bounds on Rényi entropic quantities derived from the ααα-SRD.
One-shot analogues for various information theory results known in the asymptotic case are proven using smooth min and max Rényi divergences. In particular, we prove that smooth min Rényi divergence can be used to prove one-shot analogue of the Stein's lemma. Using smooth min Rényi divergence we prove a special case of packing lemma in the one-shot setting. Furthermore, we prove a one-shot analogue of covering lemma using smooth max Rényi divergence. We also propose one-shot achievable rate for source coding under maximum distortion criterion. This achievable rate is quantified in terms of smooth max Rényi divergence.