On the Common Randomness Capacity of a Special Class of Two-way Channels

Saeed Hajizadeh

arxiv: 1906.11231 · v1 · pith:FE7NOX4Rnew · submitted 2019-06-26 · 💻 cs.IT · math.IT

On the Common Randomness Capacity of a Special Class of Two-way Channels

Saeed Hajizadeh This is my paper

Pith reviewed 2026-05-25 15:00 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords common randomnesstwo-way channelscapacity boundsreceiver-decomposable channelsintertwined channelsouter bound

0 comments

The pith

An outer bound on common randomness capacity for intertwined receiver-decomposable two-way channels is tight when the channel decomposes into one-way channels.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies common randomness generation over intertwined two-way channels where each marginal transition probability depends on the signal transmitted by the receiving node. It gives explicit schemes that let the two nodes agree on common randomness in certain special cases. For the receiver-decomposable subclass an outer bound is obtained together with a finite cardinality constraint on the auxiliary variables. The paper shows that this outer bound never exceeds the common randomness capacity of the one-way decomposition of the same channel, so the bound is tight precisely when the two-way channel decomposes.

Core claim

For intertwined receiver-decomposable two-way channels the common randomness capacity is at most a mutual-information expression involving auxiliary random variables whose alphabet sizes are bounded; this expression is itself at most the common randomness capacity of the corresponding one-way decomposition, establishing tightness in the decomposing case.

What carries the argument

The outer bound on common randomness capacity for the receiver-decomposable class of two-way channels, obtained via auxiliary random variables subject to cardinality limits.

If this is right

The common randomness capacity equals the one-way capacity whenever the two-way channel decomposes.
Explicit schemes achieve positive common randomness rates in the special intertwined settings examined.
The cardinality bound reduces the outer-bound expression to a finite-dimensional optimization.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same decomposition argument may apply to other coordination tasks over two-way links.
The receiver-decomposable structure could be used to obtain capacity results for related multi-terminal problems.

Load-bearing premise

The two-way channel belongs to the intertwined receiver-decomposable class in which each marginal channel depends on the signal transmitted by its own receiver.

What would settle it

A concrete intertwined receiver-decomposable two-way channel whose achievable common randomness rate exceeds the stated outer bound would falsify the claim.

Figures

Figures reproduced from arXiv: 1906.11231 by Saeed Hajizadeh.

**Figure 2.** Figure 2: RD two-way channel We desire to find the maximum amount of common randomness the two terminals can agree upon after a block of n uses of the channel. In other words, let the terminals communicate through the channel in n blocks and after gathering the corresponding outputs, each of them can compute a common random output. This random output will take its values from a set, say K. The supremum of the cardin… view at source ↗

read the original abstract

In this paper, we would like to study the common randomness (CR) capacity of intertwined two-way channels, namely those whose marginal channel transition probabilities depends also on the signal they transmit. We bring a few special settings and provide constructive schemes with which the two nodes can agree upon a common randomness. We then provide an outer bound on the CR capacity of intertwined receiver-decomposable (RD) two-way channel and will provide a bound on the cardinality of the available auxiliary variables. We will also show this outer bound is bounded above by Venkatesan-Anantharam CR capacity which makes it tight for decomposing two-way setting.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper adds constructive schemes and a cardinality-bounded outer bound for common randomness on intertwined receiver-decomposable two-way channels, with tightness shown against the Venkatesan-Anantharam result in the decomposing case.

read the letter

The main contribution is a set of explicit schemes that let the two nodes generate shared randomness on a few intertwined two-way channels, plus an outer bound specialized to the receiver-decomposable subclass that includes a cardinality limit on the auxiliaries. The paper then shows the new outer bound sits below the Venkatesan-Anantharam capacity, which gives equality for the decomposing subcase. That comparison is the cleanest part of the work and turns the outer bound into a capacity result for that subcase. The constructions follow the usual random coding style for common randomness but are adapted to the dependence of each marginal on the local transmit symbol, which is the defining feature of the intertwined model. The outer bound derivation appears to reuse standard mutual-information techniques from the two-way channel literature but tailors the auxiliary structure to the receiver-decomposable property. No obvious internal contradictions appear in the high-level claims. The main limitation is that the abstract supplies neither the explicit transition matrices nor the error-probability calculations, so the tightness argument cannot be verified without the full proofs. The model restriction to intertwined RD channels is stated up front, so it is not an unaccounted loophole. This is a narrow but technically coherent extension of existing two-way CR results. It will mainly interest specialists already working on two-way channel capacities or common randomness extraction. The combination of inner bounds, outer bound, and matching result in a special case is enough to justify sending it to referees rather than desk-rejecting it.

Referee Report

2 major / 0 minor

Summary. The paper studies the common randomness (CR) capacity of intertwined two-way channels whose marginal transition probabilities depend on the transmitted signals. It presents constructive schemes for CR generation in a few special settings, derives an outer bound on the CR capacity of the intertwined receiver-decomposable (RD) subclass together with a cardinality bound on the auxiliary variables, and shows that this outer bound is at most the Venkatesan-Anantharam CR capacity, which establishes tightness for the decomposing case.

Significance. If the derivations and comparisons hold, the work supplies both achievable schemes and a matching outer bound for a non-standard class of two-way channels, together with an explicit connection to an existing capacity result that yields tightness in a special case. This constitutes a standard but useful incremental contribution to the information-theoretic study of common randomness over interactive channels.

major comments (2)

Abstract: the existence of schemes and an outer bound is asserted, yet no explicit channel transition matrices, rate expressions, error analysis, or derivation steps are supplied; without these the central claims cannot be verified.
Abstract: the claim that the new outer bound lies below the Venkatesan-Anantharam capacity (and is therefore tight for the decomposing setting) is stated at a high level; the specific form of the outer bound and the steps establishing the inequality are not visible, preventing assessment of whether the comparison is load-bearing or merely notational.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed comments on our manuscript. We address each major comment below, pointing to the relevant sections of the full paper where the requested details appear.

read point-by-point responses

Referee: Abstract: the existence of schemes and an outer bound is asserted, yet no explicit channel transition matrices, rate expressions, error analysis, or derivation steps are supplied; without these the central claims cannot be verified.

Authors: The abstract is a concise high-level summary. Explicit channel transition matrices for the special settings, achievable rate expressions, error probability analyses for the constructive schemes, and the full derivation steps for the outer bound (including the cardinality bound on auxiliary variables) are all supplied in the body of the manuscript: the schemes appear in Section III with accompanying error analysis, while the outer bound derivation is in Section IV. revision: no
Referee: Abstract: the claim that the new outer bound lies below the Venkatesan-Anantharam capacity (and is therefore tight for the decomposing setting) is stated at a high level; the specific form of the outer bound and the steps establishing the inequality are not visible, preventing assessment of whether the comparison is load-bearing or merely notational.

Authors: The specific form of the outer bound is stated explicitly as the single-letter expression in Theorem 1 (with the associated cardinality bound), and the proof that it is upper-bounded by the Venkatesan-Anantharam capacity is given in Section V. The comparison proceeds by showing that every feasible auxiliary distribution for the new bound satisfies the mutual-information constraints of the Venkatesan-Anantharam region, establishing the inequality directly rather than notationally. revision: no

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper derives an outer bound on CR capacity for the intertwined receiver-decomposable two-way channel class via standard mutual-information arguments and a cardinality bound on auxiliaries, then shows this bound is at most the Venkatesan-Anantharam capacity (an external result by unrelated authors). Constructive inner bounds are given by explicit schemes. No equation reduces a claimed result to a fitted parameter, self-definition, or load-bearing self-citation; the comparison uses an independent prior capacity expression whose validity does not depend on the present paper's fitted values or definitions. The class definition (marginals depending on transmitted signals) is stated upfront and used directly in the bound derivation, with no smuggling of ansatzes or renaming of known results as new organization.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The abstract invokes standard discrete-memoryless channel assumptions and the definition of receiver-decomposability; no free parameters, invented entities, or ad-hoc axioms are visible.

axioms (1)

domain assumption The two-way channels are discrete memoryless with marginal transition probabilities that may depend on the transmitted symbol.
Standard modeling choice for capacity problems; stated in the abstract's definition of intertwined channels.

pith-pipeline@v0.9.0 · 5622 in / 1187 out tokens · 39058 ms · 2026-05-25T15:00:35.321560+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

5 extracted references · 5 canonical work pages

[1]

Common randomness in information theory and cryptography. ii. cr capacity,

R. Ahlswede and I. Csiszar, “Common randomness in information theory and cryptography. ii. cr capacity,” IEEE Trans. on Info. Theory, vol. 44, no. 1, Jan. 1998

work page 1998
[2]

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

S. Venkatesan and V . Anantharam, “The common randomness capacity of a pair of independent discrete memoryless channels,” IEEE Trans. on Info. Theory , vol. 44, no. 1, Jan. 1998

work page 1998
[3]

Capacity of two-way channels with symmetry properties,

J. J. Weng, L. Song, F. Alajaji, and T. Linder, “Capacity of two-way channels with symmetry properties,” IEEE Trans. on Info. Theory, to appear

work page
[4]

Preserving receiver’s anonymity for circular structured p2p networks,

A. Naghizadeh, S. Berenjian, B. Razeghi, S. Shahanggar, and N. R. Pour, “Preserving receiver’s anonymity for circular structured p2p networks,” in Annual IEEE Consumer Communications and Networking Conference (CCNC) , July 2015

work page 2015
[5]

Dependence balance outer bounds for the discrete memoryless two-way multiple access broadcast channel,

S. Hajizadeh and N. Devroye, “Dependence balance outer bounds for the discrete memoryless two-way multiple access broadcast channel,” in Proc. Allerton Conf. Commun., Control and Comp. , Sep.-Oct. 2014

work page 2014

[1] [1]

Common randomness in information theory and cryptography. ii. cr capacity,

R. Ahlswede and I. Csiszar, “Common randomness in information theory and cryptography. ii. cr capacity,” IEEE Trans. on Info. Theory, vol. 44, no. 1, Jan. 1998

work page 1998

[2] [2]

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

S. Venkatesan and V . Anantharam, “The common randomness capacity of a pair of independent discrete memoryless channels,” IEEE Trans. on Info. Theory , vol. 44, no. 1, Jan. 1998

work page 1998

[3] [3]

Capacity of two-way channels with symmetry properties,

J. J. Weng, L. Song, F. Alajaji, and T. Linder, “Capacity of two-way channels with symmetry properties,” IEEE Trans. on Info. Theory, to appear

work page

[4] [4]

Preserving receiver’s anonymity for circular structured p2p networks,

A. Naghizadeh, S. Berenjian, B. Razeghi, S. Shahanggar, and N. R. Pour, “Preserving receiver’s anonymity for circular structured p2p networks,” in Annual IEEE Consumer Communications and Networking Conference (CCNC) , July 2015

work page 2015

[5] [5]

Dependence balance outer bounds for the discrete memoryless two-way multiple access broadcast channel,

S. Hajizadeh and N. Devroye, “Dependence balance outer bounds for the discrete memoryless two-way multiple access broadcast channel,” in Proc. Allerton Conf. Commun., Control and Comp. , Sep.-Oct. 2014

work page 2014