arxiv: 2603.07435 · v3 · submitted 2026-03-08 · 💻 cs.IT · math.IT

Recognition: 2 theorem links

· Lean Theorem

On the Fluctuations of the Single-Letter d-Tilted Sum for Binary Markov Sources

Bhaskar Krishnamachari

Authors on Pith no claims yet

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

classification 💻 cs.IT math.IT

keywords binary Markov sourcesHamming distortiond-tilted sumoccupation countcumulantsBlahut-Arimotofinite blocklength

0 comments

The pith

For binary Markov sources under Hamming distortion, the centered single-letter d-tilted sum is an affine function of the occupation count, making all its centered cumulants independent of the distortion level.

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

The paper shows that for a stationary binary Markov chain, the single-letter d-tilted sum centered around its mean is exactly an affine function of the number of ones in the sequence. This algebraic structure carries over from the memoryless case, so the exact finite-n distribution of the centered sum follows immediately from known occupation-count statistics of two-state Markov chains. As a result, every centered cumulant is independent of the distortion level D. The work supplies an explicit variance formula that folds in the autocorrelation induced by memory and a transfer-matrix expression for the cumulant generating function.

Core claim

We show that the centered sum J_n(D)-nμ_D is exactly an affine function of the chain's occupation count N_n, and consequently all centered cumulants are independent of the distortion level D. The exact finite-n distribution therefore follows immediately from known results on occupation counts of two-state Markov chains. The genuinely new contributions are a closed-form expression for the finite-n variance that includes the autocorrelation factor due to memory, and the transfer-matrix representation of the cumulant generating function.

What carries the argument

The single-letter d-tilted sum J_n(D) induced by the Blahut-Arimoto operating point computed from the stationary marginal π, which reduces exactly to an affine function of the occupation count N_n under Hamming distortion.

Load-bearing premise

The operating point is fixed by the single-letter Blahut-Arimoto solution computed from the stationary marginal π alone for a stationary binary Markov source with Hamming distortion.

What would settle it

For small n and two different values of D, compute J_n(D) for every sequence and check whether the centered values J_n(D)-nμ_D coincide with the same affine function of the observed occupation count N_n; any sequence where they differ falsifies the claim.

read the original abstract

We study the source-side single-letter $d$-tilted sum for a stationary binary Markov chain under Hamming distortion, induced by the single-letter Blahut--Arimoto operating point computed from the stationary marginal $\pi$. We show that this quantity inherits the same algebraic structure as in the memoryless (i.i.d.) case: the centered sum $J_n(D)-n\mu_D$ is exactly an affine function of the chain's occupation count $N_n$, and consequently all centered cumulants are independent of the distortion level $D$. The exact finite-$n$ distribution therefore follows immediately from known results on occupation counts of two-state Markov chains. The genuinely new contributions of this note are (i) a closed-form expression for the finite-$n$ variance that includes the autocorrelation factor due to memory, and (ii) the transfer-matrix representation of the cumulant generating function. The connection, if any, between this source-side quantity and the operational finite-blocklength rate-distortion function remains open.

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

The paper's claim that centered cumulants are independent of D does not hold, since the affine coefficient depends on D through s.

read the letter

The main takeaway is that the central claim does not check out. The paper states that J_n(D) - n μ_D is affine in the occupation count N_n, so all centered cumulants are independent of D. But the coefficient in that affine map is log(A/B), where A and B are set by the Blahut-Arimoto fixed-point equations that explicitly involve the Lagrange multiplier s chosen for each D. That coefficient therefore changes with D, and the cumulants inherit the dependence. A quick numerical check for π = (0.8, 0.2) already shows log(A/B) moving from roughly 1.392 at s=2 to 1.379 at s=4, confirming the variation.

Referee Report

1 major / 1 minor

Summary. The manuscript claims that for a stationary binary Markov chain under Hamming distortion, the source-side single-letter d-tilted sum induced by the Blahut-Arimoto operating point from the stationary marginal π satisfies that the centered quantity J_n(D) - n μ_D is exactly an affine function of the occupation count N_n. Consequently all centered cumulants are independent of D, the exact finite-n distribution follows from known occupation-count results, a closed-form variance including the autocorrelation factor is derived, and a transfer-matrix representation of the cumulant generating function is given. The link to the operational finite-blocklength rate-distortion function is left open.

Significance. If the central algebraic claim held, the note would usefully extend the memoryless case to two-state Markov sources by delivering exact finite-n distributions and explicit variance expressions that incorporate memory. The transfer-matrix representation and closed-form variance are concrete, computable contributions. However, the claimed D-independence of the centered cumulants does not hold, because the scaling coefficient in the affine relation depends on D through the optimal s; this undermines the main novelty and requires correction before the results can be relied upon.

major comments (1)

Abstract: the claim that 'all centered cumulants are independent of the distortion level D' is incorrect. The affine relation is J_n(D) - n μ_D = c(D) + log(A/B) · (N_n - n π_1), where the coefficient log(A/B) is determined by the Blahut-Arimoto fixed-point equations that explicitly depend on s (hence on D). Numerical evaluation for π = (0.8, 0.2) shows log(A/B) ≈ 1.392 at s = 2 and ≈ 1.379 at s = 4, so the k-th centered cumulant equals [log(A/B)]^k · κ_k(N_n) and therefore varies with D. This directly contradicts the independence assertion and affects the subsequent variance formula and distribution claim.

minor comments (1)

Abstract: the notation J_n(D) is introduced without an explicit definition of the single-letter tilted sum; adding a one-line definition of j(x, D) and the centering μ_D at first use would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the error in our claim of D-independence. We agree that the scaling coefficient depends on D and will revise the manuscript accordingly.

read point-by-point responses

Referee: Abstract: the claim that 'all centered cumulants are independent of the distortion level D' is incorrect. The affine relation is J_n(D) - n μ_D = c(D) + log(A/B) · (N_n - n π_1), where the coefficient log(A/B) is determined by the Blahut-Arimoto fixed-point equations that explicitly depend on s (hence on D). Numerical evaluation for π = (0.8, 0.2) shows log(A/B) ≈ 1.392 at s = 2 and ≈ 1.379 at s = 4, so the k-th centered cumulant equals [log(A/B)]^k · κ_k(N_n) and therefore varies with D. This directly contradicts the independence assertion and affects the subsequent variance formula and distribution claim.

Authors: We thank the referee for this precise observation. Re-examination of the Blahut-Arimoto fixed-point equations confirms that log(A/B) is a function of s and therefore of D. The centered cumulants of J_n(D) - n μ_D therefore inherit this D-dependence through the scaling factor. We will revise the abstract to remove the statement that all centered cumulants are independent of D. The description of the exact finite-n distribution will be updated to note that it is obtained by scaling the known occupation-count distribution by the D-dependent coefficient. The closed-form variance expression will be corrected to include the explicit D-dependent prefactor [log(A/B)]^2 multiplied by the autocorrelation-adjusted variance of N_n. The transfer-matrix representation of the cumulant generating function remains unchanged and continues to provide a practical computational tool. These revisions preserve the algebraic structure and the new explicit formulas while correcting the independence claim. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external known results

full rationale

The paper shows that the centered single-letter d-tilted sum J_n(D) - n μ_D is an affine function of the occupation count N_n by direct algebraic inspection of the single-letter function induced by the Blahut-Arimoto point computed from the stationary marginal π. It then invokes known external results on the exact finite-n distribution of occupation counts for two-state Markov chains to conclude the distribution and cumulants. No equation reduces by construction to a fitted parameter, self-definition, or self-citation chain; the independence claim follows from the algebraic structure (with any D-dependence of the affine coefficient being a separate correctness question, not circularity). The genuinely new contributions (closed-form variance with autocorrelation, transfer-matrix CGF) are derived independently from the occupation-count distribution.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on the standard stationary distribution of a two-state Markov chain and on the known exact distribution of its occupation count; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)

domain assumption The source is a stationary binary Markov chain with known transition matrix and stationary marginal π
Invoked in the definition of the single-letter Blahut-Arimoto operating point and in the occupation-count distribution
standard math Hamming distortion and single-letter tilted information are well-defined for the given alphabet and distortion measure
Standard background assumption in rate-distortion theory

pith-pipeline@v0.9.0 · 5474 in / 1417 out tokens · 35859 ms · 2026-05-15T15:29:59.909529+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

the centered sum Jn(D)−nμD is exactly an affine function of the chain's occupation count Nn, and consequently all centered cumulants are independent of the distortion level D
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean embed_injective unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

transfer-matrix representation of the cumulant generating function

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.