🔢 mathematics

Finite-Resolution Information from Collision Statistics

This paper establishes a framework for approximating Shannon entropy and mutual information using finite-resolution collision statistics and low-order Rényi entropies, deriving error bounds that distinguish between deterministic approximation limits and finite-sample estimation errors while demonstrating that low-order collision moments cannot fully recover Shannon information.

Original authors: Alexander J. Gates

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alexander J. Gates

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to describe a complex landscape to someone who has never seen it. You have a camera, but it's a bit broken. Instead of taking one perfect, high-definition photo of the whole scene, your camera can only take a series of "collision" photos.

In this paper, the author, Alexander Gates, explores what happens when we try to understand information (like how unpredictable a message is, or how much two things depend on each other) using only these limited "collision" photos.

Here is the breakdown of the paper's ideas using simple analogies:

1. The "Collision" Camera

Imagine you have a bag of colored marbles. You pull out a handful of marbles one by one.

A "Collision" happens if you pull out two marbles of the same color in a row.
A "Triplet Collision" happens if you pull out three of the same color.

In the world of data, these collisions are easy to count. If you have a million text messages, you can easily count how many times the letter "e" appears twice in a row, or how many times a specific word repeats. These are the "collision statistics."

The paper argues that these counts are like taking a photo with a specific lens. A "pair collision" photo (looking for two matches) gives you a blurry, wide-angle view. A "triplet collision" photo (looking for three matches) zooms in a bit more on the most common things.

2. The Goal: The "Perfect" Picture (Shannon Entropy)

In information theory, there is a "gold standard" for measuring uncertainty called Shannon Entropy. Think of this as the perfect, high-definition 4K photo of the entire marble bag. It tells you exactly how diverse or unpredictable the bag is.

The problem is that calculating this perfect photo is hard when you don't have enough data (like trying to guess the whole bag's contents after only pulling out 10 marbles).

3. The Solution: Guessing the Perfect Picture from Blurry Ones

Since we can easily count collisions, the author asks: Can we use these blurry "collision" photos to guess what the perfect 4K photo looks like?

The paper says: Yes, but with a catch.

The author creates a method to take the "pair collision" photo, the "triplet collision" photo, and the "quadruplet collision" photo, and then uses math to draw a smooth line connecting them. By extending that line back to the "perfect" point, they create an estimate of the Shannon Entropy.

4. The Two Types of Mistakes

This is the most important part of the paper. The author separates the errors into two distinct buckets:

Bucket A: The "Blurry Lens" Error (Approximation Error)
Even if you had an infinite number of marbles and could count every single collision perfectly, your estimate would still be slightly wrong. Why? Because you are trying to guess a complex curve (the perfect photo) using only a few straight lines (the collision photos). If the landscape is very bumpy, a few straight lines won't capture the curves perfectly.
- The Paper's Claim: This error is unavoidable if you only use a fixed number of collision types. No amount of extra data will fix this. It's a limitation of the "lens" you chose, not the data you have.
Bucket B: The "Bad Sample" Error (Estimation Error)
This is the error caused by not having enough marbles. If you only pull out 5 marbles, your count of collisions might be wrong just by bad luck.
- The Paper's Claim: If you keep pulling more marbles (increasing sample size), this error goes away. You will eventually know the exact number of collisions.

The Big Takeaway: You can fix Bucket B by getting more data, but you can never fix Bucket A without changing your method (using more types of collisions).

5. The "Zoom" Effect

The paper also explains that looking for different types of collisions changes what you see in the bag.

Low-order collisions (pairs): These see the whole bag. They notice if there are many different colors, even rare ones.
High-order collisions (triplets, quadruplets): These act like a magnifying glass on the most common colors. If you look for three red marbles in a row, you are mostly ignoring the blue and green ones. You are focusing only on the "heavy hitters."

So, as you add more complex collision types to your guess, you aren't just getting "more information"; you are actually zooming in on the most frequent events and ignoring the rare ones.

6. The "Impossible" Puzzle

Finally, the paper proves a surprising fact: You cannot perfectly reconstruct the whole picture just from a few collision counts.

Imagine two different bags of marbles.

Bag A has 50% Red, 50% Blue.
Bag B has 66% Red, 17% Blue, 17% Green.

If you only look for "pairs" (two of the same color), both bags might look exactly the same! They have the same "pair collision" rate. But their "perfect" uncertainty (Shannon Entropy) is different.

This means that if you only use a limited number of collision counts, there is a fundamental limit to how much you can know. You can get a good approximation, but you can never be 100% sure you have the true answer just from those limited counts.

Summary

The paper doesn't invent a new way to calculate the perfect answer. Instead, it builds a framework to understand what we lose when we try to measure information using simple, countable "collisions."

It tells us:

Counting collisions is easy and useful.
We can use them to guess the complex answer.
But we must accept that our guess will always have a "blurry lens" error that more data cannot fix.
Adding more complex collisions changes the focus of our view, zooming in on the most common events.

It's a guide for knowing when a simple, countable summary is enough, and when we are missing the "irreducible" details of the data.

Technical Summary: Finite-Resolution Information from Collision Statistics

Problem Statement
Estimating Shannon entropy and mutual information from finite discrete samples is a persistent challenge, particularly when the alphabet size is large relative to the number of observations. Standard empirical estimators (e.g., plug-in) suffer from significant bias in sparse regimes, while various corrections (Miller–Madow, Bayesian, minimax) attempt to recover the Shannon functional directly. This paper addresses a complementary question: rather than seeking a better estimator for the Shannon functional, what information is inherently visible from a finite number of low-order collision moments? The authors argue that two distinct sources of error are often conflated in this domain: statistical estimation error (how well a moment is estimated from data) and deterministic approximation error (how much information is lost when restricting the population target to finitely many collision moments).

Methodology
The paper formalizes a framework where Shannon entropy and mutual information are approximated by extrapolating the Rényi entropy path from integer orders $k \geq 2$ back to the Shannon point $\alpha = 1$ .

Collision Statistics and Rényi Entropy: The foundation is the order- $k$ collision probability $C_k(P) = \sum p_i^k$ , which represents the probability that $k$ independent samples fall on the same state. These are directly countable and form the basis for integer-order Rényi entropies $H_k(P) = \frac{1}{1-k} \log C_k(P)$ .
Finite-Resolution Approximations: The authors treat the sequence $H_2(P), H_3(P), \dots$ as observations of the function $h(\alpha) = H_\alpha(P)$ . They construct approximations to Shannon entropy $H(P)$ by interpolating these integer-order values using Lagrange polynomials and evaluating the result at $\alpha = 1$ . For example, a second-order approximation is $\hat{H}_2(P) = 2H_2(P) - H_3(P)$ .
Extension to Mutual Information: Mutual information is approximated by applying the same interpolation logic to the Rényi entropy contrast $K_\alpha(X; Y) = H_\alpha(X) + H_\alpha(Y) - H_\alpha(X, Y)$ , which converges to Shannon mutual information $I(X; Y)$ as $\alpha \to 1$ .
Error Decomposition: The total error of an empirical estimator $\hat{e}H_r$ $\overset{e}{^} H_{r}$ is decomposed into:
- Estimation Error: The stochastic error arising from estimating finite collision probabilities from a sample of size $N$ . This vanishes as $N \to \infty$ .
- Approximation Error: The deterministic gap between the finite-order population target $\hat{e}H_r(P)$ and the true Shannon entropy $H(P)$ . This gap persists regardless of sample size and is bounded by the higher-order derivatives of the Rényi entropy path.

Key Contributions

Formulation of Finite-Resolution Targets: The paper defines a family of population targets built from low-order collision moments. It establishes that fixed-order collision estimators converge to these finite-resolution Rényi-based functionals, not to Shannon entropy or mutual information themselves.
Separation of Error Sources: A primary contribution is the rigorous separation of estimation error from approximation error. The authors demonstrate that increasing sample size improves the precision of the finite-resolution target but does not eliminate the deterministic bias relative to Shannon quantities.
Interpolation Error Bounds: The authors derive interpolation-error bounds showing that the approximation error is controlled by the curvature and higher-order variation of the Rényi entropy path near the Shannon point.
Non-Identifiability Proof: The paper proves that finite collision moments do not generally identify Shannon entropy. Specifically, for any fixed number of collision orders $r$ , there exist distinct distributions on sufficiently large alphabets that share the same collision moments $C_2, \dots, C_{r+1}$ but possess different Shannon entropies.
Resolution Parameter Interpretation: The collision order $k$ is characterized as a resolution parameter. Low orders aggregate probability mass broadly, while high orders increasingly concentrate on the largest probability masses (approaching min-entropy), effectively suppressing the influence of the distribution's tail.

Results

Numerical Experiments: Simulations on a binary symmetric channel illustrate the approximation–estimation tradeoff.
- Population Level: Finite-order approximations ( $\hat{e}I_r$ ) reproduce the qualitative behavior of Shannon mutual information but exhibit deterministic overestimation at intermediate noise levels. This error is intrinsic to the finite-order truncation and persists even with exact population knowledge.
- Sample Level: As sample size $N$ increases, empirical estimators converge to their respective finite-resolution population targets, not to the Shannon value. Higher-order approximations reduce the deterministic gap to Shannon entropy but require larger sample sizes to stabilize due to the rarity of high-order coincidence events.
Concentration Effects: Experiments with tiered distributions show that increasing the collision order acts as a concentration filter, rapidly reducing the "effective number" of contributing states and shifting sensitivity toward high-probability events.

Significance and Claims
The paper does not claim that low-order collision statistics should replace direct estimators of Shannon entropy (such as NSB or minimax estimators), nor does it propose a new minimax estimator. Instead, its significance lies in clarifying the nature of information recovery from coincidence data:

Transparency: It provides a transparent hierarchy of finite-resolution summaries, making explicit what part of Shannon information is captured by coincidence structure at a given order and what is irreducibly lost.
Conceptual Clarity: It resolves the conflation of estimation and approximation errors, clarifying that fixed-order collision methods are consistent estimators of finite-resolution targets, not of Shannon quantities.
Theoretical Limits: By proving non-identifiability, the paper establishes an intrinsic limitation: no method relying solely on a finite set of low-order collision moments can recover Shannon entropy exactly for all distributions on large alphabets.
Interdisciplinary Connection: The framework links entropy estimation, Rényi information, and diversity measurement (e.g., Simpson diversity and Hill numbers), suggesting that pair-counting and higher-order tuple statistics can be viewed as points on a collision-information path.

In summary, the paper offers a finite-resolution view of information, arguing that the value of collision statistics lies not in replacing Shannon estimators, but in defining interpretable, scale-dependent summaries of uncertainty where the tradeoff between resolution and estimability is explicit.