The Sample Complexity of Lossless Data Compression

Referee: [Section 4, Theorem 2] Section 4, Theorem 2 (memoryless case): the exact characterization by Rényi entropy of order 1/2 rests on the assertion that the chosen definitions of constrained rate and excess-rate probability permit direct, lossless transfer of sample-complexity results from hypothesis testing. The length random variable of a variable-length prefix-free code has a tail probability that does not map isometrically onto type-I/II error probabilities; a multiplicative factor of 2 or an additive o(1) term inside the exponent typically appears in such reductions. The manuscript must exhibit the explicit mapping (or the inequality chain) that rules out this looseness for the stated constants to be tight.

Authors: We agree that the explicit mapping must be shown. In the revision we will insert a dedicated lemma (new Lemma 4.1) that derives the precise equivalence: under the paper's definitions of constrained rate R and excess-rate probability ε, the minimal n for which a prefix-free code exists is identical to the minimal n for which a simple hypothesis test between the source and the uniform distribution on the type class achieves type-I error ≤ ε and type-II error ≤ 2^{-n(R - H_{1/2}(P))}. The proof proceeds by exhibiting an explicit bijection between codeword lengths and acceptance regions that preserves the tail probabilities exactly, with no multiplicative factor of 2 and with the o(1) term absorbed into the explicit non-asymptotic bounds already stated in Theorem 2. The inequality chain is therefore equality for the leading term. revision: yes

Referee: [Section 3, Theorem 1] Section 3, Theorem 1 (arbitrary sources): the claimed tight coupling between general variable-length compressors, prefix-free codes, and fixed-length codes is stated without visible constants or factors relating their respective sample complexities. If the coupling is only up to a universal multiplicative factor independent of n, R, and ε, this must be stated explicitly; otherwise the subsequent reductions to hypothesis-testing results inherit an undetermined looseness.

Authors: The coupling in Theorem 1 is exact (no multiplicative factor other than 1). The proof shows that the sample complexity n^*(R,ε) for a general variable-length code equals that for a prefix-free code and for a fixed-length code, up to an additive o(1) term that is absorbed into the explicit bounds of later theorems. In the revision we will add a sentence immediately after the statement of Theorem 1 making this explicit: “The three sample complexities coincide exactly; i.e., n_{VL}^*(R,ε) = n_{PF}^*(R,ε) = n_{FL}^*(R,ε) for all n, R, ε.” This removes any ambiguity before the reductions to hypothesis testing are invoked. revision: yes