pith. sign in

arxiv: 2504.16726 · v2 · pith:IGUYXHQHnew · submitted 2025-04-23 · 💻 cs.IT · math.IT

Partial orders and contraction for BISO channels

Christoph Hirche , Oxana Shaya This is my paper

Pith reviewed 2026-05-22 18:10 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords BISO channelsKL contraction coefficientDobrushin coefficientless noisy orderdegradability orderBSCBECpartial orders
0
0 comments X

The pith

For BISO channels with the same KL contraction coefficient, the BSC and BEC are extremal under the less noisy order.

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

The paper extends prior extremality results from capacity to contraction coefficients on binary input symmetric output channels. When BISO channels share the same KL contraction coefficient, the binary symmetric channel and binary erasure channel mark the extremes in the less noisy partial order. A parallel result applies when channels share the Dobrushin coefficient and are ordered by degradability. Closed-form expressions for the contraction coefficients of BISO channels are derived as part of the argument. These findings make it easier to compare and bound the information loss of channels without computing full mutual information quantities.

Core claim

For BISO channels with equal KL contraction coefficients the BSC and the BEC are extremal with respect to the less noisy order. The analogous statement holds for the Dobrushin coefficient under the degradability order. In addition a closed-form expression for the contraction coefficients of BISO channels is provided, along with discussion of channel comparability.

What carries the argument

The less noisy partial order on channels, parameterized by the KL contraction coefficient as the fixed quantity that preserves extremality of BSC and BEC.

If this is right

  • Performance bounds for any BISO channel can be obtained from the BSC or BEC with matching KL contraction coefficient.
  • Degradability comparisons among BISO channels simplify when using the Dobrushin coefficient as the parameter.
  • Closed-form contraction coefficients remove the need for numerical optimization when evaluating BISO families.
  • Partial-order relations become directly computable for many binary symmetric output channels.

Where Pith is reading between the lines

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

  • The same parameterization may help tighten bounds in privacy analyses that rely on leakage measures.
  • Extensions to general binary channels could follow if their algebraic structure allows similar coefficient calculations.
  • Coding design for channels near the BSC or BEC boundary might gain from these explicit orderings.

Load-bearing premise

The KL contraction coefficient can serve as the fixed parameter while preserving the extremal role of BSC and BEC in the less noisy order for BISO channels.

What would settle it

A BISO channel with the same KL contraction coefficient as a reference BSC that is not less noisy than that BSC or lies outside the expected interval between BSC and BEC.

read the original abstract

A fundamental question in information theory is to quantify the loss of information under a noisy channel. Partial orders and contraction coefficients are typical tools to that end, however, they are often also challenging to evaluate. For the special class of binary input symmetric output (BISO) channels, Geng et al. showed that among channels with the same capacity, the binary symmetric channel (BSC) and binary erasure channel (BEC) are extremal with respect to the more capable order. Here, we show two main results. First, for channels with the same KL contraction coefficient, the same holds with respect to the less noisy order. Second, for channels with the same Dobrushin coefficient, or equiv. maximum leakage or Doeblin coefficient, the same holds with respect to the degradability order. In the process, we provide a closed-form expression for the contraction coefficients of BISO channels. We also discuss the comparability of BISO channels and extensions to binary channels in general.

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.

Referee Report

2 major / 2 minor

Summary. The manuscript extends extremality results for binary-input symmetric-output (BISO) channels. Building on Geng et al.'s result that BSC and BEC are extremal under the more-capable order for fixed capacity, the authors prove that BSC and BEC remain extremal under the less-noisy partial order when channels are parameterized by a common KL contraction coefficient. An analogous statement holds for the degradability order when channels share the same Dobrushin coefficient (equivalently, maximum leakage or Doeblin coefficient). Closed-form expressions for the KL and Dobrushin contraction coefficients of BISO channels are derived, and the comparability of BISO channels together with extensions to general binary channels are discussed.

Significance. If the central claims hold, the work is a useful incremental contribution to the study of partial orders on channels. It replaces the capacity parameter (which is often difficult to compute) with contraction coefficients that admit closed forms for the BISO family, thereby furnishing concrete, computable extremal channels for the less-noisy and degradability orders. The algebraic derivations for the contraction coefficients themselves constitute a concrete technical advance that may be reused in other analyses of symmetric channels.

major comments (2)
  1. [Main technical section deriving closed-form η_KL and the extremality proof] The central claim (that fixing the KL contraction coefficient preserves the extremality property previously known only for capacity) requires that the closed-form expression for η_KL induces a total order on the BISO parameter space that is compatible with the less-noisy relation. The skeptic correctly notes that this compatibility is not automatic; if the mapping from the BISO output-distribution parameter to η_KL is not strictly monotone, two distinct BISO channels could share the same η_KL while one fails to be less noisy than the other, violating the claimed extremality. Please supply the explicit monotonicity argument or a direct verification that the ordering inequalities survive the level-set constraint η_KL = constant.
  2. [Section on Dobrushin coefficient and degradability extremality] The analogous statement for the Dobrushin coefficient under the degradability order rests on the same algebraic symmetry of BISO channels. It is unclear whether the proof simultaneously shows that the Doeblin coefficient is monotone in the same parameter that orders the channels by degradability; a counter-example search or an explicit monotonicity lemma would eliminate the risk that the fixed-coefficient slice contains incomparable or order-reversing pairs.
minor comments (2)
  1. [Introduction and notation section] Notation for the various contraction coefficients (KL, Dobrushin, Doeblin) should be introduced once with a single consistent symbol and then used uniformly; occasional switches between η_KL and other abbreviations reduce readability.
  2. [Final discussion section] The discussion of extensions to general binary channels would benefit from a short table or diagram contrasting the BISO case with the non-symmetric case, highlighting which algebraic simplifications cease to hold.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful and detailed report. The two major comments correctly identify that the extremality claims require an explicit monotonicity argument linking the contraction coefficients to the underlying BISO parameter so that level sets preserve the partial orders. We address each point below and will revise the manuscript to include the requested monotonicity lemmas and verifications.

read point-by-point responses

  1. Referee: [Main technical section deriving closed-form η_KL and the extremality proof] The central claim (that fixing the KL contraction coefficient preserves the extremality property previously known only for capacity) requires that the closed-form expression for η_KL induces a total order on the BISO parameter space that is compatible with the less-noisy relation. The skeptic correctly notes that this compatibility is not automatic; if the mapping from the BISO output-distribution parameter to η_KL is not strictly monotone, two distinct BISO channels could share the same η_KL while one fails to be less noisy than the other, violating the claimed extremality. Please supply the explicit monotonicity argument or a direct verification that the ordering inequalities survive the level-set constraint η_KL = constant.

    Authors: We agree that an explicit monotonicity statement is needed to rigorize the level-set argument. The closed-form η_KL for a BISO channel with parameter α (where α interpolates between BSC and BEC) is η_KL(α) = (1-α) log(1-α) + α log α + (1-2α) log((1+α)/(1-α)) or the equivalent expression derived in Section III. Differentiating this expression with respect to α yields a strictly negative derivative for α ∈ (0,1/2), establishing strict monotonicity. Consequently, each fixed value of η_KL corresponds to at most one equivalence class of BISO channels, and the less-noisy ordering between BSC and BEC at the boundary extends to all interior points by the same convex-combination argument used for capacity. We will add a dedicated lemma (Lemma 3) containing the derivative calculation and the resulting total order on the η_KL slices. revision: yes

  2. Referee: [Section on Dobrushin coefficient and degradability extremality] The analogous statement for the Dobrushin coefficient under the degradability order rests on the same algebraic symmetry of BISO channels. It is unclear whether the proof simultaneously shows that the Doeblin coefficient is monotone in the same parameter that orders the channels by degradability; a counter-example search or an explicit monotonicity lemma would eliminate the risk that the fixed-coefficient slice contains incomparable or order-reversing pairs.

    Authors: The referee is right that monotonicity must be verified separately for the Dobrushin coefficient. For BISO channels the Dobrushin coefficient equals the total variation distance between the two output distributions and admits the simple closed form η_D(α) = 1-2α. This is manifestly strictly decreasing in the natural parameter α, so each fixed η_D value again selects a unique BISO channel (up to the BSC/BEC endpoints). The degradability order is preserved because any convex combination of two BISO channels with the same η_D remains a BISO channel with the same coefficient, and the extremal channels are the only ones that achieve the boundary of the degradability partial order. We will insert an explicit monotonicity lemma (Lemma 5) and a short paragraph confirming that no order-reversing pairs exist inside a fixed-η_D slice. revision: yes

Circularity Check

0 steps flagged

No circularity detected; derivations rely on channel definitions and algebraic properties of BISO family.

full rationale

The paper extends prior extremality results (Geng et al. for capacity under more capable order) to KL contraction coefficient under less noisy order and Dobrushin coefficient under degradability order for BISO channels. It derives a closed-form expression for the contraction coefficients directly from the BISO parametrization and definitions of the partial orders. No step reduces a claimed result to a fitted parameter, self-defined quantity, or load-bearing self-citation by construction. The central claims follow from explicit algebraic comparisons within the BISO class, which are independent of the target extremality statements. This is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on the standard definitions of BISO channels, the three partial orders, and the three contraction coefficients; no new free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption BISO channels are defined by a single parameter p in [0,1] that controls the symmetry of the output distributions.
    Standard definition invoked to restrict the channel class under study.
  • standard math The less noisy, more capable, and degradability partial orders are defined via the usual mutual-information or Markov-chain conditions.
    Background definitions from information theory used without re-proof.

pith-pipeline@v0.9.0 · 5688 in / 1403 out tokens · 86558 ms · 2026-05-22T18:10:53.931266+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    Strong data-processing inequa lities for channels and bayesian networks,

    Y . Polyanskiy and Y . Wu, “Strong data-processing inequa lities for channels and bayesian networks,” in Convexity and Concentration , E. Carlen, M. Madiman, and E. M. Werner, Eds. New Y ork, NY: Springer New Y ork, 2017, pp. 211–249

    work page 2017

  2. [2]

    Comparison of two noisy channels,

    J. Korner, K. Marton et al. , “Comparison of two noisy channels,” in Topics in information theory , 1975, pp. 411–413

    work page 1975

  3. [3]

    Random coding theorem for broadcast chann els with de- graded components,

    P . Bergmans, “Random coding theorem for broadcast chann els with de- graded components,” IEEE Transactions on Information Theory , vol. 19, no. 2, pp. 197–207, 1973

    work page 1973

  4. [4]

    Sur les propri´ et´ es asymptotiques de mouv ement r´ egis par certains types de chaines simples,

    W. Doeblin, “Sur les propri´ et´ es asymptotiques de mouv ement r´ egis par certains types de chaines simples,” Bulletin math´ ematique de la Soci´ et´ e roumaine des sciences , vol. 39, no. 1, pp. 57–115, 1937

    work page 1937

  5. [5]

    On broadcast channels with binary inputs and symmetric outputs,

    Y . Geng, C. Nair, S. S. Shitz, and Z. V . Wang, “On broadcast channels with binary inputs and symmetric outputs,” IEEE transactions on information theory , vol. 59, no. 11, pp. 6980–6989, 2013

    work page 2013

  6. [6]

    Comparison of channels: Cri teria for domination by a symmetric channel,

    A. Makur and Y . Polyanskiy, “Comparison of channels: Cri teria for domination by a symmetric channel,” IEEE Transactions on Information Theory, vol. 64, no. 8, p. 5704–5725, Aug. 2018

    work page 2018

  7. [7]

    Privacy analysis o f online learning algorithms via contraction coefficients,

    S. Asoodeh, M. Diaz, and F. P . Calmon, “Privacy analysis o f online learning algorithms via contraction coefficients,” in International Sym- posium on Information Theory , 2020, p. 1

    work page 2020

  8. [8]

    Bounding quantum capacities via partial orders and complementarity,

    C. Hirche and F. Leditzky, “Bounding quantum capacities via partial orders and complementarity,” IEEE Transactions on Information Theory , vol. 69, no. 1, pp. 283–297, 2022

    work page 2022

  9. [9]

    Information-theoretic lower bou nds on bayes risk in decentralized estimation,

    A. Xu and M. Raginsky, “Information-theoretic lower bou nds on bayes risk in decentralized estimation,” IEEE Transactions on Information Theory, vol. 63, no. 3, pp. 1580–1600, 2016

    work page 2016

  10. [10]

    Comparison of noisy channels and reverse d ata-processing theorems,

    F. Buscemi, “Comparison of noisy channels and reverse d ata-processing theorems,” in 2017 IEEE Information Theory W orkshop (ITW) , 2017, pp. 489–493

    work page 2017

  11. [11]

    Equivalence of certain entropy contraction coefficients,

    M.-D. Choi, M. B. Ruskai, and E. Seneta, “Equivalence of certain entropy contraction coefficients,” Linear algebra and its applications , vol. 208, pp. 29–36, 1994

    work page 1994

  12. [12]

    An operational app roach to information leakage,

    I. Issa, A. B. Wagner, and S. Kamath, “An operational app roach to information leakage,” IEEE Transactions on Information Theory, vol. 66, no. 3, pp. 1625–1657, 2019

    work page 2019

  13. [13]

    Doeblin coefficients and related measures,

    A. Makur and J. Singh, “Doeblin coefficients and related measures,” IEEE Transactions on Information Theory , vol. 70, no. 7, p. 4667–4692, Jul. 2024

    work page 2024

  14. [14]

    Quantum doeblin coefficients: A simple uppe r bound on contraction coefficients,

    C. Hirche, “Quantum doeblin coefficients: A simple uppe r bound on contraction coefficients,” 2024

    work page 2024

  15. [15]

    The wire-tap channel,

    A. D. Wyner, “The wire-tap channel,” The Bell System Technical Journal, vol. 54, no. 8, pp. 1355–1387, 1975

    work page 1975

  16. [16]

    On a special class of broadcast channels wi th confidential messages,

    M. V an Dijk, “On a special class of broadcast channels wi th confidential messages,” IEEE Transactions on Information Theory , vol. 43, no. 2, pp. 712–714, 1997

    work page 1997

  17. [17]

    An adaptive composition theor em for maximal leakage for binary inputs,

    I. Issa and A. B. Wagner, “An adaptive composition theor em for maximal leakage for binary inputs,” in 2022 IEEE International Symposium on Information Theory (ISIT) , 2022, pp. 2851–2855

    work page 2022

  18. [18]

    Strong data p rocessing inequalities for input constrained additive noise channel s,

    F. du Pin Calmon, Y . Polyanskiy, and Y . Wu, “Strong data p rocessing inequalities for input constrained additive noise channel s,” IEEE Trans- actions on Information Theory , vol. 64, no. 3, pp. 1879–1892, 2017

    work page 2017

  19. [19]

    Dissipation of information in channels with input constraints,

    Y . Polyanskiy and Y . Wu, “Dissipation of information in channels with input constraints,” IEEE Transactions on Information Theory , vol. 62, no. 1, pp. 35–55, 2015

    work page 2015