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:2305.05524 · IEEE International Symposium on Information Theory (ISIT)

A Lower and Upper Bound on the Epsilon-Uniform Common Randomness Capacity

Rami Ezzine, Moritz Wiese, Christian Deppe, Holger Boche

Published Jun 25, 2023• 5 citations
arXivHTMLPDF

Abstract

We consider a standard two-source model for uniform common randomness (UCR) generation, in which Alice and Bob observe independent and identically distributed (i. i. d.) samples of a correlated finite source and where Alice is allowed to send information to Bob over an arbitrary single-user channel. We study the ϵ-UCR capacity for the proposed model, defined as the maximum common randomness rate one can achieve such that the probability that Alice and Bob do not agree on a common uniform or nearly uniform random variable does not exceed ϵ. We establish a lower and an upper bound on the ϵ-UCR capacity using the bounds on the ϵ-transmission capacity proved by Verdú and Han for arbitrary point-to-point channels.A detailed version with all proofs, explanations and more discussions can be found in [1].

DOI
10.1109/isit54713.2023.10206640

Related papers

Common Randomness Generation from Sources with Countable Alphabet

Wafa Labidi, Rami Ezzine, Christian Deppe +2 more

We study a two-source model for common randomness (CR) generation in which the sender Alice and the receiver Bob generate a common random variable with a high probability of agreement by observing independent and identically distributed (i.i.d.) samples of correlated sources on countably infinite alphabets. The two parties are additionally allowed to communicate over a noisy memoryless channel. In our work, we establish a single-letter lower and upper-bound on the CR capacity for the proposed model. This is a challenging scenario because some of the finite alphabet properties, namely of the entropy can not be extended to the countably infinite case. We use a generalized typicality criterion, called unified typicality, which can be applied to random variables on countably infinite alphabets.

arXiv:2210.04556•International Conference on Communications•May 28, 2023•2 citations

Common Randomness Generation from Sources with Infinite Polish Alphabet

Wafa Labidi, Rami Ezzine, Moritz Wiese +2 more

We investigate the problem of common randomness (CR) generation in the basic two-party communication setting in which a sender and a receiver aim to agree on a common random variable with high probability. The terminals observe independent and identically distributed (i.i.d.) samples of sources with an arbitrary distribution defined on a Polish alphabet and are allowed to communicate as little as possible over a noisy, memoryless channel. We establish single-letter upper and lower bounds on the CR capacity for the specified model. The derived bounds hold with equality except for at most countably many points where discontinuity issues might arise.

arXiv:2405.01948•May 3, 2024•0 citations

Common Randomness Generation from Finite Compound Sources

Rami Ezzine, Moritz Wiese, Christian Deppe +1 more

We investigate the problem of generating common randomness (CR) from finite compound sources aided by unidirectional communication over rate-limited perfect channels. The two communicating parties, often referred to as terminals, observe independent and identically distributed (i.i.d.) samples of a finite compound source and aim to agree on a common random variable with a high probability for every possible realization of the source state. Both parties know the set of source states as well as their statistics. However, they are unaware of the actual realization of the source state. We establish a single-letter lower and upper bound on the compound CR capacity for the specified model. Furthermore, we present two special scenarios where the established bounds coincide.

arXiv:2401.14323•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•5 citations

Common Randomness Generation from Sources with Infinite Polish Alphabets

Wafa Labidi, Rami Ezzine, Moritz Wiese +2 more

We study the problem of common randomness (CR) generation in a fundamental two-party communication scenario, where a sender and a receiver seek to agree-with high probability-on a shared random variable. Both parties observe independent and identically distributed (i.i.d.) samples from sources defined over a Polish alphabet with an arbitrary joint distribution. Communication is restricted to a unidirectional, minimally interactive exchange over a noisy, memoryless channel. For this setting, we establish single-letter lower and upper bounds on the CR capacity. These bounds coincide except possibly at a countable set of points where discontinuities may arise.

IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•0 citations

Common Randomness Generation from Gaussian Sources

Wafa Labidi, Rami Ezzine, Christian Deppe +1 more

We study the problem of common randomness (CR) generation in the basic two-party communication setting in which the sender and the receiver aim to agree on a common random variable with high probability by observing independent and identically distributed (i.i.d.) samples of correlated Gaussian sources and while communicating as little as possible over a noisy memoryless channel. We completely solve the problem by giving a single-letter characterization of the CR capacity for the proposed model and by providing rigorous proof of it We prove that the CR capacity is infinite when the Gaussian sources are perfectly correlated.

arXiv:2201.11078•IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•9 citations

The common randomness capacity of a pair of independent discrete memoryless channels

Sivarama Venkatesan, Venkat Anantharam

We study the following problem: two agents Alice and Bob are connected to each other by independent discrete memoryless channels. They wish to generate common randomness, i.e. agree on a common random variable, by communicating interactively over the two channels. Assuming that Alice and Bob are allowed access to independent external random sources at rates (in bits per step of communication) of H/sub A/ and H/sub B/, respectively, we show that they can generate common randomness at a rate of max{min[H/sub A/+H(W|Q),I(P;V)]+min[H/sub B/+H(V|P), I(Q;W)]} bits per step, by exploiting the noise on the two channels. Here, V is the channel from Alice to Bob, and W is the channel from Bob to Alice. The maximum is over all probability distributions P and Q on the input alphabets of V and W, respectively. We also prove a strong converse which establishes the above rate as the highest attainable in this situation.

IEEE Transactions on Information Theory•Jan 1, 1998•34 citations
We consider a standard two-source model for uniform common randomness (UCR) generation, in which Alice and Bob observe independent and identically distributed (i. i. d.) samples of a correlated finite source and where Alice is allowed to send information to Bob over an arbitrary single-user channel. We study the ϵ-UCR capacity for the proposed model, defined as the maximum common randomness rate one can achieve such that the probability that Alice and Bob do not agree on a common uniform or nearly uniform random variable does not exceed ϵ. We establish a lower and an upper bound on the ϵ-UCR capacity using the bounds on the ϵ-transmission capacity proved by Verdú and Han for arbitrary point-to-point channels.A detailed version with all proofs, explanations and more discussions can be found in [1].
We study a two-source model for common randomness (CR) generation in which the sender Alice and the receiver Bob generate a common random variable with a high probability of agreement by observing independent and identically distributed (i.i.d.) samples of correlated sources on countably infinite alphabets. The two parties are additionally allowed to communicate over a noisy memoryless channel. In our work, we establish a single-letter lower and upper-bound on the CR capacity for the proposed model. This is a challenging scenario because some of the finite alphabet properties, namely of the entropy can not be extended to the countably infinite case. We use a generalized typicality criterion, called unified typicality, which can be applied to random variables on countably infinite alphabets.
We investigate the problem of common randomness (CR) generation in the basic two-party communication setting in which a sender and a receiver aim to agree on a common random variable with high probability. The terminals observe independent and identically distributed (i.i.d.) samples of sources with an arbitrary distribution defined on a Polish alphabet and are allowed to communicate as little as possible over a noisy, memoryless channel. We establish single-letter upper and lower bounds on the CR capacity for the specified model. The derived bounds hold with equality except for at most countably many points where discontinuity issues might arise.
We investigate the problem of generating common randomness (CR) from finite compound sources aided by unidirectional communication over rate-limited perfect channels. The two communicating parties, often referred to as terminals, observe independent and identically distributed (i.i.d.) samples of a finite compound source and aim to agree on a common random variable with a high probability for every possible realization of the source state. Both parties know the set of source states as well as their statistics. However, they are unaware of the actual realization of the source state. We establish a single-letter lower and upper bound on the compound CR capacity for the specified model. Furthermore, we present two special scenarios where the established bounds coincide.
We study the problem of common randomness (CR) generation in a fundamental two-party communication scenario, where a sender and a receiver seek to agree-with high probability-on a shared random variable. Both parties observe independent and identically distributed (i.i.d.) samples from sources defined over a Polish alphabet with an arbitrary joint distribution. Communication is restricted to a unidirectional, minimally interactive exchange over a noisy, memoryless channel. For this setting, we establish single-letter lower and upper bounds on the CR capacity. These bounds coincide except possibly at a countable set of points where discontinuities may arise.
We study the problem of common randomness (CR) generation in the basic two-party communication setting in which the sender and the receiver aim to agree on a common random variable with high probability by observing independent and identically distributed (i.i.d.) samples of correlated Gaussian sources and while communicating as little as possible over a noisy memoryless channel. We completely solve the problem by giving a single-letter characterization of the CR capacity for the proposed model and by providing rigorous proof of it We prove that the CR capacity is infinite when the Gaussian sources are perfectly correlated.
We study the following problem: two agents Alice and Bob are connected to each other by independent discrete memoryless channels. They wish to generate common randomness, i.e. agree on a common random variable, by communicating interactively over the two channels. Assuming that Alice and Bob are allowed access to independent external random sources at rates (in bits per step of communication) of H/sub A/ and H/sub B/, respectively, we show that they can generate common randomness at a rate of max{min[H/sub A/+H(W|Q),I(P;V)]+min[H/sub B/+H(V|P), I(Q;W)]} bits per step, by exploiting the noise on the two channels. Here, V is the channel from Alice to Bob, and W is the channel from Bob to Alice. The maximum is over all probability distributions P and Q on the input alphabets of V and W, respectively. We also prove a strong converse which establishes the above rate as the highest attainable in this situation.