Pith. sign in

REVIEW 2 major objections 4 minor 51 references

The Sample Complexity of Lossless Data Compression

T0 review · 2 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

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

Pith's one-line read This paper introduces the sample complexity of lossless compression and proves that it is set by Rényi entropy of order 1/2, not Shannon entropy.

desk verdict Useful finite-blocklength compression paper: sample complexity scales with D_{1/2}, not entropy; written lower-bound proof has a fixable gap. read the letter →

arxiv 2601.06688 v5 pith:LGBLR5XL submitted 2026-01-10 cs.IT math.ITmath.STstat.TH

Terence Viaud , Ioannis Kontoyiannis This is my paper · ORCID
classification cs.ITmath.ITmath.STstat.TH MSC 94A2994A1762B1062F03
keywords samplecomplexitylosslessdatacompressionRényientropydivergencehypothesistestingidentityMarkovsourcesuniversal
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

The paper defines the sample complexity of lossless data compression: the shortest blocklength at which some compressor can simultaneously satisfy a rate constraint and an excess-rate probability bound. Its central result is that, for memoryless sources, this quantity is proportional to log(1/ε) divided by the Rényi divergence of order 1/2 between the source distribution and the uniform distribution — equivalently, the Rényi entropy of order 1/2 — rather than the Shannon entropy that governs asymptotic rates. The proof route passes through fixed-length codes and a total-variation identity that identifies the compression problem with a simple hypothesis test between the source and the uniform distribution. The same program is carried out for Markov sources, where the Rényi divergence rate of order 1/2 plays the role, and for universal compression over families of memoryless sources, where the sample complexity is characterized by the family's minimum order-1/2 Rényi divergence from uniform. A sympathetic reader would care because this gives explicit, non-asymptotic blocklength guarantees with reasonable constants, directly usable in practice.

What carries the argument

The workhorse is the Rényi divergence of order 1/2, D_{1/2}(P∥Q) = −2 log Σ_x √(P(x)Q(x)), which is quadratically related to Hellinger distance and tensorizes under products: D_{1/2}(P^n∥Q^n) = nD_{1/2}(P∥Q). Proposition 3.1, a total-variation identity, identifies the fixed-length compression sample complexity with the hypothesis-testing risk between P^n and U^n, reducing compression to testing. Proposition 2.2 sandwiches total variation distance between 2^{−D_{1/2}−1} and 2^{−D_{1/2}/2}, giving the explicit log(1/ε)/D_{1/2} rates. For Markov sources, the Perron–Frobenius theorem applied to the square root of the entrywise product of transition matrices yields the Rényi divergence rate. For

What would settle it

Numerically evaluate n*(X,ε) exactly for a binary memoryless source by exhaustive search over all prefix-free codes for n up to, say, 30 and ε=0.05; the paper's Theorem 4.3 says the crossing point satisfies explicit lower and upper bounds involving D_{1/2}, so if the observed n* falls outside those bounds — or systematically tracks log(1/ε)/H(P) instead — the central claim fails.

Watch

Extended reading notes

Core claim

For a memoryless source X with marginal P on an alphabet of size m, the paper proves that the variable-length sample complexity n*(X,ε) — the smallest blocklength at which some lossless compressor can keep both the excess-rate probability and the rate term 2^{nR}/|A|^n no larger than ε — satisfies (log(1/ε)−3)/D_{1/2}(P∥U) ≤ n* ≤ 2 log(1/ε)/D_{1/2}(P∥U) + 1 for every ε∈(0,1). The same order holds for prefix-free and fixed-length codes. Since D_{1/2}(P∥U) = log|A| − H_{1/2}(P), the quantity that determines sample complexity is the Rényi entropy of order 1/2, not the Shannon entropy. The paper extends this to Markov sources, where the Rényi divergence rate D_{1/2}(X∥U) replaces the per-letter

Load-bearing premise

The central memoryless bound is self-contained, but the universal upper bound borrows collision-statistic variance identities and an amplification lemma from the distribution-testing literature; if those results fail uniformly over all P with D_{1/2}(P∥U) ≥ δ, the √m/δ blocklength guarantee collapses.

Editorial extensions

If this is right

  • For any known memoryless source, a practitioner can compute the blocklength needed for a guaranteed (ε, rate) performance directly from D_{1/2}(P∥U), up to universal constants; the paper supplies the constants.
  • The same characterization holds for fixed-length and prefix-free codes, and moving between the three code classes only costs constant factors, so the choice of code class does not change the sample-complexity order.
  • For Markov sources, the relevant quantity is the Rényi divergence rate of order 1/2; for symmetric chains the bounds depend only on that rate and log m, not on spectral gaps or other mixing parameters.
  • For universal compression of D_{1/2} families, the blocklength scales as √m/δ in the moderate-confidence regime, and the minimal separation from uniform behaves as √m/n — a direct analogue of identity-testing separation rates.
  • Classical asymptotic expansions for lossless compression describe how n* behaves at different ε scales, but the finite-blocklength pivot is always D_{1/2}, not the entropy rate.

Reading between the lines

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

  • If the D_{1/2} characterization is taken as the canonical finite-blocklength quantity, the classical Gaussian and large-deviation refinements can be re-derived as different ε-regimes of a single n*(X,ε) curve; checking this numerically for small alphabets would clarify the boundary between asymptotic regimes.
  • The √m gap between the general universal upper and lower bounds suggests that collision statistics may not be optimal for all D_{1/2} families; a sharper statistic or a modified separation measure might close the gap, with a concrete target of n* ≍ √m log(1/ε)/δ in all regimes.
  • Because the Markov bounds in Theorem 5.2 depend on the initial distribution and the Perron eigenvector, an adaptive compressor that chooses blocklength based on an estimate of the mixing structure might outperform the fixed bound; this is a testable extension.
  • The framework's definition couples rate and error probability through the ratio 2^{nR}/|A|^n; adopting a different scaling would change all bounds, so the useful next step is to verify that the same order-1/2 Rényi characterization survives under an additive or absolute-rate constraint.
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.

Referee Report

2 major / 4 minor

Summary. The paper introduces a non-asymptotic framework for lossless data compression, defining the sample complexity n*(X,ε) as the smallest blocklength at which a variable-length compressor can achieve both an excess-rate probability at most ε and a rate constraint 2^{nR}/|A|^n ≤ ε. For memoryless sources, the main result (Theorem 4.3) states that n*(X,ε) is of order log(1/ε)/D_{1/2}(P∥U), where D_{1/2} is the Rényi divergence of order 1/2, rather than depending on Shannon entropy. The paper also proves analogous results for fixed-length and prefix-free codes, extends the characterization to Markov sources using Rényi divergence rates, and develops universal compression bounds for families of memoryless sources separated from uniformity by D_{1/2}, connecting the problem to identity testing. The proofs are mostly self-contained for the memoryless case, with external bounds from distribution testing appropriately credited.

Significance. If the results hold, the paper gives a clean, operational characterization of finite-blocklength compression in terms of Rényi entropy of order 1/2, with explicit constants and a clear connection to hypothesis testing. The universal bounds and separation-rate interpretation are novel and potentially influential. A notable strength is that the core memoryless arguments are self-contained and use standard tools (Le Cam's lemma, tensorization) with external results correctly cited. However, the lower-bound proofs in the central theorems rely on an inequality that Proposition 2.2 as stated does not provide; the necessary inequality is proved later in Appendix A but not invoked. This gap is localized and readily repairable, but it affects the converse half of the main characterization and the corresponding Markov lower bounds.

major comments (2)
  1. [Sec. 3.2 (proof of Theorem 3.2); App. A, Eq. (44)] The lower half of Theorem 3.2 is not justified by the stated Proposition 2.2. The proof uses 'the lower bound in Proposition 2.2' to conclude 2^{-nD}-1 ≤ ε(n), but for D>0 this left inequality is vacuous (the LHS is negative), so it cannot yield a lower bound on N_fl(X,ε). The needed inequality is the stronger ε(n) ≥ 1 - sqrt(1 - 2^{-nD}) ≥ (1/2)2^{-nD}, which is proved later as Eq. (44) but not stated in Proposition 2.2. Since Theorem 4.3's lower bound inherits this step, the converse part of the main characterization (6) is not proved as written. The fix is straightforward: state the sharpened lower bound in Proposition 2.2 or cite Eq. (44) in the proof.
  2. [Sec. 5 (Theorems 5.2 and 5.3)] The same insufficient lower bound is used in the Markov results. In the proof of Theorem 5.2, after bounding D_{1/2}(P^n∥U^n), the line ε(n) ≥ 2^{-D_{1/2}(P^n∥U^n)}-1 is again vacuous for positive divergence; the subsequent lower bound on N_fl requires the sharper inequality from Eq. (44). The same issue appears in Theorem 5.3. Both lower bounds are repairable by following the memoryless fix, but as written they are not established.
minor comments (4)
  1. [Sec. 1.3, after Eq. (5)] The sentence 'where in the infimum in (5) is over all variable-length codes' is ungrammatical; it should read 'where the infimum in (5) is over all variable-length codes...'.
  2. [Appendix B, Eq. (45)] The notation '(loge 2)' is ambiguous. It should be written as \(\ln 2\) or \(\log_2 e\) to avoid confusion between the natural and base-2 logarithms.
  3. [Theorem 6.4] The constants C1 and C2 are not explicit, although the proof in Appendix B yields a concrete value for C2 (on the order of 3600 after amplification). Stating explicit values would strengthen the non-asymptotic claim.
  4. [Sec. 5.2, proof of Theorem 5.3] The claim that τ1 ≥ 1/m follows from positivity of the Perron eigenvector v(1) is correct but worth a brief justification, since the reader must verify that the minimum occurs when v(1) is concentrated on a single coordinate.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the D_{1/2} sample-complexity bounds follow from self-contained TV/Hellinger inequalities and external testing bounds; self-citations are non-load-bearing background.

full rationale

I walked the derivation chain for Theorems 3.2, 4.1–4.3, 5.2, 5.3, 6.3, and 6.4. The memoryless result is not built from its conclusion: starting from the definition of N_fl, Le Cam's lemma identifies inf_C [P^n(C^c)+U^n(C)] = 1-||P^n-U^n||_TV (Proposition 3.1, proved in the paper), and Proposition 2.2 (proved in Appendix A) plus tensorization give explicit two-sided bounds in terms of D_{1/2}. The lower-bound direction of Theorem 3.2 uses the stated upper bound 1-TV ≤ 2^{-D/2}, not the vacuous lower half of Proposition 2.2; the needed lower estimate on 1-TV is exactly Eq. (44) in Appendix A, so the written proof has a small gap, but it is a correctness/presentation issue, not a circular one. The variable-length and prefix-free results are obtained from fixed-length results by constructive coding arguments (Theorems 4.1, 4.2), with the relation (3) imported from [30]; that is an external, peer-reviewed theorem, not the paper's own conclusion, and it is not what makes D_{1/2} appear. Markov results use the Rényi-divergence formula of Proposition 5.1 imported from [38] (not the authors) and Perron-Frobenius arguments; universal results use independent collision-statistic identities from [9] and identity-testing bounds from [18]. No fitted parameter is renamed as a prediction, no ansatz is smuggled in via a self-citation, and no claimed 'prediction' reduces to its own input by construction. The only manuscript passages I would flag are the imprecisely stated inference in the Theorem 3.2 proof and the transfer statements to earlier results in Sections 1.5 and 3.2, Remark 2; these are support/acknowledgment issues, not circularity. Score 0.

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

No free parameters are fitted: the constants in Theorems 4.3 and 6.4 are explicit or universal. The axioms are standard information-theory and matrix-analysis results, or known distribution-testing bounds imported with citation. The only new object is the sample-complexity functional n*(X,ε), which is a definition rather than a postulated entity.

assumptions (9)
  • standard math Tensorization of Rényi divergence of order 1/2: D_{1/2}(P^n∥Q^n) = n D_{1/2}(P∥Q) for product measures
    Invoked in proofs of Theorems 3.2 and 4.3; cited to van Erven and Harremoës [44] as Proposition 2.1.
  • standard math Le Cam's lemma representation: N_fl(X,ε) = inf{n : 1 − ∥P^n − U^n∥_TV ≤ ε}
    Proposition 3.1, proved in the paper; used as the bridge between compression and hypothesis testing throughout.
  • standard math Rényi divergence / total variation inequalities: 2^{-D_{1/2}} − 1 ≤ 1 − TV ≤ 2^{-D_{1/2}/2}
    Proposition 2.2, proved in Appendix A; used to convert TV bounds into D_{1/2} bounds in all main theorems.
  • standard math Perron-Frobenius theorem for irreducible nonnegative matrices
    Used in Theorem 5.2 to obtain Perron eigenvalue and positive right eigenvector of the matrix sqrt(P⊙Q); cited to Seneta [39].
  • standard math Rényi divergence formula for Markov chains: D_{1/2}(P^n∥Q^n) = −2 log([μ⊙ν]^T (sqrt(P⊙Q))^{n−1} 1)
    Proposition 5.1, imported from Rached, Alajaji, and Campbell [38]; load-bearing for both Markov theorems.
  • standard math Sample-optimal identity testing bound for total-variation families (Theorem 6.3)
    Imported from Diakonikolas et al. [18, Theorem 2]; gives n_fl(Q_TV,δ,ε) ≍ (log(1/ε)+√(m log(1/ε)))/δ².
  • standard math Collision-statistic variance formulas and amplification lemma from Canonne [9]
    Appendix B uses [9, Eq (2.9), (2.11)] and [9, Lemma 1.1] to prove the upper bound in Theorem 6.4.
  • standard math Existence of an optimal variable-length compressor independent of the rate R
    Used in the lower-bound proof of Theorem 4.1; cited to Kontoyiannis and Verdú [30, Theorem 1].
  • domain assumption Finite alphabet, arbitrary source processes; Markov sources are irreducible; symmetric Markov sources start from the uniform distribution
    The theorems are restricted to these classes. This is stated in Sections 2 and 5 and is not argued to hold more generally.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Sample Complexity of Lossless Data Compression." pith.science (2026). https://pith.science/paper/LGBLR5XL

@misc{pith2026260106688,
  author       = {Pith},
  title        = {Pith review of: The Sample Complexity of Lossless Data Compression},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LGBLR5XL}},
  note         = {Machine review of arXiv:2601.06688}
}
abstract

A new framework is introduced for examining and evaluating the fundamental limits of lossless data compression, that emphasizes genuinely non-asymptotic results. The {\em sample complexity} of compressing a given source is defined as the smallest blocklength at which it is possible to compress that source at a specifically constrained rate and to within a specified excess-rate probability. This formulation parallels corresponding developments in statistics and computer science, and it facilitates the use of existing results on the sample complexity of various hypothesis testing problems. For arbitrary sources, the sample complexity of general variable-length compressors is shown to be tightly coupled with the sample complexity of prefix-free codes and fixed-length codes. For memoryless sources, it is shown that the sample complexity is characterized not by the source entropy, but by its R\'{e}nyi entropy of order~$1/2$. Nonasymptotic bounds on the sample complexity are obtained, with explicit constants. Generalizations to Markov sources are established, showing that the sample complexity is determined by the source's R\'{e}nyi entropy rate of order~$1/2$. Finally, bounds on the sample complexity of universal data compression are developed for families of memoryless sources. There, the sample complexity is characterized by the minimum R\'{e}nyi divergence of order~$1/2$ between elements of the family and the uniform distribution. The connection of this problem with identity testing and with the associated separation rates is explored and discussed.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 2 linked inside Pith

  1. [1]

    Acharya, C.L

    J. Acharya, C.L. Canonne, Y. Liu, Z. Sun, and H. Tyagi. Interactive inference under information constraints. In2021 IEEE International Symposium on Information Theory (ISIT), pages 326–331, Melbourne, Australia, July 2021

    2021

  2. [2]

    Acharya, C.L

    J. Acharya, C.L. Canonne, and H. Tyagi. Inference under information constraints II: Com- munication constraints and shared randomness.IEEE Trans. Inform. Theory, 66(12):7856– 7877, October 2020

    2020

  3. [3]

    Acharya, C

    J. Acharya, C. Daskalakis, and G. Kamath. Optimal testing for properties of distributions. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors,Advances in Neural Information Processing Systems, volume 28, Montréal, Quebec, December 2015

    2015

  4. [4]

    Altuğ, A.B

    Y. Altuğ, A.B. Wagner, and I. Kontoyiannis. Lossless compression with moderate error probability. In2013 IEEE International Symposium on Information Theory (ISIT), pages 1744–1748, Istanbul, Turkey, July 2013

    2013

  5. [5]

    Bar-Yossef.The complexity of massive data set computations

    Z. Bar-Yossef.The complexity of massive data set computations. PhD thesis, Department of Computer Science, University of California, Berkeley, Berkeley, CA, 2002

    2002

  6. [6]

    R.E. Blahut. Hypothesis testing and information theory.IEEE Trans. Inform. Theory, 20(4):405–417, July 1974

    1974

  7. [7]

    Canonne.A survey on distribution testing: Your data is big

    C.L. Canonne.A survey on distribution testing: Your data is big. But is it blue?Number 9 in Graduate Surveys. Theory of Computing Library, 2020

    2020

  8. [8]

    C.L. Canonne. A short note on an inequality between KL and TV.arXiv e-prints, 2202.07198 [math.PR], February 2022

    arXiv 2022

Show all 51 references
  1. [9]

    C.L. Canonne. Topics and techniques in distribution testing: A biased but representative sample.Foundations and Trends in Communications and Information Theory, 19(6):1032– 1198, November 2022

    2022

  2. [10]

    S.O. Chan, Q. Ding, and S.H. Li. Learning and testing irreducible Markov chains via thek- cover time. In V. Feldman, K. Ligett, and S. Sabato, editors,32nd International Conference on Algorithmic Learning Theory, volume 132 ofProceedings of Machine Learning Research, pages 458...

    2021

  3. [11]

    Cherapanamjeri and P.L

    Y. Cherapanamjeri and P.L. Bartlett. Testing symmetric Markov chains without hitting. In A. Beygelzimer and D. Hsu, editors,32nd Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 758–785, June 2019

    2019

  4. [12]

    Cover and J.A

    T.M. Cover and J.A. Thomas.Elements of information theory. John Wiley & Sons, New York, NY, second edition, 2006

    2006

  5. [13]

    Csiszár and J

    I. Csiszár and J. Körner.Information theory: Coding theorems for discrete memoryless systems. Academic Press, New York, NY, 1981

    1981

  6. [14]

    Csiszár and G

    I. Csiszár and G. Longo. On the error exponent for source coding and for testing simple statistical hypotheses.Studia Sci. Math. Hungar., 6:181–191, 1971

    1971

  7. [15]

    Csiszár and P

    I. Csiszár and P. Shields. Information theory and statistics: A tutorial.Foundations and Trends in Communications and Information Theory, 1(4):417–528, December 2004. 25

    2004

  8. [16]

    Daskalakis and N

    C. Daskalakis and N. Dikkala, N.and Gravin. Testing symmetric Markov chains from a single trajectory. In S. Bubeck, V. Perchet, and P. Rigollet, editors,31st Conference On Learning Theory, volume 75 ofProceedings of Machine Learning Research, pages 385–409, July 2018

    2018

  9. [17]

    Diakonikolas, T

    I. Diakonikolas, T. Gouleakis, D.M. Kane, and S. Rao. Communication and memory efficient testing of discrete distributions. In A. Beygelzimer and D. Hsu, editors,32nd Conference on Learning Theory (COLT), volume 99 ofProceedings of Machine Learning Research, pages 1070–1106, June 2019

    2019

  10. [18]

    Diakonikolas, T

    I. Diakonikolas, T. Gouleakis, J. Peebles, and E. Price. Sample-optimal identity testing with high probability. In I. Chatzigiannakis, C. Kaklamanis, D. Marx, and D. Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 1...

    2018

  11. [19]

    Diakonikolas, T

    I. Diakonikolas, T. Gouleakis, J. Peebles, and E. Price. Collision-based testers are optimal for uniformity and closeness.Chic. J. Theor. Comput. Sci, 25:1–21, 2019

    2019

  12. [20]

    Diakonikolas, D.M

    I. Diakonikolas, D.M. Kane, and V. Nikishkin. Testing identity of structured distributions. InProceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1841–1854. SIAM, 2015

    2015

  13. [21]

    Dobrushin

    R.L. Dobrushin. Asymptotic bounds of the probability of error for the transmission of messages over a discrete memoryless channel with a symmetric transition probability matrix. Teor. Veroyatnost. i Primenen, 7:283–311, 1962

    1962

  14. [22]

    J. Gao, S. Chen, Y. Wu, L. Liu, G. Caire, H.V. Poor, and W. Zhang. Finite-blocklength information theory.arXiv e-prints,2504.07743 [cs.IT], April 2025

    2025

  15. [23]

    Goldreich and D

    O. Goldreich and D. Ron. On testing expansion in bounded-degree graphs. In O. Goldre- ich, editor,Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, pages 68–75. Springer, Berlin, Heidelberg, 2011

    2011

  16. [24]

    Yu.I. Ingster. Asymptotically minimax testing of nonparametric hypotheses on the density of the distribution of an independent sample.Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov.(LOMI), 136:74–96, 1984

    1984

  17. [25]

    Yu.I. Ingster. Asymptotically optimal tests for composite finite-parametric hypotheses. Teoriya Veroyatnostei i ee Primeneniya, 30(2):289–308, 1985

    1985

  18. [26]

    Ingster and I.A

    Yu.I. Ingster and I.A. Suslina.Nonparametric goodness-of-fit testing under Gaussian models, volume 169 ofLecture Notes in Statistics. Springer, New York, NY, 2002

    2002

  19. [27]

    Jelinek.Probabilistic information theory: Discrete and memoryless models

    F.K. Jelinek.Probabilistic information theory: Discrete and memoryless models. McGraw- Hill, New York, NY, 1968

    1968

  20. [28]

    Kontoyiannis

    I. Kontoyiannis. Second-order noiseless source coding theorems.IEEE Trans. Inform. The- ory, 43(4):1339–1341, July 1997

    1997

  21. [29]

    Kontoyiannis and S

    I. Kontoyiannis and S. Verdú. Optimal lossless compression: Source varentropy and dis- persion. In2013 IEEE International Symposium on Information Theory (ISIT), pages 1739–1743, Istanbul, Turkey, July 2013. 26

    2013

  22. [30]

    Kontoyiannis and S

    I. Kontoyiannis and S. Verdú. Optimal lossless data compression: Non-asymptotics and asymptotics.IEEE Trans. Inform. Theory, 60(2):777–795, February 2014

    2014

  23. [31]

    L. Le Cam. On the asymptotic theory of estimation and testing hypotheses. InProc. 3rd Berkeley Sympos. Math. Statist. and Probab., volume 3, pages 129–157, Berkeley, CA, 1956. University of California Press

    1956

  24. [32]

    L. Le Cam. Locally asymptotically normal families of distributions. Certain approximations to families of distributions and their use in the theory of estimation and testing hypotheses. Univ. California Publ. Statist.,Berkeley, CA, 3:37, 1960

    1960

  25. [33]

    Le Cam.Asymptotic methods in statistical decision theory

    L. Le Cam.Asymptotic methods in statistical decision theory. Springer-Verlag, New York, NY, 1986

    1986

  26. [34]

    McMillan

    B. McMillan. The basic theorems of information theory.Ann. Math. Statist., 24(2):196–219, June 1953

    1953

  27. [35]

    Neyman and E.S

    J. Neyman and E.S. Pearson. On the problem of the most efficient tests of statistical hypotheses.Philos. Trans. Roy. Soc. London A, 231(694-706):289–337, 1933

    1933

  28. [36]

    Paninski

    L. Paninski. A coincidence-based test for uniformity given very sparsely sampled discrete data.IEEE Trans. Inform. Theory, 54(10):4750–4755, October 2008

    2008

  29. [37]

    Pensia, V

    A. Pensia, V. Jog, and P.-L. Loh. The sample complexity of simple binary hypothesis testing. In37th Annual Conference on Learning Theory, volume 247 ofProceedings of Machine Learning Research, pages 4205–4206, 2024

    2024

  30. [38]

    Rached, F

    Z. Rached, F. Alajaji, and L. Lorne Campbell. Rényi’s divergence and entropy rates for finite alphabet Markov sources.IEEE Trans. Inform. Theory, 47(4):1553–1561, May 2001

    2001

  31. [39]

    Seneta.Non-negative matrices and Markov chains

    E. Seneta.Non-negative matrices and Markov chains. Springer, New York, NY, 1981

    1981

  32. [40]

    C.E. Shannon. A mathematical theory of communication.Bell System Tech. J., 27(3):379– 423, 623–656, 1948

    1948

  33. [41]

    Strassen

    V. Strassen. Asymptotische Abschätzungen in Shannons Informationstheorie. In3rd Prague Conf. Information Theory, Statist. Decision Functions, Random Processes (Liblice, 1962), pages 689–723. Publ. House Czech. Acad. Sci., Prague, 1964

    1962

  34. [42]

    Theocharous, L

    A. Theocharous, L. Gavalakis, and I. Kontoyiannis. Pragmatic lossless compression: Fun- damental limits and universality.arXiv e-prints,2501.10103 [cs.IT], November 2025

    2025

  35. [43]

    Valiant and P

    G. Valiant and P. Valiant. An automatic inequality prover and instance optimal identity testing. In2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 51–60, 2014

    2014

  36. [44]

    van Erven and P

    T. van Erven and P. Harremoës. Rényi divergence and Kullback-Leibler divergence.IEEE Trans. Inform. Theory, 60(7):3797–3820, July 2014

    2014

  37. [45]

    A. Wald. Statistical decision functions which minimize the maximum risk.Ann. of Math., 46(2):265–280, April 1945

    1945

  38. [46]

    Wald.Statistical decision functions

    A. Wald.Statistical decision functions. Wiley, New York, NY, 1950. 27

    1950

  39. [47]

    Wang and M.C.H

    Y. Wang and M.C.H. Choi. Information divergences of Markov chains and their applications. arXiv e-prints,2312.04863 [cs.IT], December 2023

    2023 arXiv

  40. [48]

    Wolfer and A

    G. Wolfer and A. Kontorovich. Minimax testing of identity to a reference ergodic Markov chain. In S. Chiappa and R. Calandra, editors,23rd International Conference on Artificial Intelligence and Statistics, volume 108 ofProceedings of Machine Learning Research, pages 191–201, ...

    2020

  41. [49]

    Wolfer and A

    G. Wolfer and A. Kontorovich. Statistical estimation of ergodic Markov chain kernel over discrete state space.Bernoulli, 27(1):532–553, February 2021

    2021

  42. [50]

    Yushkevich

    A.A. Yushkevich. On limit theorems connected with the concept of the entropy of Markov chains.Uspehi Mat. Nauk, 8:177–180, 1953. (Russian)

    1953

  43. [51]

    J. Ziv. Back from infinity: A constrained resources approach to information theory (Shannon Lecture).IEEE Information Theory Society Newsletter, 48(1):21–30, 1998. 28

    1998

Pith tools

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