pith. sign in

arxiv: 2606.01218 · v1 · pith:4L6SLHOVnew · submitted 2026-05-31 · 💻 cs.IT · math.IT

Finite-Resolution Information from Collision Statistics

Alexander J. Gates This is my paper

Pith reviewed 2026-06-28 16:29 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords collision statisticsRényi entropyShannon entropymutual informationentropy estimationfinite-resolution informationinterpolation bounds
0
0 comments X

The pith

Low-order collision statistics approximate Shannon entropy with error controlled by the Rényi entropy path near order 1.

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

Collision statistics count how often independent samples coincide on the same state, directly yielding the integer-order Rényi entropies that serve as finite-resolution views of information. The paper derives interpolation-error bounds showing that the gap between these quantities and Shannon entropy or mutual information is governed by the shape of the Rényi path near order 1. It separates this fixed deterministic approximation error from statistical estimation error, proving that larger samples tighten the estimate of the collision-based target without closing the gap to the Shannon limit. The work further establishes that no finite collection of collision moments suffices to recover Shannon entropy in general and that higher orders weight the approximation toward high-probability events.

Core claim

Collision statistics provide a finite-resolution view of information by measuring how often a fixed number of independent samples fall on the same state. These directly countable quantities form the basis of integer-order Rényi entropies. Low-order Rényi entropies approximate Shannon entropy and mutual information, with interpolation-error bounds showing that approximation error is controlled by the shape of the Rényi entropy path near the Shannon point. Deterministic error is separated from finite-sample estimation error: for fixed collision order, increasing sample size improves estimation of the finite-resolution target but does not eliminate its deterministic difference from Shannon entr

What carries the argument

The Rényi entropy path as a function of order, with interpolation-error bounds near the Shannon point (order 1) that quantify the deterministic approximation error from finite collision moments.

If this is right

  • For any fixed collision order, larger samples reduce statistical estimation error around the finite-resolution target while leaving its deterministic offset from Shannon entropy unchanged.
  • Raising the collision order shrinks the deterministic approximation gap to Shannon entropy but increases sensitivity to high-probability events.
  • Shannon entropy and mutual information cannot be recovered exactly from any finite set of collision moments in general.
  • The approximation-estimation tradeoff can be tuned by choosing collision order, with numerical comparisons to plug-in and Miller-Madow estimators illustrating the resulting behavior.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Collision-based approximations may remain useful in streaming or memory-constrained settings where full histogram construction is infeasible, provided the target resolution matches the application.
  • The separation of deterministic and statistical errors suggests that standard bias-correction techniques cannot eliminate the gap shown by the interpolation bounds.
  • Choosing collision order according to whether rare or common events dominate the quantity of interest offers a practical design lever not available in direct Shannon estimators.

Load-bearing premise

The shape of the Rényi entropy path near order 1 controls the interpolation error in the derived approximation bounds.

What would settle it

A probability distribution in which Shannon entropy equals a fixed function of only finitely many collision probabilities would falsify the claim that finite collision moments do not generally identify Shannon entropy.

Figures

Figures reproduced from arXiv: 2606.01218 by Alexander J. Gates.

Figure 1
Figure 1. Figure 1: Population approximation error for the binary symmetric channel [PITH_FULL_IMAGE:figures/full_fig_p017_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Fixed-order sampling behavior for the binary symmetric channel with [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Collision order as a concentration filter. For each distribution, the state-level contribution to the order-k collision probability is normalized as w (k) i = p k i / ∑j p k j . The figure shows the effective number of contributing states, N (k) eff = 1/ ∑i (w (k) i ) 2 , as a function of collision order. For the uniform distribution, all states contribute equally and the effective number remains fixed at … view at source ↗
read the original abstract

Collision statistics provide a finite-resolution view of information by measuring how often a fixed number of independent samples fall on the same state. These directly countable quantities form the basis of integer-order R\'enyi entropies. Here, we use low-order R\'enyi entropies to approximate Shannon entropy and mutual information, while characterizing what is necessarily lost when only finitely many collision moments are used. We derive interpolation-error bounds showing that approximation error is controlled by the shape of the R\'enyi entropy path near the Shannon point. We also separate this deterministic error from finite-sample estimation error: for fixed collision order, increasing sample size improves estimation of the finite-resolution target but does not eliminate its deterministic difference from Shannon entropy or mutual information. Finally, we show that finite collision moments do not generally identify Shannon entropy, and that increasing collision order shifts sensitivity toward high-probability events. Numerical experiments illustrate the approximation--estimation tradeoff and compare collision-based approximations with plug-in and Miller--Madow estimators. The framework links collision counts, R\'enyi entropy, Shannon limits, and mutual information through a finite-resolution view of information, clarifying when low-order coincidence structure is informative and when irreducible information is lost.

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.

Referee Report

1 major / 1 minor

Summary. The manuscript presents a framework viewing information through finite-resolution collision statistics corresponding to integer-order Rényi entropies. It derives interpolation-error bounds for approximating Shannon entropy and mutual information from low-order Rényi entropies, with error controlled by the shape of the Rényi entropy path near order 1. The work separates deterministic approximation error from finite-sample estimation error, shows that finite collision moments do not generally identify Shannon entropy, and demonstrates that increasing collision order shifts sensitivity toward high-probability events. Numerical experiments compare collision-based approximations against plug-in and Miller-Madow estimators.

Significance. If the interpolation bounds hold, the paper provides a useful clarification of the approximation-estimation tradeoff in collision-based entropy estimation and a clean separation between deterministic loss and statistical error. The extension to mutual information and the observation on sensitivity to high-probability events are constructive. The numerical comparisons supply practical evidence of the tradeoff. The overall contribution is modest but well-scoped for the information-theory literature; its impact depends on confirming that the regularity conditions invoked for the Rényi path apply to general discrete distributions.

major comments (1)
  1. [Abstract / interpolation-error bounds derivation] Abstract and derivation of interpolation-error bounds: the claim that approximation error is controlled by the shape of the Rényi entropy path near the Shannon point (order 1) requires regularity conditions (differentiability, continuity, or monotonicity properties) on the Rényi function for arbitrary discrete distributions on finite alphabets. These conditions are not established, yet they are load-bearing for both the deterministic-vs-estimation error separation and the conclusion that finite collision moments do not identify Shannon entropy.
minor comments (1)
  1. [Abstract] The abstract refers to 'finite collision moments' without an explicit early statement that these are exactly the integer-order Rényi entropies; a single clarifying sentence would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for identifying the need to establish regularity conditions on the Rényi entropy path. We address the major comment below.

read point-by-point responses

  1. Referee: Abstract and derivation of interpolation-error bounds: the claim that approximation error is controlled by the shape of the Rényi entropy path near the Shannon point (order 1) requires regularity conditions (differentiability, continuity, or monotonicity properties) on the Rényi function for arbitrary discrete distributions on finite alphabets. These conditions are not established, yet they are load-bearing for both the deterministic-vs-estimation error separation and the conclusion that finite collision moments do not identify Shannon entropy.

    Authors: We agree that the interpolation bounds rely on regularity of the Rényi function near order 1. However, for any discrete distribution on a finite alphabet these conditions hold automatically. The map α ↦ ∑ p_i^α is a finite sum of exponential functions exp(α log p_i) and is therefore C^∞ on (0, ∞). The Rényi entropy H_α is thus C^∞ on (0,∞) excluding α=1, and the limit lim_{α→1} H_α equals the Shannon entropy by standard properties of the logarithm and the fact that the derivative at α=1 recovers the entropy. Continuity at α=1 follows similarly. We will add a brief lemma (or appendix) to the revised manuscript that states and proves these facts for finite alphabets. With this addition, the interpolation-error bounds are justified, the deterministic approximation error is cleanly separated from the estimation error, and the conclusion that finite-order collisions do not identify Shannon entropy remains valid because matching values at finitely many points α=2,3,… does not determine the value at α=1. revision: yes

Circularity Check

0 steps flagged

No circularity: derivations from Rényi definitions and collision moments are self-contained

full rationale

The paper's core claims—interpolation-error bounds controlled by Rényi path shape near order 1, separation of deterministic vs. estimation error, and non-identification of Shannon entropy by finite collision moments—follow directly from the definitions of integer-order Rényi entropies and standard interpolation theory applied to the entropy function. No step reduces a claimed prediction to a fitted input by construction, invokes a self-citation as the sole justification for a uniqueness or regularity property, or renames an empirical pattern. The regularity conditions on the Rényi path are invoked as mathematical assumptions whose consequences are derived, not smuggled in via prior self-work. The framework remains externally falsifiable via direct computation on discrete distributions.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract does not specify any free parameters, axioms, or invented entities; full manuscript required for assessment.

pith-pipeline@v0.9.1-grok · 5729 in / 1358 out tokens · 36855 ms · 2026-06-28T16:29:43.208333+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 1 canonical work pages

  1. [1]

    Note on the Bias of Information Estimates.Information Theory in Psychology: Problems and Methods1955, pp

    Miller, G.A. Note on the Bias of Information Estimates.Information Theory in Psychology: Problems and Methods1955, pp. 95–100

  2. [2]

    Estimation of Entropy and Mutual Information.Neural Computation2003,15, 1191–1253

    Paninski, L. Estimation of Entropy and Mutual Information.Neural Computation2003,15, 1191–1253

  3. [3]

    Estimating Entropy on m Bins Given Fewer than m Samples.IEEE Transactions on Information Theory2004,50, 2200–2203

    Paninski, L. Estimating Entropy on m Bins Given Fewer than m Samples.IEEE Transactions on Information Theory2004,50, 2200–2203

  4. [4]

    Finite Sample Corrections to Entropy and Dimension Estimates.Physics Letters A1988, 128, 369–373

    Grassberger, P . Finite Sample Corrections to Entropy and Dimension Estimates.Physics Letters A1988, 128, 369–373

  5. [5]

    Entropy and Inference, Revisited.Advances in Neural Information Processing Systems2002,14, 471–478

    Nemenman, I.; Shafee, F.; Bialek, W. Entropy and Inference, Revisited.Advances in Neural Information Processing Systems2002,14, 471–478

  6. [6]

    Estimating the Unseen: An n/ logn -Sample Estimator for Entropy and Support Size, Shown Optimal via New CLTs

    Valiant, G.; Valiant, P . Estimating the Unseen: An n/ logn -Sample Estimator for Entropy and Support Size, Shown Optimal via New CLTs. In Proceedings of the Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, 2011, pp. 685–694

    2011

  7. [7]

    Minimax Estimation of Functionals of Discrete Distributions.IEEE Transactions on Information Theory2015,61, 2835–2885

    Jiao, J.; Venkat, K.; Han, Y.; Weissman, T. Minimax Estimation of Functionals of Discrete Distributions.IEEE Transactions on Information Theory2015,61, 2835–2885

  8. [8]

    Minimax Rates of Entropy Estimation on Large Alphabets via Best Polynomial Approxima- tion.IEEE Transactions on Information Theory2016,62, 3702–3720

    Wu, Y.; Yang, P . Minimax Rates of Entropy Estimation on Large Alphabets via Best Polynomial Approxima- tion.IEEE Transactions on Information Theory2016,62, 3702–3720

  9. [9]

    A Class of Statistics with Asymptotically Normal Distribution.The Annals of Mathematical Statistics1948,19, 293–325

    Hoeffding, W. A Class of Statistics with Asymptotically Normal Distribution.The Annals of Mathematical Statistics1948,19, 293–325

  10. [10]

    Serfling, R.J.Approximation Theorems of Mathematical Statistics; Wiley, 1980

    1980

  11. [11]

    On Measures of Entropy and Information.Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability1961,1, 547–561

    Rényi, A. On Measures of Entropy and Information.Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability1961,1, 547–561

  12. [12]

    Towards more efficient Renyi entropy estimation.Entropy2023,25, 185

    Skorski, M. Towards more efficient Renyi entropy estimation.Entropy2023,25, 185

  13. [13]

    Measurement of Diversity.Nature1949,163, 688

    Simpson, E.H. Measurement of Diversity.Nature1949,163, 688

  14. [14]

    Diversity and Evenness: A Unifying Notation and Its Consequences.Ecology1973,54, 427–432

    Hill, M.O. Diversity and Evenness: A Unifying Notation and Its Consequences.Ecology1973,54, 427–432

  15. [15]

    23 of 23

    Cover, T.M.; Thomas, J.A.Elements of Information Theory, 2 ed.; Wiley, 2006. 23 of 23

    2006

  16. [16]

    The entropy universe.Entropy2021,23, 222

    Ribeiro, M.; Henriques, T.; Castro, L.; Souto, A.; Antunes, L.; Costa-Santos, C.; Teixeira, A. The entropy universe.Entropy2021,23, 222

  17. [17]

    Information Radius.Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete1969,14, 149–160

    Sibson, R. Information Radius.Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete1969,14, 149–160

  18. [18]

    Information Measures and Capacity of Order α for Discrete Memoryless Channels.Topics in Information Theory1977, pp

    Arimoto, S. Information Measures and Capacity of Order α for Discrete Memoryless Channels.Topics in Information Theory1977, pp. 41–52

  19. [19]

    Rényi Divergence and Kullback–Leibler Divergence.IEEE Transactions on Information Theory2014,60, 3797–3820

    van Erven, T.; Harremoës, P . Rényi Divergence and Kullback–Leibler Divergence.IEEE Transactions on Information Theory2014,60, 3797–3820

  20. [20]

    Bayesian Entropy Estimation for Countable Discrete Distributions.Journal of Machine Learning Research2014,15, 2833–2868

    Archer, E.; Park, I.M.; Pillow, J.W. Bayesian Entropy Estimation for Countable Discrete Distributions.Journal of Machine Learning Research2014,15, 2833–2868

  21. [21]

    Macdonald, I.G.Symmetric Functions and Hall Polynomials, 2 ed.; Oxford University Press, 1995

    1995

  22. [22]

    Comparing clusterings—an information based distance.Journal of Multivariate Analysis2007, 98, 873–895

    Meil˘ a, M. Comparing clusterings—an information based distance.Journal of Multivariate Analysis2007, 98, 873–895

  23. [23]

    Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance.Journal of Machine Learning Research2010,11, 2837– 2854

    Vinh, N.X.; Epps, J.; Bailey, J. Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance.Journal of Machine Learning Research2010,11, 2837– 2854

  24. [24]

    The Impact of Random Models on Clustering Similarity.Journal of Machine Learning Research2017,18, 1–28

    Gates, A.J.; Ahn, Y.Y. The Impact of Random Models on Clustering Similarity.Journal of Machine Learning Research2017,18, 1–28

  25. [25]

    Objective criteria for the evaluation of clustering methods

    Rand, W.M. Objective Criteria for the Evaluation of Clustering Methods.Journal of the American Statistical Association1971,66, 846–850. https://doi.org/10.1080/01621459.1971.10482356

    work page doi:10.1080/01621459.1971.10482356 1971

  26. [26]

    Comparing Partitions.Journal of Classification1985,2, 193–218

    Hubert, L.; Arabie, P . Comparing Partitions.Journal of Classification1985,2, 193–218. https://doi.org/10.100 7/BF01908075

  27. [27]

    Unifying Information-Theoretic and Pair-Counting Clustering Similarity.arXiv preprint arXiv:2511.030002025

    Gates, A.J. Unifying Information-Theoretic and Pair-Counting Clustering Similarity.arXiv preprint arXiv:2511.030002025

    Pith/arXiv arXiv

  28. [28]

    Element-centric clustering comparison unifies overlaps and hierarchy.Scientific reports2019,9, 8574

    Gates, A.J.; Wood, I.B.; Hetrick, W.P .; Ahn, Y.Y. Element-centric clustering comparison unifies overlaps and hierarchy.Scientific reports2019,9, 8574