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:1601.05875 · IEEE Transactions on Information Theory

Distributed Simulation of Continuous Random Variables

Cheuk Ting Li, Abbas El Gamal

Published Jul 1, 2016• 30 citations
arXivHTMLPDF

Abstract

We establish the first known upper bound on the exact and Wyner's common information of n continuous random variables in terms of the dual total correlation between them (which is a generalization of mutual information). In particular, we show that when the pdf of the random variables is log-concave, there is a constant gap of n2 loge + 9n log n between this upper bound and the dual total correlation lower bound that does not depend on the distribution. The upper bound is obtained using a computationally efficient dyadic decomposition scheme for constructing a discrete common randomness variable W from which the n random variables can be simulated in a distributed manner. We then bound the entropy of W using a new measure, which we refer to as the erosion entropy.

DOI
10.1109/tit.2017.2735438

Related papers

A Universal Coding Scheme for Remote Generation of Continuous Random Variables

Cheuk Ting Li, Abbas El Gamal

Alice selects an arbitrary pdf f and uses a stochastic encoder to generate a prefix-free codeword M, which is sent to Bob so that he can generate a single instance of the random variable X ~ f. We describe a universal coding scheme for this setup which works for any f , and establish an upper bound on its expected codeword length when the pdf f is bounded, orthogonally concave (which includes quasiconcave pdf), and has a finite first absolute moment. A dyadic decomposition scheme is used to express the pdf as a mixture of uniform pdfs over hypercubes. Alice randomly selects a hypercube according to its weight, encodes its position and size into M, and sends it to Bob who generates X uniformly over the hypercube. Compared to previous results on channel simulation, our coding scheme applies to any continuous distribution and does not require two-way communication or shared randomness. Applying our coding scheme to classical simulation of quantum entanglement, we obtain a tighter bound on the average codeword length than previously known.

arXiv:1603.05238•IEEE Transactions on Information Theory•Sep 1, 2016•8 citations

One-Shot Bounds on State Generation using Correlated Resources and Local Encoders

Ian M. George, Min-Hsiu Hsieh, Eric Chitambar

Distributed source simulation is the task where two (or more) parties share some correlated randomness and use local operations and no communication to convert this into some target correlation. Wyner’s seminal result showed that asymptotically the rate of uniform shared randomness needed for this task is given by a mutual information induced measure, now referred to as Wyner’s common information. In this work we characterize the quantum version of this task in the one-shot setting using the smooth entropy framework and one-shot operational quantities. We further establish asymptotic equipartition properties for our correlation measures. We also introduce entanglement versions of the distributed source simulation task and determine bounds in this setting via quantum embezzling.

IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2023•5 citations

One-Shot Distributed Source Simulation: As Quantum as It Can Get

Ian George, Min-Hsiu Hsieh, Eric Chitambar

Distributed source simulation is the task where two (or more) parties share some correlated randomness and use local operations and no communication to convert this into some target correlation. Wyner’s seminal result showed that asymptotically the rate of uniform shared randomness needed for this task is given by a mutual information induced measure, now referred to as Wyner’s common information. This asymptotic result was extended by Hayashi in the quantum setting to separable states, the largest class of states for which this task can be performed to vanishing error. In this work we characterize this task in a near-tight manner in the one-shot setting using the smooth entropy framework. We do this by introducing one-shot operational quantities and correlation measures that characterize them. We establish asymptotic equipartition properties for our correlation measures thereby recovering the previous vanishing-error asymptotic results. In doing so, we consider technical points in one-shot network information theory and provide methods for cardinality bounds in the smooth entropy calculus. We also introduce entangled state versions of the distributed source simulation task and determine bounds in this setting via quantum embezzling. This provides a strong characterization of this network task in the one-shot, quantum regime.

arXiv:2301.04301•IEEE Transactions on Information Theory•Oct 23, 2025•10 citations

Lower bounds for interactive function computation via Wyner common information

Shijin Rajakrishnan, Sundara Rajan S, Vinod M. Prabhakaran

The question of how much communication is required between collaborating parties to compute a function of their data is of fundamental importance in the fields of theoretical computer science and information theory. In this work, the focus is on coming up with lower bounds on this. The information cost of a protocol is the amount of information the protocol reveals to Alice and Bob about each others inputs, and the information complexity of a function is the infimum of information costs over all valid protocols. For the amortized case, it is known that the optimal rate for the computation is equal to the information complexity. Exactly computing this information complexity is not straight forward however. In this work we lower bound information complexity for independent inputs in terms of the Wyner common information of a certain pair of random variables. We show a structural property for the optimal auxiliary random variable of Wyner common information and exploit this to exactly compute the Wyner common information in certain cases. The lower bound obtained through this technique is shown to be tight for a non-trivial example - equality (EQ) for the ternary alphabet. We also give an example to show that the lower bound may, in general, not be tight.

arXiv:1602.02390•National Conference on Communications•Mar 1, 2016•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

Exact Channel Simulation under Exponential Cost

Spencer Hill, Fady Alajaji, Tamás Linder

In this work, we generalize results in exact channel simulation to an exponential communication cost, specifically to Campbell’s average codeword length L(t) of order t [1], and to Rényi’s entropy. In exact channel simulation, given a source of shared randomness, a sender wishes to communicate a message to the receiver so they can generate a sample from the conditional distribution PY |X. We lower bound the Campbell cost of channel simulation using any sampling algorithm, showing that it grows approximately as It+1(X; Y), where Iα is an appropriately defined α-mutual information of order α. Using the Poisson functional representation of Li and El Gamal [2], we prove an upper bound on L(t) whose leading α-mutual information term has order within ϵ of the lower bound. Our results reduce to the bounds of Harsha et al. [3] as t → 0. We also provide numerical examples for the additive white Gaussian noise channel, demonstrating that the upper and lower bounds are typically within 5-10 bits of each other.

•Sep 17, 2025•0 citations
We establish the first known upper bound on the exact and Wyner's common information of n continuous random variables in terms of the dual total correlation between them (which is a generalization of mutual information). In particular, we show that when the pdf of the random variables is log-concave, there is a constant gap of n2 loge + 9n log n between this upper bound and the dual total correlation lower bound that does not depend on the distribution. The upper bound is obtained using a computationally efficient dyadic decomposition scheme for constructing a discrete common randomness variable W from which the n random variables can be simulated in a distributed manner. We then bound the entropy of W using a new measure, which we refer to as the erosion entropy.
Alice selects an arbitrary pdf f and uses a stochastic encoder to generate a prefix-free codeword M, which is sent to Bob so that he can generate a single instance of the random variable X ~ f. We describe a universal coding scheme for this setup which works for any f , and establish an upper bound on its expected codeword length when the pdf f is bounded, orthogonally concave (which includes quasiconcave pdf), and has a finite first absolute moment. A dyadic decomposition scheme is used to express the pdf as a mixture of uniform pdfs over hypercubes. Alice randomly selects a hypercube according to its weight, encodes its position and size into M, and sends it to Bob who generates X uniformly over the hypercube. Compared to previous results on channel simulation, our coding scheme applies to any continuous distribution and does not require two-way communication or shared randomness. Applying our coding scheme to classical simulation of quantum entanglement, we obtain a tighter bound on the average codeword length than previously known.
Distributed source simulation is the task where two (or more) parties share some correlated randomness and use local operations and no communication to convert this into some target correlation. Wyner’s seminal result showed that asymptotically the rate of uniform shared randomness needed for this task is given by a mutual information induced measure, now referred to as Wyner’s common information. In this work we characterize the quantum version of this task in the one-shot setting using the smooth entropy framework and one-shot operational quantities. We further establish asymptotic equipartition properties for our correlation measures. We also introduce entanglement versions of the distributed source simulation task and determine bounds in this setting via quantum embezzling.
Distributed source simulation is the task where two (or more) parties share some correlated randomness and use local operations and no communication to convert this into some target correlation. Wyner’s seminal result showed that asymptotically the rate of uniform shared randomness needed for this task is given by a mutual information induced measure, now referred to as Wyner’s common information. This asymptotic result was extended by Hayashi in the quantum setting to separable states, the largest class of states for which this task can be performed to vanishing error. In this work we characterize this task in a near-tight manner in the one-shot setting using the smooth entropy framework. We do this by introducing one-shot operational quantities and correlation measures that characterize them. We establish asymptotic equipartition properties for our correlation measures thereby recovering the previous vanishing-error asymptotic results. In doing so, we consider technical points in one-shot network information theory and provide methods for cardinality bounds in the smooth entropy calculus. We also introduce entangled state versions of the distributed source simulation task and determine bounds in this setting via quantum embezzling. This provides a strong characterization of this network task in the one-shot, quantum regime.
The question of how much communication is required between collaborating parties to compute a function of their data is of fundamental importance in the fields of theoretical computer science and information theory. In this work, the focus is on coming up with lower bounds on this. The information cost of a protocol is the amount of information the protocol reveals to Alice and Bob about each others inputs, and the information complexity of a function is the infimum of information costs over all valid protocols. For the amortized case, it is known that the optimal rate for the computation is equal to the information complexity. Exactly computing this information complexity is not straight forward however. In this work we lower bound information complexity for independent inputs in terms of the Wyner common information of a certain pair of random variables. We show a structural property for the optimal auxiliary random variable of Wyner common information and exploit this to exactly compute the Wyner common information in certain cases. The lower bound obtained through this technique is shown to be tight for a non-trivial example - equality (EQ) for the ternary alphabet. We also give an example to show that the lower bound may, in general, not be tight.
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 this work, we generalize results in exact channel simulation to an exponential communication cost, specifically to Campbell’s average codeword length L(t) of order t [1], and to Rényi’s entropy. In exact channel simulation, given a source of shared randomness, a sender wishes to communicate a message to the receiver so they can generate a sample from the conditional distribution PY |X. We lower bound the Campbell cost of channel simulation using any sampling algorithm, showing that it grows approximately as It+1(X; Y), where Iα is an appropriately defined α-mutual information of order α. Using the Poisson functional representation of Li and El Gamal [2], we prove an upper bound on L(t) whose leading α-mutual information term has order within ϵ of the lower bound. Our results reduce to the bounds of Harsha et al. [3] as t → 0. We also provide numerical examples for the additive white Gaussian noise channel, demonstrating that the upper and lower bounds are typically within 5-10 bits of each other.