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

On Exact and ∞\infty∞-Rényi Common Informations

Lei Yu, Vincent Y. F. Tan

Published Sep 30, 2018• 2 citations
arXivHTMLPDF

Abstract

Recently, two extensions of Wyner's common information\textemdash exact and Rényi common informations\textemdash were introduced respectively by Kumar, Li, and El Gamal (KLE), and the present authors. The class of common information problems involves determining the minimum rate of the common input to two independent processors needed to exactly or approximately generate a target joint distribution. For the exact common information problem, exact generation of the target distribution is required, while for Wyner's and $α$-Rényi common informations, the relative entropy and Rényi divergence with order $α$ were respectively used to quantify the discrepancy between the synthesized and target distributions. The exact common information is larger than or equal to Wyner's common information. However, it was hitherto unknown whether the former is strictly larger than the latter for some joint distributions. In this paper, we first establish the equivalence between the exact and $\infty$-Rényi common informations, and then provide single-letter upper and lower bounds for these two quantities. For doubly symmetric binary sources, we show that the upper and lower bounds coincide, which implies that for such sources, the exact and $\infty$-Rényi common informations are completely characterized. Interestingly, we observe that for such sources, these two common informations are strictly larger than Wyner's. This answers an open problem posed by KLE. Furthermore, we extend Wyner's, $\infty$-Rényi, and exact common informations to sources with countably infinite or continuous alphabets, including Gaussian sources.

DOI
10.48550/arxiv.1810.00295

Related papers

On Exact and ∞-Rényi Common Informations

Lei Yu, Vincent Y. F. Tan

Recently, two extensions of Wyner's common information-exact and Rényi common informations-were introduced respectively by Kumar, Li, and El Gamal (KLE), and the present authors. The class of common information problems involves determining the minimum rate of the common input to two independent processors needed to exactly or approximately generate a target joint distribution. For the exact common information problem, exact generation of the target distribution is required, while for Wyner's and α-Rényi common informations, the relative entropy and Rényi divergence with order α were respectively used to quantify the discrepancy between the synthesized and target distributions. The exact common information is larger than or equal to Wyner's common information. However, it was hitherto unknown whether the former is strictly larger than the latter for some joint distributions. In this paper, we first establish the equivalence between the exact and ∞-Rényi common informations, and then provide single-letter upper and lower bounds for these two quantities. For doubly symmetric binary sources, we show that the upper and lower bounds coincide, which implies that for such sources, the exact and ∞-Rényi common informations are completely characterized. Interestingly, we observe that for such sources, these two common informations are strictly larger than Wyner's. This answers an open problem posed by KLE. Furthermore, we extend Wyner's, ∞-Rényi, and exact common informations to sources with countably infinite or continuous alphabets, including Gaussian sources.

IEEE Transactions on Information Theory•Jan 29, 2020•23 citations

On Exact and ∞-Rényi Common Informations

Lei Yu, Vincent Y. F. Tan

Recently, two extensions of Wyner's common information-exact and Rényi common informations-were introduced respectively by Kumar, Li, and El Gamal (KLE), and the present authors. The class of common information problems refers to determining the minimum rate of the common input to two independent processors needed to generate an exact or approximate joint distribution. For the exact common information problem, an exact generation of the target distribution is required, while for Wyner's and α-Rényi common informations, the relative entropy and Rényi divergence with order α were respectively used to quantify the discrepancy between the synthesized and target distributions. The exact common information is larger than or equal to Wyner's common information. However, it was hitherto unknown whether the former is strictly larger than the latter. In this paper, we first establish the equivalence between the exact and ∞-Rényi common informations, and then provide single-letter upper and lower bounds for these two quantities. For doubly symmetric binary sources, we show that the upper and lower bounds coincide, which implies that for such sources, the exact and ∞-Rényi common informations are completely characterized. Interestingly, we observe that for such sources, these two common informations are strictly larger than Wyner's. This answers an open problem posed by KLE.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•2 citations

Wyner's Common Information under Rényi Divergence Measures

Lei Yu, Vincent Y. F. Tan

We study a generalized version of Wyner's common information problem (also coined the distributed source simulation problem). The original common information problem consists in understanding the minimum rate of the common input to independent processors to generate an approximation of a joint distribution when the distance measure used to quantify the discrepancy between the synthesized and target distributions is the normalized relative entropy. Our generalization involves changing the distance measure to the unnormalized and normalized Rényi divergences of order $α=1+s\in[0,2]$. We show that the minimum rate needed to ensure the Rényi divergences between the distribution induced by a code and the target distribution vanishes remains the same as the one in Wyner's setting, except when the order $α=1+s=0$. This implies that Wyner's common information is rather robust to the choice of distance measure employed. As a byproduct of the proofs used to the establish the above results, the exponential strong converse for the common information problem under the total variation distance measure is established.

arXiv:1709.02168•Sep 7, 2017•0 citations

Exact common information

Gowtham Ramani Kumar, Cheuk Ting Li, Abbas El Gamal

This paper introduces the notion of exact common information, which is the minimum description length of the common randomness needed for the exact distributed generation of two correlated random variables (X, Y). We introduce the quantity G(X; Y) = minX→W→YH(W) as a natural bound on the exact common information and study its properties and computation. We then introduce the exact common information rate, which is the minimum description rate of the common randomness for the exact generation of a 2-DMS (X, Y). We give a multiletter characterization for it as the limit Ḡ(X; Y) = limn→∞(1/n)G(Xn; Yn). While in general Ḡ(X; Y) is greater than or equal to the Wyner common information, we show that they are equal for the Symmetric Binary Erasure Source. We do not know, however, if the exact common information rate has a single letter characterization in general.

arXiv:1402.0062•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•64 citations

Generalized Common Informations: Measuring Commonness by the Conditional Maximal Correlation

Lei Yu, Houqiang Li, Chang Wen Chen

In literature, different common informations were defined by Gács and Körner, by Wyner, and by Kumar, Li, and Gamal, respectively. In this paper, we define two generalized versions of common informations, named approximate and exact information-correlation functions, by exploiting the conditional maximal correlation as a commonness or privacy measure. These two generalized common informations encompass the notions of Gács-Körner's, Wyner's, and Kumar-Li-Gamal's common informations as special cases. Furthermore, to give operational characterizations of these two generalized common informations, we also study the problems of private sources synthesis and common information extraction, and show that the information-correlation functions are equal to the minimum rates of commonness needed to ensure that some conditional maximal correlation constraints are satisfied for the centralized setting versions of these problems. As a byproduct, the conditional maximal correlation has been studied as well.

arXiv:1610.09289•Oct 28, 2016•14 citations

Rényi Resolvability and Its Applications to the Wiretap Channel

Lei Yu, Vincent Y. F. Tan

The conventional channel resolvability problem refers to the determination of the minimum rate required for an input process so that the output distribution approximates a target distribution in either the total variation distance or the relative entropy. In contrast to previous works, in this paper, we use the (normalized or unnormalized) Rényi divergence (with the Rényi parameter in $[0,2]\cup\{\infty\}$) to measure the level of approximation. We also provide asymptotic expressions for normalized Rényi divergence when the Rényi parameter is larger than or equal to $1$ as well as (lower and upper) bounds for the case when the same parameter is smaller than $1$. We characterize the Rényi resolvability, which is defined as the minimum rate required to ensure that the Rényi divergence vanishes asymptotically. The Rényi resolvabilities are the same for both the normalized and unnormalized divergence cases. In addition, when the Rényi parameter smaller than~$1$, consistent with the traditional case where the Rényi parameter is equal to~$1$, the Rényi resolvability equals the minimum mutual information over all input distributions that induce the target output distribution. When the Rényi parameter is larger than $1$ the Rényi resolvability is, in general, larger than the mutual information. The optimal Rényi divergence is proven to vanish at least exponentially fast for both of these two cases, as long as the code rate is larger than the Rényi resolvability. The optimal exponential rate of decay for i.i.d.\ random codes is also characterized exactly. We apply these results to the wiretap channel, and completely characterize the optimal tradeoff between the rates of the secret and non-secret messages when the leakage measure is given by the (unnormalized) Rényi divergence.

arXiv:1707.00810•Jul 4, 2017•0 citations
Recently, two extensions of Wyner's common information\textemdash exact and Rényi common informations\textemdash were introduced respectively by Kumar, Li, and El Gamal (KLE), and the present authors. The class of common information problems involves determining the minimum rate of the common input to two independent processors needed to exactly or approximately generate a target joint distribution. For the exact common information problem, exact generation of the target distribution is required, while for Wyner's and ααα-Rényi common informations, the relative entropy and Rényi divergence with order ααα were respectively used to quantify the discrepancy between the synthesized and target distributions. The exact common information is larger than or equal to Wyner's common information. However, it was hitherto unknown whether the former is strictly larger than the latter for some joint distributions. In this paper, we first establish the equivalence between the exact and ∞\infty∞-Rényi common informations, and then provide single-letter upper and lower bounds for these two quantities. For doubly symmetric binary sources, we show that the upper and lower bounds coincide, which implies that for such sources, the exact and ∞\infty∞-Rényi common informations are completely characterized. Interestingly, we observe that for such sources, these two common informations are strictly larger than Wyner's. This answers an open problem posed by KLE. Furthermore, we extend Wyner's, ∞\infty∞-Rényi, and exact common informations to sources with countably infinite or continuous alphabets, including Gaussian sources.
Recently, two extensions of Wyner's common information-exact and Rényi common informations-were introduced respectively by Kumar, Li, and El Gamal (KLE), and the present authors. The class of common information problems involves determining the minimum rate of the common input to two independent processors needed to exactly or approximately generate a target joint distribution. For the exact common information problem, exact generation of the target distribution is required, while for Wyner's and α-Rényi common informations, the relative entropy and Rényi divergence with order α were respectively used to quantify the discrepancy between the synthesized and target distributions. The exact common information is larger than or equal to Wyner's common information. However, it was hitherto unknown whether the former is strictly larger than the latter for some joint distributions. In this paper, we first establish the equivalence between the exact and ∞-Rényi common informations, and then provide single-letter upper and lower bounds for these two quantities. For doubly symmetric binary sources, we show that the upper and lower bounds coincide, which implies that for such sources, the exact and ∞-Rényi common informations are completely characterized. Interestingly, we observe that for such sources, these two common informations are strictly larger than Wyner's. This answers an open problem posed by KLE. Furthermore, we extend Wyner's, ∞-Rényi, and exact common informations to sources with countably infinite or continuous alphabets, including Gaussian sources.
Recently, two extensions of Wyner's common information-exact and Rényi common informations-were introduced respectively by Kumar, Li, and El Gamal (KLE), and the present authors. The class of common information problems refers to determining the minimum rate of the common input to two independent processors needed to generate an exact or approximate joint distribution. For the exact common information problem, an exact generation of the target distribution is required, while for Wyner's and α-Rényi common informations, the relative entropy and Rényi divergence with order α were respectively used to quantify the discrepancy between the synthesized and target distributions. The exact common information is larger than or equal to Wyner's common information. However, it was hitherto unknown whether the former is strictly larger than the latter. In this paper, we first establish the equivalence between the exact and ∞-Rényi common informations, and then provide single-letter upper and lower bounds for these two quantities. For doubly symmetric binary sources, we show that the upper and lower bounds coincide, which implies that for such sources, the exact and ∞-Rényi common informations are completely characterized. Interestingly, we observe that for such sources, these two common informations are strictly larger than Wyner's. This answers an open problem posed by KLE.
We study a generalized version of Wyner's common information problem (also coined the distributed source simulation problem). The original common information problem consists in understanding the minimum rate of the common input to independent processors to generate an approximation of a joint distribution when the distance measure used to quantify the discrepancy between the synthesized and target distributions is the normalized relative entropy. Our generalization involves changing the distance measure to the unnormalized and normalized Rényi divergences of order α=1+s∈[0,2]α=1+s\in[0,2]α=1+s∈[0,2]. We show that the minimum rate needed to ensure the Rényi divergences between the distribution induced by a code and the target distribution vanishes remains the same as the one in Wyner's setting, except when the order α=1+s=0α=1+s=0α=1+s=0. This implies that Wyner's common information is rather robust to the choice of distance measure employed. As a byproduct of the proofs used to the establish the above results, the exponential strong converse for the common information problem under the total variation distance measure is established.
This paper introduces the notion of exact common information, which is the minimum description length of the common randomness needed for the exact distributed generation of two correlated random variables (X, Y). We introduce the quantity G(X; Y) = minX→W→YH(W) as a natural bound on the exact common information and study its properties and computation. We then introduce the exact common information rate, which is the minimum description rate of the common randomness for the exact generation of a 2-DMS (X, Y). We give a multiletter characterization for it as the limit Ḡ(X; Y) = limn→∞(1/n)G(Xn; Yn). While in general Ḡ(X; Y) is greater than or equal to the Wyner common information, we show that they are equal for the Symmetric Binary Erasure Source. We do not know, however, if the exact common information rate has a single letter characterization in general.
In literature, different common informations were defined by Gács and Körner, by Wyner, and by Kumar, Li, and Gamal, respectively. In this paper, we define two generalized versions of common informations, named approximate and exact information-correlation functions, by exploiting the conditional maximal correlation as a commonness or privacy measure. These two generalized common informations encompass the notions of Gács-Körner's, Wyner's, and Kumar-Li-Gamal's common informations as special cases. Furthermore, to give operational characterizations of these two generalized common informations, we also study the problems of private sources synthesis and common information extraction, and show that the information-correlation functions are equal to the minimum rates of commonness needed to ensure that some conditional maximal correlation constraints are satisfied for the centralized setting versions of these problems. As a byproduct, the conditional maximal correlation has been studied as well.
The conventional channel resolvability problem refers to the determination of the minimum rate required for an input process so that the output distribution approximates a target distribution in either the total variation distance or the relative entropy. In contrast to previous works, in this paper, we use the (normalized or unnormalized) Rényi divergence (with the Rényi parameter in [0,2]∪{∞}[0,2]\cup\{\infty\}[0,2]∪{∞}) to measure the level of approximation. We also provide asymptotic expressions for normalized Rényi divergence when the Rényi parameter is larger than or equal to 111 as well as (lower and upper) bounds for the case when the same parameter is smaller than 111. We characterize the Rényi resolvability, which is defined as the minimum rate required to ensure that the Rényi divergence vanishes asymptotically. The Rényi resolvabilities are the same for both the normalized and unnormalized divergence cases. In addition, when the Rényi parameter smaller than~111, consistent with the traditional case where the Rényi parameter is equal to~111, the Rényi resolvability equals the minimum mutual information over all input distributions that induce the target output distribution. When the Rényi parameter is larger than 111 the Rényi resolvability is, in general, larger than the mutual information. The optimal Rényi divergence is proven to vanish at least exponentially fast for both of these two cases, as long as the code rate is larger than the Rényi resolvability. The optimal exponential rate of decay for i.i.d.\ random codes is also characterized exactly. We apply these results to the wiretap channel, and completely characterize the optimal tradeoff between the rates of the secret and non-secret messages when the leakage measure is given by the (unnormalized) Rényi divergence.