A Tight Uniform Continuity Bound for Equivocation

Graeme Smith; Mohammad A. Alhejji

A Tight Uniform Continuity Bound for Equivocation

T0 review · 0 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For finite alphabets, the conditional Shannon entropy changes by at most ε log(|X|-1)+h(ε) under total variation distance ε, and this bound is tight.

desk verdict A sound, self-contained proof of a tight, alphabet-size-independent continuity bound for classical equivocation; the main soft spot is a missing explicit comparison with Winter's quantum bound. read the letter →

arxiv 1909.00787 v3 pith:JOHEOL3U submitted 2019-09-02 cs.IT math.ITquant-ph

Mohammad A. Alhejji , Graeme Smith This is my paper · ORCID

classification cs.ITmath.ITquant-ph MSC 94A17

keywords conditionalShannonentropyequivocationuniformcontinuityboundtotalvariationdistancetightG-majorizationmajorization

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper answers a basic question: if two joint distributions on finite alphabets X and Y differ by at most ε in total variation distance, how far apart can their conditional Shannon entropies H(X|Y) be? The answer is |H(X|Y)-H(X'|Y')| ≤ ε log(|X|-1)+h(ε), and the paper shows this bound is tight for every allowed ε up to 1-1/|X|. The bound is uniform in the size of Y, so it remains useful when the conditioning system is large. This matters because distributions are usually estimated or approximated from data or from a restricted class, and a tight worst-case guarantee controls the error in computed information-theoretic rates.

What carries the argument

The engine of the proof is the subgroup S_{X|Y} of permutations that leave H(X|Y) invariant: permutations of the Y labels and, within each fixed Y outcome, arbitrary permutations of the X labels. The authors order both distributions into blocks according to these symmetries, then apply a 'walking' transfer step due to Pinelis that moves probability mass within each block to make qX'Y' concentrated on one X value per Y outcome, without increasing total variation distance or decreasing the entropy difference. An averaging stochastic map E: νXY(i,j) ↦ (1/|Y|)∑_j νXY(i,j) then turns both distributions into product forms with uniform Y marginals while preserving the invariants. At that point the ordinary (unconditional) Shannon entropy bound applies and yields ε log(|X|-1)+h(ε).

What would settle it

Compute the entropy difference for the paper's extremal example—qX'Y'(1,1)=1 and pXY(1,1)=1-ε, pXY(i,1)=ε/(|X|-1) for i≠1—and check it equals ε log(|X|-1)+h(ε); any finite-support pair exceeding the right-hand side would refute the theorem.

Watch

Extended reading notes

Core claim

The central result is that equivocation—the conditional Shannon entropy H(X|Y)—satisfies a tight uniform continuity bound with respect to total variation distance. Specifically, for ε ∈ (0, 1-1/|X|], any two finitely supported joint distributions pXY and qX'Y' on X × Y with TV(pXY, qX'Y') ≤ ε obey |H(X|Y)-H(X'|Y')| ≤ ε log(|X|-1)+h(ε), where h is the binary entropy function. Moreover, for each such ε there are distributions with TV exactly ε that saturate the inequality, so no strictly smaller bound of this form exists. The proof reduces the problem to the unconditional Shannon entropy by walking two distributions toward a product form while preserving total variation distance and monotonicity of the entropy difference.

Load-bearing premise

The proof requires the conditioning random variable Y to have a finite alphabet; the permutation-group and block-averaging steps break down when |Y| is infinite, and the paper leaves that case open.

Editorial extensions

If this is right

For any finite alphabet sizes |X| and |Y|, two joint distributions within total variation ε have equivocations differing by at most ε log(|X|-1)+h(ε), a bound that does not grow with |Y|.
The bound is saturated for every ε ∈ (0, 1-1/|X|], e.g. by q concentrated on a single point and p spreading ε uniformly over the remaining |X|-1 outcomes, so the worst-case error is fully characterized.
Entropy estimates computed from empirically or approximately estimated distributions inherit this worst-case guarantee on the resulting conditional entropy values.
The proof does not cover infinite Y; the paper states the infinite-alphabet version as an open problem.
By the same group-invariance reasoning, the authors suggest that conditional Rényi entropies and mutual information may admit similar symmetry-based continuity treatments.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A testable extension is to check whether the same bound holds for countably infinite Y; the finite-support obstruction is the averaging map E and the permutation group, but a limiting argument might recover the bound if the marginal on Y is controlled.
The proof technique suggests that other entropy-like quantities invariant under a subgroup of the symmetric group, such as certain conditional Rényi entropies, should obey analogous continuity bounds with the group structure replacing Schur-majorization; this is a research program the paper hints at but does not carry out.
For communication-rate algorithms that approximate arbitrary distributions by a special class, the tightness of the bound means the worst-case error in the computed rate can be exactly this large, so such algorithms should budget for it.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper proves a tight uniform continuity bound for classical conditional Shannon entropy: |H(X|Y)-H(X'|Y')| ≤ ε log(|X|-1)+h(ε) under total variation distance, with a matching tightness construction. The proof is self-contained and the technique is genuinely fresh: instead of the usual Fannes-type or Alicki-Fannes-type arguments, it uses G-majorization, a reordering step, a Pinelis-style 'walking' of the distributions, and a stochastic averaging map. I went through the walking step carefully, including the tricky case where an I_j block is empty; the transfers preserve total variation and do not decrease the entropy difference, and the convexity argument checks out. The reduction to the unconditional bound is clean, and the tightness example is correct. This is a nice, solid result.

On novelty: the paper claims the bound was not previously known in the classical case, and the literature it cites supports that claim. But it does not cite or compare against Winter's tight uniform continuity bound for quantum conditional entropy (Commun. Math. Phys. 347, 2016), which is arguably a strictly stronger statement that would imply this classical result. That omission matters for positioning: the authors should clarify whether their contribution is the first explicit classical statement, or a new proof of a known consequence. Either way, the paper has value, because the G-majorization proof is elementary and may generalize to other conditional entropies, as the concluding remarks suggest.

The only real limitation is the finite-support assumption on Y, which the authors explicitly flag and leave as an open problem. That is honest and not a defect for a note of this scope. The paper is short, clearly written, and the math is reproducible from the text. No fitted parameters, no hand-waving.

Who is this for? People working on continuity bounds for entropies, entropy estimation, and rate approximation. It is a useful toolbox result, not a breakthrough. It deserves a serious referee and, after a revision that addresses the Winter comparison, acceptance.

I would cite it and bring it to a reading group.

Referee Report

0 major / 5 minor

Summary. The paper establishes a tight uniform continuity bound for the conditional Shannon entropy (equivocation) of two finite jointly distributed random variables. The main theorem states that for any pXY, qX'Y' on X×Y with TV(pXY,qX'Y') ≤ ε, where 0<ε≤1−1/|X|, the absolute difference of the equivocations is at most ε log(|X|−1)+h(ε), and the bound is saturated for every ε in that range. The proof is a self-contained three-step argument: first reorder the joint probability vectors in a way that preserves total variation and equivocation; then apply a 'walking' transformation that reduces one distribution to one with H(X'|Y')=0 while not increasing total variation and not decreasing the entropy difference; finally average over the Y blocks to obtain product distributions, reducing the problem to the tight bound for unconditional entropy. The paper also provides an explicit tightness example and flags that the proof requires |Y| finite, leaving the infinite-alphabet case open.

Significance. If the theorem is correct, it provides the sharp form of the continuity bound for classical conditional entropy with alphabet-size dependence log(|X|−1) rather than log|X|, and it is independent of |Y|. The proof is elegant and genuinely elementary: it exploits the invariance of equivocation under the symmetry group S_{X|Y} and a convexity-based walking argument, with no fitted parameters or post hoc constructions. The explicit tightness example makes the optimality claim directly checkable, and the finite-support restriction on the conditioning variable is stated honestly with the infinite-alphabet case left open. The main caveat is that the introduction mischaracterizes Ref. [8] (Winter), which does prove tight uniform continuity bounds for quantum conditional entropy; the authors should explain the precise relation between their classical bound and the classical specialization of Winter's bound. This is a presentation and positioning issue rather than a technical flaw.

minor comments (5)

[Section I] The sentence 'uniform bounds, which are not tight but are independent of the size of the conditioning system, were proven for the conditional Shannon and von Neumann entropies in [10], [8]' is inaccurate for [8]: Winter's paper proves tight uniform continuity bounds for quantum conditional entropy. Please revise this sentence and explicitly compare the classical specialization of Winter's bound, ε log|X| + (1+ε)h(ε/(1+ε)), with the present bound, ε log(|X|-1) + h(ε), so that the contribution is stated precisely.
[Section II-B] The monotonicity computation around Eqs. (14)-(17) is terse. Please state that the block totals pY(j) and qY'(j) are fixed during the transfers, so the displayed expression is the change of pY(j)H(X|Y=j) − qY'(j)H(X'|Y'=j), and that the two bracketed terms are nonnegative by convexity of η(x)=x log x together with inequalities (12) and (13).
[Section II-B, I_j empty case] In the paragraph treating the case I_j=∅, the discussion of what happens if qY'(j)=0, or if qX'Y'(1,j)−pXY(1,j) remains negative when qX'Y'(1,j) reaches qY'(j), is implicit. A short explicit statement that zero-probability blocks require no action and that the averaging argument only needs the final marginal qX'(1)=1 would improve readability.
[Section II-C] After the averaging map E in Eq. (18), the paper should state explicitly that H(X'|Y')=0 and H(X|Y)=H(X) for the resulting product distributions; this makes the reduction to the unconditional entropy estimate immediate.
[Throughout] There are minor typographical and stylistic issues: 'We present' with a capital W in the introduction, 'V arious' in the concluding remarks, and inconsistent use of 'non-increasing' versus 'nonincreasing'; these should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof is self-contained and derives the conditional entropy bound from explicit reductions to the unconditional entropy bound, with tightness by explicit construction.

full rationale

Walking through the derivation chain: the paper proves the conditional bound by successively transforming q to a degenerate distribution while not increasing total variation distance and not decreasing the entropy difference (Section II-B), then applying the unconditional uniform continuity bound to the resulting product distributions. The unconditional bound is not assumed as a black-box equivalent of the target; it is restated and proved inline via Schur majorization and the elementary inequality H(X) ≤ ǫ log(|X|−1)+h(ǫ). The tightness construction (Eqs. (21)–(22)) is explicit: with q(1,1)=1, p(1,1)=1−ǫ, and p(i,1)=ǫ/(|X|−1), direct evaluation gives TV=ǫ and H(X|Y)−H(X'|Y') = ǫ log(|X|−1)+h(ǫ). The only author self-citation, Ref. [13] (Leung–Smith), is motivational for capacity-approximation applications and plays no role in the proof. The finite-support assumption on the conditioning variable is stated in the theorem and explicitly flagged in the Concluding Remarks as an open problem, not hidden. The Pinelis walking technique is cited as an external proof idea, not as a substitute for the derivation. No fitted parameter is renamed as a prediction, no load-bearing step reduces by construction to the claimed inequality, and no uniqueness or existence claim is imported from prior work by the same authors. The central inequality and its saturation are therefore derived rather than assumed.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The proof rests on standard convexity and majorization facts and on the finite-support assumption for Y. No free parameters or new entities are introduced.

assumptions (4)

standard math Shannon entropy and conditional entropy are concave and invariant under the group S_{X|Y} of permutations of Y labels and exchanges within Y blocks.
Invariance follows from the definition (Eq. 4); concavity is a standard property of conditional entropy.
standard math G-majorization preorder: if vector p is in the convex hull of the orbit of q under a group G, then any G-invariant concave function f satisfies f(p) >= f(q).
Cited from Steerneman and Marshall-Olkin; used in Section II.B to assert that entropy does not increase under the walking replacements.
domain assumption The stochastic map E in Eq. (18) is a convex combination of permutations in S_{X|Y}.
This requires finite |Y|; the authors explicitly assume finite support for Y and leave the infinite case open.
standard math eta(x) = x log x is convex on (0,1].
Used in the walking step to show the entropy difference does not decrease.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Tight Uniform Continuity Bound for Equivocation." pith.science (2026). https://pith.science/paper/JOHEOL3U

@misc{pith2026190900787,
  author       = {Pith},
  title        = {Pith review of: A Tight Uniform Continuity Bound for Equivocation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JOHEOL3U}},
  note         = {Machine review of arXiv:1909.00787}
}

read the original abstract

We prove a tight uniform continuity bound for the conditional Shannon entropy of discrete finitely supported random variables in terms of total variation distance.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

A strong converse for stabilizer codes over Pauli channels via the blowing-up lemma
quant-ph 2026-07 accept novelty 7.0 of 10

Above the coherent information of its own input, any stabilizer code over a product Pauli channel has entanglement fidelity decaying exponentially in block length.
Optimal uniform continuity bound for conditional entropy of classical--quantum states
quant-ph 2019-09 accept novelty 6.0 of 10

For classical-quantum states, the conditional entropy can change by at most epsilon log2(d_B-1) + h2(epsilon) under a trace-distance perturbation epsilon, and this bound cannot be improved.

Reference graph

Works this paper leans on

20 extracted references · 18 canonical work pages · cited by 2 Pith papers

[8]

Tight uniform continuity bounds for quantum entropies: Conditional entropy, relative entropy distanc e and energy constraints,

A. Winter, “Tight uniform continuity bounds for quantum entropies: Conditional entropy, relative entropy distanc e and energy constraints,” Communications in Mathematical Physics , vol. 347, no. 1, pp. 291–313, Oct 2016. [Online]. Available : https://doi.org/10.1007/s00220-016-2609-8

doi:10.1007/s00220-016-2609-8 2016
[1]

Estimating mutual information via kolmogoro v distance,

Z. Zhang, “Estimating mutual information via kolmogoro v distance,” IEEE Transactions on Information Theory , vol. 53, no. 9, pp. 3280– 3282, Sep. 2007

work page 2007
[2]

The interplay between entropy and v ariational distance,

S. Ho and R. W. Y eung, “The interplay between entropy and v ariational distance,” IEEE Transactions on Information Theory , vol. 56, no. 12, pp. 5906–5929, Dec 2010

work page 2010
[3]

Entropy bounds for discrete random variables via maximal coupling,

I. Sason, “Entropy bounds for discrete random variables via maximal coupling,” IEEE Transactions on Information Theory , vol. 59, no. 11, pp. 7118–7131, Nov 2013

work page 2013
[4]

A continuity property of the entropy density for spin lattice systems,

M. Fannes, “A continuity property of the entropy density for spin lattice systems,” Comm. Math. Phys. , vol. 31, no. 4, pp. 291–294,

work page
[5]

A sharp continuity estimate for the v on neumann entropy,

K. M. R. Audenaert, “A sharp continuity estimate for the v on neumann entropy,” Journal of Physics A: Mathematical and Theoretical , vol. 40, no. 28, pp. 8127–8136, jun 2007. [Online]. Availabl e: https://doi.org/10.1088%2F1751-8113%2F40%2F28%2Fs18

work page 2007
[6]

Maximum and minimum entropy st ates yielding local continuity bounds,

E. P . Hanson and N. Datta, “Maximum and minimum entropy st ates yielding local continuity bounds,” Journal of Mathematical Physics , vol. 59, no. 4, p. 042204, 2018. [Online]. Available: https://doi.org/10.1063/1.5000120

work page doi:10.1063/1.5000120 2018
[7]

Entropy and total variation distance (answ er),

I. Pinelis, “Entropy and total variation distance (answ er),” MathOverﬂow, visited on 2019-08-03. [Online]. Avail able: https://mathoverﬂow.net/questions/310689/entropy-an d-total-variation-distance

work page 2019

Show all 20 references

[9]

Tight uniform continuity boun d for a family of entropies,

E. P . Hanson and N. Datta, “Tight uniform continuity boun d for a family of entropies,” 2017

2017
[10]

Continuity of quantum conditi onal information,

R. Alicki and M. Fannes, “Continuity of quantum conditi onal information,” Journal of Physics A: Mathematical and General , vol. 37, no. 5, pp. L55–L57, jan 2004. [Online]. Available: https://doi.org/10.1088%2F0305-4470%2F37%2F5%2Fl01

2004
[11]

T. M. Cover and J. A. Thomas, Elements of Information Theory (Wiley Series in Telecommun ications and Signal Processing) . New Y ork, NY , USA: Wiley-Interscience, 2006

2006
[12]

Cryptographic distingu ishability measures for quantum-mechanical states,

C. A. Fuchs and J. van de Graaf, “Cryptographic distingu ishability measures for quantum-mechanical states,” IEEE Transactions on Information Theory , vol. 45, no. 4, pp. 1216–1227, May 1999

1999
[13]

Continuity of quantum channel ca pacities,

D. Leung and G. Smith, “Continuity of quantum channel ca pacities,” Communications in Mathematical Physics , vol. 292, no. 1, pp. 201–215, Nov 2009. [Online]. Available: https://doi.org/10.1007/s00220-009-0833-1

2009 doi
[14]

Tight uniform continuity bounds for th e quantum conditional mutual information, for the holevo qu antity, and for capacities of quantum channels,

M. E. Shirokov, “Tight uniform continuity bounds for th e quantum conditional mutual information, for the holevo qu antity, and for capacities of quantum channels,” Journal of Mathematical Physics , vol. 58, no. 10, p. 102202, 2017. [Online]. Available: https://doi.org/10.1063...

2017 doi
[15]

Appro ximate degradable quantum channels,

D. Sutter, V . B. Scholz, A. Winter, and R. Renner, “Appro ximate degradable quantum channels,” IEEE Transactions on Information Theory , vol. 63, no. 12, pp. 7832–7844, Dec 2017

2017
[16]

A. W. Marshall, I. Olkin, and B. C. Arnold, Inequalities: Theory of Majorization and its Applications , 2nd ed. Springer, 2011, vol. 143

2011
[17]

G-majorization, group-induced cone o rderings, and reﬂection groups,

A. Steerneman, “G-majorization, group-induced cone o rderings, and reﬂection groups,” Linear Algebra and its Applications , vol. 127, pp. 107 – 119, 1990. [Online]. Available: http://www.sciencedirect.com/science/article/pii/002437959090338D

1990
[18]

Tomamichel, Quantum Information Processing with Finite Resources: Mat hematical F oundations, 1st ed

M. Tomamichel, Quantum Information Processing with Finite Resources: Mat hematical F oundations, 1st ed. Springer Publishing Company, Incorporated, 2015

2015
[19]

Information measures and capacity of orde r α for discrete memoryless channels,

S. Arimoto, “Information measures and capacity of orde r α for discrete memoryless channels,” Topics in Information Theory , 1977. [Online]. Available: https://ci.nii.ac.jp/naid/10022581674/en/

1977
[1973]

Available: https://projecteuclid.org:443/euclid.cmp/1103859037

[Online]. Available: https://projecteuclid.org:443/euclid.cmp/1103859037

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [8]

Tight uniform continuity bounds for quantum entropies: Conditional entropy, relative entropy distanc e and energy constraints,

A. Winter, “Tight uniform continuity bounds for quantum entropies: Conditional entropy, relative entropy distanc e and energy constraints,” Communications in Mathematical Physics , vol. 347, no. 1, pp. 291–313, Oct 2016. [Online]. Available : https://doi.org/10.1007/s00220-016-2609-8

doi:10.1007/s00220-016-2609-8 2016

[2] [1]

Estimating mutual information via kolmogoro v distance,

Z. Zhang, “Estimating mutual information via kolmogoro v distance,” IEEE Transactions on Information Theory , vol. 53, no. 9, pp. 3280– 3282, Sep. 2007

work page 2007

[3] [2]

The interplay between entropy and v ariational distance,

S. Ho and R. W. Y eung, “The interplay between entropy and v ariational distance,” IEEE Transactions on Information Theory , vol. 56, no. 12, pp. 5906–5929, Dec 2010

work page 2010

[4] [3]

Entropy bounds for discrete random variables via maximal coupling,

I. Sason, “Entropy bounds for discrete random variables via maximal coupling,” IEEE Transactions on Information Theory , vol. 59, no. 11, pp. 7118–7131, Nov 2013

work page 2013

[5] [4]

A continuity property of the entropy density for spin lattice systems,

M. Fannes, “A continuity property of the entropy density for spin lattice systems,” Comm. Math. Phys. , vol. 31, no. 4, pp. 291–294,

work page

[6] [5]

A sharp continuity estimate for the v on neumann entropy,

K. M. R. Audenaert, “A sharp continuity estimate for the v on neumann entropy,” Journal of Physics A: Mathematical and Theoretical , vol. 40, no. 28, pp. 8127–8136, jun 2007. [Online]. Availabl e: https://doi.org/10.1088%2F1751-8113%2F40%2F28%2Fs18

work page 2007

[7] [6]

Maximum and minimum entropy st ates yielding local continuity bounds,

E. P . Hanson and N. Datta, “Maximum and minimum entropy st ates yielding local continuity bounds,” Journal of Mathematical Physics , vol. 59, no. 4, p. 042204, 2018. [Online]. Available: https://doi.org/10.1063/1.5000120

work page doi:10.1063/1.5000120 2018

[8] [7]

Entropy and total variation distance (answ er),

I. Pinelis, “Entropy and total variation distance (answ er),” MathOverﬂow, visited on 2019-08-03. [Online]. Avail able: https://mathoverﬂow.net/questions/310689/entropy-an d-total-variation-distance

work page 2019