💻 computer science

Auditing Combinatorial Randomness from Finite Transcripts

This paper establishes the information-theoretic limits of auditing public randomness from finite transcripts and proposes a suite of generator-agnostic statistical tests based on marginal, geometric, and topological features that can detect structured deviations with significantly lower sample complexity than unrestricted uniformity testing.

Original authors: Faruk Alpay, Levent Sarioglu

Published 2026-06-23

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Faruk Alpay, Levent Sarioglu

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 catch a cheater in a giant lottery game. The game involves picking 5 numbers out of 50, over and over again. The organizers publish a long list (a "transcript") of every winning combination they've ever drawn. Your job is to look at this list and decide: Is this truly random, or has someone tampered with the machine?

This paper is about building a better set of magnifying glasses for that detective work.

The Problem: The "Infinite" Possibility Trap

The authors start with a scary math fact. If you have 50 numbers and pick 5, there are over 2 million possible combinations.

The Old Way: Most auditors just check if every single number (1 through 50) appears roughly the same number of times.
The Flaw: A cheater could rig the machine so that every number appears equally often, but they always appear in specific pairs or groups. For example, if the number "7" is drawn, the number "12" is almost always drawn with it. A simple check of individual numbers would miss this completely. It's like checking if a deck of cards has the right number of Aces, Kings, and Queens, but failing to notice that every time an Ace is dealt, a King is dealt right after it.

The paper proves that to catch any possible cheating method in a list of this size, you would need an impossibly huge amount of data (more lottery draws than have ever happened in history). It's a "barrier" that makes total proof impossible for short lists.

The Solution: Looking at the Shape of the Data

Since we can't check every single possibility, the authors suggest checking for specific, common ways people might cheat. They call these "structured alternatives."

They built a "battery" of tests that look at the geometry of the lottery draws, not just the counts. Think of it like this:

Marginal Test (The Old Way): Counts how many times "7" appears.
Geometric Test (The New Way): Looks at the "shape" of the draws. Do the numbers clump together in blocks? Do they avoid each other in specific patterns? Do they stick together like glue from one draw to the next?

They use five specific "lenses" to look at the data:

Marginal Chi-Square: The old count check.
Pair Maxima: Checks if specific pairs of numbers show up together too often.
Serial Overlap: Checks if the numbers in today's draw are suspiciously similar to yesterday's.
Anchored Boxes: Checks if numbers are crowded into specific "zones" or ranges.
MST Geometry: A complex way of measuring the "distance" between draws to see if they form weird clusters.

The Experiment: Testing the Detective's Tools

The authors tested their new tools on real data:

Real Lottery Data: They analyzed 1,956 draws from the EuroMillions lottery (from 2004 to 2026).
Fake Data: They used supercomputers (GPUs) to generate millions of fake lottery draws where they knew the cheating method (e.g., "Let's make sure numbers 1-10 always appear together").

The Results:

The Real Lottery: When they applied their new, fancy geometric tests to the real EuroMillions data, everything looked normal. No cheating was detected. The "p-values" (a score of how suspicious the data is) were high, meaning the lottery looks fair.
The Fake Data: When they tested their tools on the rigged data, the results were dramatic.
- The old "count" test (Marginal Chi-Square) failed completely. It said the rigged data was fine because the individual numbers were balanced.
- The new "geometric" tests caught the cheaters immediately. They could see the hidden patterns (like the "clumping" or "repulsion" of numbers) that the old tests missed.

The Takeaway

The paper concludes that for public randomness (like lotteries or security beacons), you cannot prove a system is 100% perfect without an infinite amount of data. However, you can prove it is not rigged in specific, common ways.

By using these new geometric tools, auditors can spot "low-dimensional" cheating (simple patterns) that would otherwise be invisible. It's the difference between checking if a room has the right number of chairs, versus checking if the chairs are arranged in a secret, suspicious pattern. The paper shows that while we can't check every pattern, we can definitely catch the ones that matter most.

Technical Summary: Auditing Combinatorial Randomness from Finite Transcripts

Problem Statement

Public randomness services, such as lotteries, randomness beacons, and pseudorandom generators, produce finite transcripts of combinatorial draws (selecting $k$ labels from $m$ without replacement). The security objective is to audit these transcripts to detect tampering or implementation faults. However, a fundamental information-theoretic barrier exists: for a transcript space of size $N = \binom{m}{k}$ , testing for arbitrary joint uniformity requires a sample size scaling as $\Theta(\sqrt{N}/\epsilon^2)$ . For realistic lottery parameters (e.g., EuroMillions 5/50 or 6/90), the support size $N$ is so large that finite historical transcripts cannot certify full joint uniformity against an unrestricted adversary. Furthermore, a distribution can preserve all single-number marginal probabilities while significantly altering pair probabilities, serial overlaps, or the geometric structure of the draws, rendering standard marginal tests ineffective.

Methodology

The authors propose a "generator-agnostic" audit framework that shifts focus from arbitrary joint uniformity to testing against named structured alternative families. These families model specific, low-dimensional failure modes such as hot labels, pair couplings, serial stickiness, clustered blocks, and band repulsion.

Statistical Framework

The audit battery maps draws to the hypersimplex and evaluates exact-combinatorial null-calibrated statistics:

Marginal Chi-Square: Tests single-coordinate counts.
Pair Maxima: Evaluates the maximum deviation in pair probabilities.
Serial Overlap: Analyzes the intersection size between consecutive draws using hypergeometric moments.
Anchored-Box Discrepancy: Measures the deviation of cumulative distribution functions over a calibrated set of thresholds.
$H_0$ /MST Geometry: Projects incidence vectors and analyzes the Euclidean minimum-spanning-tree edge spectrum.

Calibration and Implementation

To handle the discrete nature of the problem and avoid continuous approximations, the authors implement exact-null Monte Carlo calibration.

Exact Null Generation: A CUDA implementation uses dynamic programming to compute exact probabilities for sorted draws without relying on continuous-uniform approximations.
P-value Calculation: Randomized-rank p-values are derived from i.i.d. exact-null replications generated at the same $(m, k, n)$ parameters as the observed sample.
Hardware: Experiments utilize CPU implementations and GPU acceleration (NVIDIA RTX 5090 and A100 SXM4) to perform up to 300,000 null replications and 60,000 alternative replications per condition.

Alternative Models

The study introduces five controlled alternative distributions to test the power of the statistics:

Hot-marginal: Multiplicative sampling weights on a subset.
Pair-injection: Fixed pairs injected with probability $\rho$ .
Block-cluster: Entire blocks of numbers returned with probability $\rho$ (preserving single-number marginals).
Band-repulsion: One number selected from each of $k$ equal bands with probability $\rho$ (preserving single-number marginals).
Serial-stickiness: Copying a label from the previous draw with probability $\rho$ .

Key Results

1. Real-World Audit (EuroMillions)

The authors audited 1,956 EuroMillions main-number draws (2004–2026).

Outcome: No statistic survived false-discovery adjustment. The minimum Benjamini–Hochberg q-value was 0.279.
Conclusion: The EuroMillions trace falls within the calibrated reference range, showing no evidence of the tested structured deviations.

2. Marginal-Preserving Blind Spots

GPU experiments demonstrated that one-dimensional marginal tests are blind to specific joint structures:

Block-Cluster (Strength 0.04): At $n=1,956$ , the pair max-z statistic achieved a detection power of 0.638, while the marginal chi-square remained at the nominal size of 0.051.
Band-Repulsion (Strength 0.08): The anchored-box statistic achieved a power of 0.741, while marginal chi-square remained at 0.051.
Implication: A distribution can appear perfectly random in terms of single-number frequency while exhibiting significant structural anomalies detectable only by joint or geometric statistics.

3. Sample-Size Frontier

The study quantifies the sample sizes required to detect specific failure modes:

For block clustering at strength 0.04, detection power rose from 0.638 at $n=1,956$ to 0.999 at $n=5,000$ .
For band repulsion at strength 0.04, anchored-box power increased from 0.186 at $n=1,956$ to 1.000 at $n=20,000$ .
This confirms that while arbitrary uniformity is untestable, specific structured deviations become detectable as the transcript length increases, provided the audit targets the correct structural family.

4. Format Scalability

Experiments on larger formats (6/54 and 6/90) confirmed that the pattern holds: marginal tests remain near nominal size for structured alternatives, while geometric and pair statistics gain power. For 6/90 block clustering at $n=5,000$ , pair max-z achieved power 1.000.

Significance and Claims

The paper claims to establish a black-box auditability frontier for public combinatorial randomness. Its primary contributions are:

Theoretical Limit: It formally characterizes the impossibility of testing arbitrary joint uniformity for large combinatorial spaces with finite transcripts, citing Paninski's lower bounds.
Constructive Alternative: It proposes a viable security model based on auditing named structured families rather than arbitrary deviations. This approach avoids the $\sqrt{N}$ sample complexity barrier by depending on the witness gap and the number of test families ( $L$ ).
Methodological Tooling: It provides a suite of generator-agnostic statistics calibrated against the exact combinatorial null, implemented with high-performance computing to enable rigorous power analysis.
Empirical Separation: It empirically demonstrates that marginal goodness-of-fit is insufficient for security auditing, as it can be exactly blind to joint-structure failures that are detectable by geometric and pair statistics.

The authors conclude that while full joint uniformity is out of reach for finite transcripts, "structured witness families" allow for meaningful security claims regarding specific, low-dimensional failure modes, provided the audit sample size is sufficient for the specific deviation being tested.