{"id":"4aee194c-e843-4145-926c-2d685a50289f","arxiv_id":"1909.00787","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For discrete random variables X,Y with total variation distance at most epsilon, the equivocation H(X|Y) satisfies the tight bound |H(X|Y)-H(X'|Y')| ≤ epsilon log(|X|-1) + h(epsilon).","lead":"The paper proves a sharp bound on how much conditional Shannon entropy can change when two joint distributions are within total variation distance epsilon: the difference is at most epsilon log(|X|-1)+h(epsilon), and examples show this is best possible. The result gives a size-independent continuity statement for equivocation, useful for entropy estimation and rate approximation in information theory.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the finite-|Y| restriction is explicit and the walking/stochastic-map proof checks out; only a novelty clarification remains.","rationale":"The reader's weakest assumption, finite support of Y, is real but does not undermine the stated theorem because the theorem explicitly restricts to finitely supported random variables and the proof requires |Y| finite only for the averaging map E. I checked the two delicate steps: the walking step preserves the difference of equivocations (in the empty-branch case only q is moved while q1-p1<0, so TV is preserved and H(X|Y) is unchanged), and E is a convex combination of Y-permutations, so H(X|Y) does not decrease while TV does not increase. The tightness construction evaluates to the claimed RHS. Thus I find no correctness flaw. The reader's conditional concern about novelty remains an editorial question, not a load-bearing mathematical objection, so the verdict should stay as the reader set it.","tokens_in":5569,"tokens_out":31827,"duration_ms":309058,"concrete_test":"Exhaustively enumerate all pairs of distributions on |X|=3, |Y|=2 over a coarse probability grid (e.g., step 0.01) and check whether |H(X|Y)-H(X'|Y')| ≤ ε log 2 + h(ε) with ε=TV; any violation would invalidate the theorem. As a positive control, confirm the construction in Eq. (21)-(22) saturates the bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. The claimed inequality and tightness construction are internally consistent. In the I_j-empty branch of the walking step, only q is transferred while q1-p1<0, so total variation is preserved and H(X|Y) is unchanged while H(X'|Y') decreases; once q1-p1 reaches zero, the nonempty-branch argument applies. The stochastic map E in Eq. (18) is a convex combination of Y-permutations in S_{X|Y}, so concavity gives H(Eν) ≥ H(ν), and TV does not increase. The final reduction to the unconditional entropy bound is valid. The finite-support assumption on Y is explicitly part of the theorem statement and is flagged in the concluding remarks; the infinite-alphabet case is an open problem, not a defect in the central claim. The only open question is novelty relative to Winter's quantum bound, which does not affect correctness.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":5721,"tokens_out":30683,"duration_ms":258081,"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.","major_comments":[],"minor_comments":[{"comment":"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":"Section I"},{"comment":"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":"Section II-B"},{"comment":"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":"Section II-B, I_j empty case"},{"comment":"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.","section":"Section II-C"},{"comment":"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.","section":"Throughout"}],"recommendation":"minor_revision","confidential_remarks":"The mathematical result and proof appear sound to me. The only substantive issue is the positioning with respect to Winter's quantum conditional-entropy bound and the broader literature; I would ask the authors to state clearly what is new relative to [8] and any earlier classical results (e.g., [1]-[3]). If the exact bound were already known, the contribution would become a proof exposition, so the editor may wish to verify novelty. This does not affect my confidence in the proof itself."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nOn 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.\n\nThe 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.\n\nWho 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.\n\nI would cite it and bring it to a reading group.","headline":"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.","tokens_in":629,"tokens_out":1472,"would_cite":true,"duration_ms":58966,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A17"],"pacs":[],"model":"deepseek-v4-flash","headline":"For finite alphabets, the conditional Shannon entropy changes by at most ε log(|X|-1)+h(ε) under total variation distance ε, and this bound is tight.","keywords":["conditional Shannon entropy","equivocation","uniform continuity bound","total variation distance","tight bound","G-majorization","Shannon entropy","majorization"],"falsifier":"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.","tokens_in":5398,"feed_emoji":"🎯","tokens_out":6428,"duration_ms":64420,"temperature":0.7,"pith_summary":"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.","feed_headline":"Tight bound pins down worst-case change in conditional entropy","feed_subtitle":"Within total variation ε, H(X|Y) shifts by at most ε log(|X|-1)+h(ε).","key_machinery":"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(ε).","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the unconditional entropy-variational distance bound invoked after the reduction to product distributions.","marker":"[1]"},{"why":"Provides the 'walking' technique of transferring probability mass without increasing total variation distance while keeping the entropy difference nondecreasing.","marker":"[7]"},{"why":"Supplies the theory of majorization used to compare concentration of probability vectors and justify entropy comparisons.","marker":"[16]"},{"why":"Formalizes G-majorization, the group-induced preorder used to exploit the S_{X|Y} invariance of equivocation.","marker":"[17]"}],"fun_headline_variants":["Tight bound reveals worst-case drift in conditional entropy","Exact max change in equivocation under total variation","No tighter bound exists: entropy shift limit proven","Conditional entropy's max jump under TV distance is fixed","Optimal uniform bound on equivocation shift"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Tight bound reveals worst-case drift in conditional entropy","Exact max change in equivocation under total variation","No tighter bound exists: entropy shift limit proven","Conditional entropy's max jump under TV distance is fixed","Optimal uniform bound on equivocation shift"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000587,"raw_usage":{"total_tokens":2639,"prompt_tokens":711,"completion_tokens":1928,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":327,"completion_tokens_details":{"reasoning_tokens":1854}},"tokens_in":327,"tokens_out":1928,"duration_ms":14181,"temperature":1.0,"reasoning_tokens":1854,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:37:43.355899+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Estimating mutual information via kolmogoro v distance,","cited_arxiv_id":null,"evidence_quote":"Supplies the unconditional entropy-variational distance bound invoked after the reduction to product distributions."},{"cited_title":"Entropy and total variation distance (answ er),","cited_arxiv_id":null,"evidence_quote":"Provides the 'walking' technique of transferring probability mass without increasing total variation distance while keeping the entropy difference nondecreasing."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the theory of majorization used to compare concentration of probability vectors and justify entropy comparisons."}],"review_version":1}