📊 statistics

E-variables and tests of randomness for distribution classes

This paper introduces the method of e-variable-approximability to construct e-variables for popular distribution classes and demonstrates how these constructions yield explicit randomness tests grounded in Levin's concept from Algorithmic Information Theory.

Original authors: Georgii Potapov, Yuri Kalnishkan

Published 2026-03-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Georgii Potapov, Yuri Kalnishkan

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 a detective trying to solve a mystery. You have a pile of evidence (data), and you want to know: Is this evidence just random noise, or does it point to a specific culprit (a specific pattern or distribution)?

For decades, detectives have used a tool called the P-value. Think of a P-value as a "suspicion meter." If the meter goes high, you suspect the data isn't random. But this meter has a major flaw: it's fragile. If you look at the evidence in chunks, or if you decide to stop looking halfway through, the meter breaks or gives you a false reading. It's like trying to measure the height of a building with a ruler that shrinks every time you blink.

Enter the E-variable. This is the new, super-powered detective tool.

The Superpower: An E-variable is a "suspicion score" that is incredibly robust. You can combine scores from different detectives, or stop looking at the data at any random moment, and the score remains valid. It never breaks.
The Catch: While we know how to make E-variables for simple, specific suspects (like "The culprit is exactly a fair coin"), it has been very hard to make them for classes of suspects (like "The culprit is any biased coin," or "The culprit is any normal distribution").

The Problem: The "Infinite Suspect" List

Imagine you are trying to prove that a coin is rigged.

Simple Case: You suspect it's rigged to land heads 60% of the time. Easy. You build a test for that specific 60%.
Complex Case: You don't know how it's rigged. It could be 60%, 61%, 59.9%, or any number in between. There are infinite possibilities.
The Old Way: To test the whole group, you might try to take the "worst-case scenario" of all the individual tests. But mathematically, this often breaks the rules. It's like trying to build a bridge by just stacking infinite planks of wood; eventually, the structure collapses, or the bridge becomes invisible (mathematically "non-measurable").

The Solution: The "Smart Net" (E-variable Approximability)

The authors of this paper, Georgii Potapov and Yuri Kalnishkan, invented a new method called E-variable Approximability.

Here is the analogy: The "Smart Net" Strategy.

Instead of trying to catch every single possible suspect (every single number between 0 and 1), you build a net with specific holes.

The Net: You pick a few "representative" suspects (e.g., 50%, 60%, 70%). Let's call these your "Net Points."
The Estimator: When you see the data, you don't try to guess the exact percentage. Instead, you ask: "Which of my Net Points is this data closest to?"
The Magic: The authors proved that if you have a valid test for your Net Points, you can combine them into a single, valid test for the entire group of suspects.

It's like having a security system with cameras at specific checkpoints. You don't need a camera on every single inch of the street. If you know that anyone moving between checkpoints behaves in a predictable way, the checkpoints are enough to catch the criminal, no matter where they are.

How They Did It (The "Smoothing" Trick)

There was one technical hurdle. The "Net" approach usually involves rounding numbers (e.g., "If it's 59%, round it to 60%"). But in the world of computer science and randomness, "rounding" is a jagged, jerky action that breaks the math needed for these tests to be "computable" (something a computer can actually calculate).

The authors used a Smoothing Technique.

Imagine the jagged edge of a cliff (the rounding).
They built a gentle ramp (a continuous function) connecting the cliffs.
This allows the computer to smoothly transition from testing for "60%" to "61%" without the math breaking.

What They Achieved

Using this "Smart Net" and "Smoothing" method, they successfully built robust E-variables for many important types of data distributions that scientists use every day:

Uniform Distributions: (Data spread evenly over a range).
Poisson Distributions: (Counting rare events, like earthquakes or typos).
Normal (Gaussian) Distributions: (The famous "Bell Curve," used for heights, test scores, etc.).
Cauchy Distributions: (Data with wild outliers).

Why This Matters

Better Science: Researchers can now design experiments that are more flexible. They can stop collecting data whenever they want without invalidating their results.
Machine Learning: This helps AI systems better detect when data is "fake" or "out of distribution."
The "Why" behind the "How": The paper connects this statistical tool back to Algorithmic Information Theory (a field about how much information is in a string of data). They showed that their new method is essentially a practical, computer-friendly version of a deep theoretical concept called "Randomness Deficiency."

In a Nutshell

The authors took a powerful but fragile statistical tool (E-variables), figured out how to make it work for complex, real-world scenarios (classes of distributions), and built a "net" that catches all the suspects without breaking the math. They turned a theoretical concept into a practical, robust tool for scientists and data scientists.

1. Problem Statement

The paper addresses two interconnected challenges in statistical hypothesis testing and Algorithmic Information Theory (AIT):

Limitations of P-values: Traditional hypothesis testing relies on p-values, which lack "natural" properties (e.g., they are not stable under random stopping times or data aggregation) and are prone to misuse.
Constructing Randomness Tests for Classes: While E-variables (non-negative statistics with expected value $\le 1$ $\leq 1$ ) offer a robust alternative to p-values, constructing explicit E-variables for composite hypotheses (classes of distributions) is difficult. Specifically, the authors aim to construct lower semi-computable (l.s.c.) randomness tests (in the sense of Levin) for specific families of distributions.
- The Core Difficulty: A naive approach to combining E-variables for simple hypotheses (e.g., taking an infimum over a parameter space) often fails because the resulting function may not be measurable or may not preserve the E-variable property (expected value $\le 1$ ). Furthermore, standard estimators like Maximum Likelihood Estimators (MLE) do not always yield valid E-variables when applied to composite classes.

2. Methodology

The authors introduce a novel framework called E-variable-approximability to bridge the gap between simple and composite hypotheses.

A. E-variable-Approximability (Definition 3.1)

A family of distributions $\mathcal{H}$ is E-variable approximable from a countable "net" $S \subset \mathcal{H}$ if there exists:

A countable set of distributions $\{P_s\}_{s \in S}$ .
An estimator function $\hat{s}: \mathcal{X} \to S$ .
A constant $C > 0$ .

Such that for any collection of E-variables $\{e_s\}$ for the simple hypotheses $\{P_s\}$ , the aggregated statistic:
$e(x) = \frac{1}{C} e_{\hat{s}(x)}(x)$
is a valid E-variable for the entire composite hypothesis $\mathcal{H}$ .

B. Technical Conditions (Lemmas 1 & 2)

To verify E-variable-approximability, the authors provide sufficient conditions involving:

Log-likelihood decomposition: Relating the log-ratio of densities to a divergence function $d(\cdot \| \cdot)$ .
Boundedness: Ensuring the divergence between the estimator and the true parameter is bounded within the partition defined by the net.
Separation: Ensuring the net points are sufficiently separated in the parameter space (via a condition on $d$ ).
Exponential Families: The paper proves that for canonical exponential families, the likelihood equation solution naturally satisfies these conditions using Kullback-Leibler (KL) divergence.

C. Continuous Interpolation (Section 3.2)

Since standard rounding functions (used in estimators) are discontinuous and thus not computable in the context of real-valued distributions, the authors introduce continuously E-variable-approximability.

They construct a "partition of unity" using continuous indicator functions to smooth the transition between discrete net points.
This ensures the resulting test function is lower semi-computable, a requirement for AIT randomness tests.

D. Connection to Randomness Deficiency

The paper leverages the concept of randomness deficiency ( $t(x|P)$ ), which is the optimal l.s.c. test of randomness. The goal is to show that the randomness test for a class $\mathcal{P}$ , defined as $t_{\mathcal{P}}(x) = \inf_{P \in \mathcal{P}} t(x|P)$ , is l.s.c. and can be explicitly constructed using the E-variable-approximability technique.

3. Key Contributions

General Approximation Technique: The paper provides a unified method to construct E-variables for composite hypotheses using E-variables for simple hypotheses as "black boxes," without relying on reverse information projection or p-value calibration.
Explicit Constructions for Major Distributions: The authors prove that E-variable-approximability holds for several critical distribution families:
- Binomial and Uniform distributions on integers.
- Poisson distributions.
- Uniform distributions on real intervals.
- Normal (Gaussian) distributions (both fixed variance and fixed mean).
- Cauchy distributions.
Lower Semi-Computability: The paper demonstrates that for these families, the randomness test relative to the class is lower semi-computable. This is a significant theoretical result, as it proves the existence of effective (algorithmic) randomness tests for these classes, extending previous results that were limited to topologically closed sets or Cantor spaces.
Theoretical Justification for MDL: The approach of "trimming" data via estimators to reduce noise impact is linked to the Minimum Description Length (MDL) principle, offering a theoretical justification for MDL in the context of E-variables.

4. Key Results

Theorem 3: Establishes that Binomial, Poisson, Uniform, Normal, and Cauchy families are E-variable-approximable. It specifies the appropriate "nets" (e.g., powers of 2 for Uniform, integer grids for Normal) and estimators (e.g., rounding to the nearest net point).
Theorem 5 & 6 (Main Algorithmic Results):
- For computable families that are E-variable-approximable, the universal randomness test for the class $t_{\mathcal{P}}(x)$ is equivalent (up to a multiplicative constant) to the test evaluated at the estimated parameter:
  $t_{\mathcal{P}}(x) \asymp t(x | P_{\hat{s}(x)})$
- Specifically, for Normal and Cauchy distributions, the randomness test for the class is equivalent to the test against the distribution with the parameter rounded to the nearest integer (or grid point).
Corollary: Provides a concrete formula for constructing an E-variable for a product of Normal distributions using a product of E-variables for the estimated mean.

5. Significance

Bridging Statistics and AIT: The work successfully translates the abstract concept of "randomness deficiency" from Algorithmic Information Theory into practical, constructive tools for statistical hypothesis testing using E-variables.
Robustness: By utilizing E-variables, the proposed tests inherit the robustness of E-variables: they allow for flexible experimental designs, valid meta-analysis (combining tests), and validity at random stopping times (supermartingale property).
Overcoming Topological Limitations: Previous existence proofs for randomness tests often required the class of distributions to be topologically closed. This paper extends these results to classes that are not topologically closed (e.g., sequences of uniform distributions converging to a point mass), which is crucial for practical machine learning applications where parameter spaces are often open or unbounded.
Practical Applicability: By providing explicit constructions for common distributions (Gaussian, Poisson, etc.), the paper makes these advanced theoretical tools accessible for application in machine learning, anomaly detection, and sequential analysis.

In summary, Potapov and Kalnishkan provide a rigorous mathematical framework to construct optimal, computable randomness tests for broad classes of distributions, solving the problem of how to aggregate simple tests into a valid composite test without losing computability or statistical validity.