Technische Samenvatting: Het Auditeren van Combinatorische Willekeur uit Eindige Transcripten

Probleemstelling

Publieke willekeur-services, zoals loterijen, randomness beacons en pseudowillekeurige generatoren, produceren eindige transcripten van combinatorische trekkingen (het selecteren van $k$ labels uit $m$ zonder teruglegging). Het beveiligingsdoel is om deze transcripten te auditeren om manipulatie of implementatiefouten te detecteren. Er bestaat echter een fundamentele informatie-theoretische barrière: voor een transcriptruimte van grootte $N = \binom{m}{k}$ vereist het testen op arbitraire gezamenlijke uniformiteit een steekproefomvang die schaalt als $\Theta(\sqrt{N}/\epsilon^2)$. Voor realistische loterijparameters (bijv. EuroMillions 5/50 of 6/90) is de ondersteuningsgrootte $N$ zo groot dat eindige historische transcripten geen volledige gezamenlijke uniformiteit kunnen certificeren tegen een onbeperkte tegenstander. Bovendien kan een distributie alle enkelvoudige marginale kansen behouden terwijl de kansen van paren, seriële overlappingen of de geometrische structuur van de trekkingen aanzienlijk worden gewijzigd, waardoor standaard marginale tests ineffectief worden.

Methodologie

De auteurs stellen een "generator-agnostisch" audit-framework voor dat de focus verlegt van willekeurige gezamenlijke uniformiteit naar het testen tegen benoemde gestructureerde alternatieve families. Deze families modelleren specifieke, laag-dimensionale faalmodi zoals hot labels, paar-koppelingen, seriële kleverigheid, geclusterde blokken en band-repulsie.

Statistisch Kader

De audit-batterij brengt trekkingen in kaart op de hypersimplex en evalueert exacte-combinatorische nul-gekalibreerde statistieken:

1. Marginale Chi-kwadraat: Test de tellingen van enkelvoudige coördinaten.
2. Paar-maxima: Evalueert de maximale afwijking in paar-kansen.
3. Seriële Overlap: Analyseert de intersectiegrootte tussen opeenvolgende trekkingen met behulp van hypergeometrische momenten.
4. Verankerde-Box Discrepantie: Meet de afwijking van cumulatieve distributiefuncties over een gekalibreerde set drempelwaarden.
5. $H_0$/MST Geometrie: Projecteert incidentievectoren en analyseert het Euclidische minimum-spanning-boom (MST) rand-spectrum.

Kalibratie en Implementatie

Om de discrete aard van het probleem aan te pakken en continue benaderingen te vermijden, implementeren de auteurs exacte-nul Monte Carlo-kalibratie.

• Exacte Nul Generatie: Een CUDA-implementatie gebruikt dynamisch programmeren om exacte kansen voor gesorteerde trekkingen te berekenen zonder te vertrouwen op continue-uniforme benaderingen.
• P-waarde Berekening: Gerandomiseerde-rang p-waarden worden afgeleid van i.i.d. exacte-nul replicaties gegenereerd met dezelfde $(m, k, n)$ parameters als de geobserveerde steekproef.
• Hardware: Experimenten maken gebruik van CPU-implementaties en GPU-acceleratie (NVIDIA RTX 5090 en A100 SXM4) om tot 300.000 nul-replicaties en 60.000 alternatieve replicaties per conditie uit te voeren.

Alternatieve Modellen

De studie introduceert vijf gecontroleerde alternatieve distributies om de kracht van de statistieken te testen:

• Hot-marginal: Multiplicatieve bemonsteringsgewichten op een deelverzameling.
• Paar-injectie: Gefixeerde paren geïnjecteerd met kans $\rho$.
• Blok-cluster: Hele blokken getallen geretourneerd met kans $\rho$ (behoudt enkelvoudige getal-marginale kansen).
• Band-repulsie: Eén getal geselecteerd uit elk van $k$ gelijke banden met kans $\rho$ (behoudt enkelvoudige getal-marginale kansen).
• Seriële-kleverigheid: Het kopiëren van een label uit de vorige trekking met kans $\rho$.

Belangrijkste Resultaten

1. Real-World Audit (EuroMillions)

De auteurs hebben 1.956 EuroMillions hoofdgetal-trekkingen geaudit (2004–2026).

• Resultaat: Geen enkele statistiek overleefde de false-discovery correctie. De minimale Benjamini–Hochberg q-waarde was 0,279.
• Conclusie: Het EuroMillions-spoor valt binnen het gekalibreerde referentiebereik en vertoont geen bewijs van de geteste gestructureerde afwijkingen.

2. Marginale Blinde Vlekken

GPU-experimenten toonden aan dat eendimensionale marginale tests blind zijn voor specifieke gezamenlijke structuren:

• Block-Cluster (Sterkte 0,04): Bij $n=1.956$ bereikte de pair max-z statistiek een detectiekracht van 0,638, terwijl de marginale chi-kwadraat op de nominale grootte van 0,051 bleef.
• Band-Repulsion (Sterkte 0,08): De anchored-box statistiek bereikte een kracht van 0,741, terwijl de marginale chi-kwadraat op 0,051 bleef.
• Implicatie: Een distributie kan perfect willekeurig lijken in termen van enkelvoudige getal-frequentie, terwijl deze significante structurele anomalieën vertoont die alleen detecteerbaar zijn door gezamenlijke of geometrische statistieken.

3. Steekproefomvang Frontier

De studie kwantificeert de steekproefomvang die vereist is om specifieke faalmodi te detecteren:

• Voor block clustering bij sterkte 0,04 steeg de detectiekracht van 0,638 bij $n=1.956$ naar 0,999 bij $n=5.000$.
• Voor band repulsion bij sterkte 0,04 steeg de anchored-box kracht van 0,186 bij $n=1.956$ naar 1,000 bij $n=20.000$.
• Dit bevestigt dat hoewel willekeurige uniformiteit ontestbaar is, specifieke gestructureerde afwijkingen detecteerbaar worden naarmate de transcriptlengte toeneemt, mits de audit zich richt op de juiste structurele familie.

4. Formaat Schaalbaarheid

Experimenten op grotere formaten (6/54 en 6/90) bevestigden dat dit patroon standhoudt: marginale tests blijven nabij de nominale grootte voor gestructureerde alternatieven, terwijl geometrische en paar-statistieken aan kracht winnen. Voor 6/90 block clustering bij $n=5.000$ bereikte pair max-z een kracht van 1,000.

Betekenis en Claims

Het artikel claimt een black-box auditbaarheid-frontier vastgesteld te hebben voor publieke combinatorische willekeur. De primaire bijdragen zijn:

1. Theoretische Limiet: Het karakteriseert formeel de onmogelijkheid om willekeurige gezamenlijke uniformiteit te testen voor grote combinatorische ruimtes met eindige transcripten, met verwijzing naar de ondergrenzen van Paninski.
2. Constructieve Alternatief: Het stelt een levensvatbaar beveiligingsmodel voor gebaseerd op het auditeren van benoemde gestructureerde families in plaats van willekeurige afwijkingen. Deze aanpak omzeilt de $\sqrt{N}$ steekproefcomplexiteitsbarrière door afhankelijk te zijn van de witness gap en het aantal testfamilies ($L$).
3. Methodologische Tooling: Het biedt een suite van generator-agnostische statistieken gekalibreerd tegen de exacte combinatorische nul, geïmplementeerd met high-performance computing om rigoureuze krachtanalyse mogelijk te maken.
4. Empirische Separatie: Het demonstreert empirisch dat marginale goedheid-van-passing onvoldoende is voor beveiligingsaudits, aangezien het exact blind kan zijn voor gezamenlijke structurele falen die wel detecteerbaar zijn door geometrische en paar-statistieken.

De auteurs concluderen dat hoewel volledige gezamenlijke uniformiteit onbereikbaar is voor eindige transcripten, "gestructureerde witness families" zinvolle beveiligingsclaims mogelijk maken met betrekking tot specifieke, laag-dimensionale faalmodi, mits de audit-steekproefomvang voldoende is voor de specifieke afwijking die wordt getest.