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

IEEE Transactions on Information Theory

The common randomness capacity of a network of discrete memoryless channels

Sivarama Venkatesan, Venkat Anantharam

Published Mar 1, 2000• 22 citations
Publisher

Abstract

We generalize our previous results on generating common randomness at two terminals to a situation where any finite number of agents, interconnected by an arbitrary network of independent, point-to-point, discrete memoryless channels, wish to generate common randomness by interactive communication over the network. Our main result is an exact characterization of the common randomness capacity of such a network, i.e., the maximum number of bits of randomness that all the agents can agree on per step of communication. As a by-product, we also obtain a purely combinatorial result, viz., a characterization of (the incidence vectors of) the spanning arborescences rooted at a specified vertex in a digraph, and having exactly one edge exiting the root, as precisely the extreme points of a certain unbounded convex polyhedron, described by a system of linear inequalities.

DOI
10.1109/18.825797

Related papers

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•35 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 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•8 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•1 citation

How Many Queries Will Resolve Common Randomness?

Himanshu Tyagi, Prakash Narayan

A set of m terminals, observing correlated signals, communicate interactively to generate common randomness for a given subset of them. Knowing only the communication, how many direct queries of the value of the common randomness will resolve it? A general upper bound, valid for arbitrary signal alphabets, is developed for the number of such queries by using a query strategy that applies to all common randomness and associated communication. When the underlying signals are independent and identically distributed repetitions of m correlated random variables, the number of queries can be exponential in signal length. For this case, the mentioned upper bound is tight and leads to a single-letter formula for the largest query exponent, which coincides with the secret key capacity of a corresponding multiterminal source model. In fact, the upper bound constitutes a strong converse for the optimum query exponent, and implies also a new strong converse for secret key capacity. A key tool, estimating the size of a large probability set in terms of Renyi entropy, is interpreted separately, too, as a lossless block coding result for general sources. As a particularization, it yields the classic result for a discrete memoryless source.

arXiv:1305.1397•May 7, 2013•1 citation

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•3 citations
We generalize our previous results on generating common randomness at two terminals to a situation where any finite number of agents, interconnected by an arbitrary network of independent, point-to-point, discrete memoryless channels, wish to generate common randomness by interactive communication over the network. Our main result is an exact characterization of the common randomness capacity of such a network, i.e., the maximum number of bits of randomness that all the agents can agree on per step of communication. As a by-product, we also obtain a purely combinatorial result, viz., a characterization of (the incidence vectors of) the spanning arborescences rooted at a specified vertex in a digraph, and having exactly one edge exiting the root, as precisely the extreme points of a certain unbounded convex polyhedron, described by a system of linear inequalities.
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.
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 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 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.
A set of m terminals, observing correlated signals, communicate interactively to generate common randomness for a given subset of them. Knowing only the communication, how many direct queries of the value of the common randomness will resolve it? A general upper bound, valid for arbitrary signal alphabets, is developed for the number of such queries by using a query strategy that applies to all common randomness and associated communication. When the underlying signals are independent and identically distributed repetitions of m correlated random variables, the number of queries can be exponential in signal length. For this case, the mentioned upper bound is tight and leads to a single-letter formula for the largest query exponent, which coincides with the secret key capacity of a corresponding multiterminal source model. In fact, the upper bound constitutes a strong converse for the optimum query exponent, and implies also a new strong converse for secret key capacity. A key tool, estimating the size of a large probability set in terms of Renyi entropy, is interpreted separately, too, as a lossless block coding result for general sources. As a particularization, it yields the classic result for a discrete memoryless source.
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.