Riepilogo Tecnico: Audit della Casualità Combinatoria da Trascrizioni Finite

Definizione del Problema

I servizi di casualità pubblica, come lotterie, beacon di casualità e generatori di numeri pseudo-casuali, producono trascrizioni finite di estrazioni combinatorie (selezione di $k$ etichette da $m$ senza reinserimento). L'obiettivo di sicurezza è sottoporre queste trascrizioni ad audit per rilevare manomissioni o difetti di implementazione. Tuttavia, esiste una barriera fondamentale dal punto di vista dell'informazione teorica: per testare l'uniformità congiunta arbitraria in uno spazio di trascrizione di dimensione $N = \binom{m}{k}$, un campione deve scalare come $\Theta(\sqrt{N}/\epsilon^2)$. Per parametri di lotteria realistici (ad esempio, EuroMillions 5/50 o 6/90), la dimensione del supporto $N$ è così elevata che le trascrizioni storiche finite non possono certificare la piena uniformità congiunta contro un avversario illimitato. Inoltre, una distribuzione può preservare tutte le probabilità marginali dei singoli numeri pur alterando significativamente le probabilità delle coppie, le sovrapposizioni seriali o la struttura geometrica delle estrazioni, rendendo inefficaci i test marginali standard.

Metodologia

Gli autori propongono un framework di audit "agnostico rispetto al generatore" che sposta il focus dall'uniformità congiunta arbitraria al test contro famiglie di alternative strutturate nominate. Queste famiglie modellano specifici modi di fallimento a bassa dimensionalità, come etichette calde (hot labels), accoppiamenti di coppie, viscosità seriale (serial stickiness), blocchi clusterizzati e repulsione di banda.

Framework Statistico

La batteria di audit mappa le estrazioni nell'ipersimplessi e valuta statistiche esatte a calibrazione combinatoria nulla:

1. Chi-Quadrato Marginale: Testa i conteggi delle singole coordinate.
2. Massimi di Coppia (Pair Maxima): Valuta la deviazione massima nelle probabilità di coppia.
3. Sovrapposizione Seriale: Analizza la dimensione dell'intersezione tra estrazioni consecutive utilizzando i momenti ipergeometrici.
4. Discrepanza Box-Ancorata (Anchored-Box): Misura la deviazione delle funzioni di distribuzione cumulata su un insieme calibrato di soglie.
5. Geometria $H_0$/MST: Proietta i vettori di incidenza e analizza lo spettro degli archi dell'albero coprente minimo euclideo (Minimum Spanning Tree).

Calibrazione e Implementazione

Per gestire la natura discreta del problema ed evitare approssimazioni continue, gli autori implementano la calibrazione Monte Carlo del nullo esatto.

• Generazione del Nullo Esatto: Un'implementazione CUDA utilizza la programmazione dinamica per calcolare le probabilità esatte per le estrazioni ordinate senza fare affidamento su approssimazioni uniformi continue.
• Calcolo del P-value: I p-value di rango randomizzato sono derivati da repliche i.i.d. del nullo esatto generate con gli stessi parametri $(m, k, n)$ del campione osservato.
• Hardware: Gli esperimenti utilizzano implementazioni CPU e accelerazione GPU (NVIDIA RTX 5090 e A100 SXM4) per eseguire fino a 300.000 repliche nulle e 60.000 repliche alternative per condizione.

Modelli Alternativi

Lo studio introduce cinque distribuzioni alternative controllate per testare la potenza delle statistiche:

• Hot-marginal: Pesi di campionamento moltiplicativi su un sottoinsieme.
• Iniezione di Coppia (Pair-injection): Coppie fisse iniettate con probabilità $\rho$.
• Cluster di Blocchi (Block-cluster): Interi blocchi di numeri restituiti con probabilità $\rho$ (preservando le marginali dei singoli numeri).
• Repulsione di Banda (Band-repulsion): Un numero selezionato da ciascuna delle $k$ bande uguali con probabilità $\rho$ (preservando le marginali dei singoli numeri).
• Viscosità Seriale (Serial-stickiness): Copia di un'etichetta dall'estrazione precedente con probabilità $\rho$.

Risultati Chiave

1. Audit nel Mondo Reale (EuroMillions)

Gli autori hanno sottoposto a audit 1.956 estrazioni dei numeri principali di EuroMillions (2004–2026).

• Esito: Nessuna statistica è sopravvissuta all'aggiustamento per la scoperta falsa (false-discovery adjustment). Il valore q minimo di Benjamini–Hochberg è stato 0,279.
• Conclusione: La traccia di EuroMillions rientra nel range di riferimento calibrato, non mostrando evidenza dei testati scostamenti strutturati.

2. Punti Ciechi a Preservazione Marginale

Gli esperimenti su GPU hanno dimostrato che i test marginali monodimensionali sono ciechi a specifiche strutture congiunte:

• Block-Cluster (Forza 0,04): Con $n=1.956$, la statistica pair max-z ha raggiunto una potenza di rilevamento di 0,638, mentre il chi-quadrato marginale è rimasto alla dimensione nominale di 0,051.
• Band-Repulsion (Forza 0,08): La statistica anchored-box ha raggiunto una potenza di 0,741, mentre il chi-quadrato marginale è rimasto a 0,051.
• Implicazione: Una distribuzione può apparire perfettamente casuale in termini di frequenza dei singoli numeri pur presentando anomalie strutturali significative rilevabili solo da statistiche geometriche o di coppia.

3. Frontiera della Dimensione del Campione

Lo studio quantifica le dimensioni del campione necessarie per rilevare specifici modi di fallimento:

• Per il clustering di blocchi con forza 0,04, la potenza di rilevamento è salita da 0,638 con $n=1.956$ a 0,999 con $n=5.000$.
• Per la repulsione di banda con forza 0,04, la potenza dell'anchored-box è aumentata da 0,186 con $n=1.956$ a 1,000 con $n=20.000$.
• Ciò conferma che, sebbene l'uniformità arbitraria sia non testabile, le deviazioni strutturate specifiche diventano rilevabili all'aumentare della lunghezza della trascrizione, a patto che l'audit colga la corretta famiglia strutturale.

4. Scalabilità del Formato

Esperimenti su formati più grandi (6/54 e 6/90) hanno confermato che il pattern si mantiene: i test marginali rimangono vicini alla dimensione nominale per le alternative strutturate, mentre le statistiche geometriche e di coppia guadagnano potenza. Per il clustering di blocchi 6/90 con forza 0,04, la statistica pair max-z ha raggiunto una potenza di 1,000 con $n=5.000$.

Significato e Rivendicazioni

Il documento sostiene di aver stabilito un frontiere di auditabilità black-box per la casualità combinatoria pubblica. I suoi contributi primari sono:

1. Limite Teorico: Caratterizza formalmente l'impossibilità di testare l'uniformità congiunta arbitraria per grandi spazi combinatori con trascrizioni finite, citando i limiti inferiori di Paninski.
2. Alternativa Costruttiva: Propone un modello di sicurezza vitale basato sull'audit di famiglie strutturate nominate piuttosto che su deviazioni arbitrarie. Questo approccio evita la barriera della complessità campionaria $\sqrt{N}$ dipendendo dal gap del testimone (witness gap) e dal numero di famiglie di test ($L$).
3. Strumentazione Metodologica: Fornisce una suite di statistiche agnostiche rispetto al generatore calibrate contro il nullo combinatorio esatto, implementate con calcolo ad alte prestazioni per consentire un'analisi rigorosa della potenza.
4. Separazione Empirica: Dimostra empiricamente che la bontà di adattamento marginale è insufficiente per l'audit di sicurezza, poiché può essere esattamente cieca a fallimenti della struttura congiunta rilevabili da statistiche geometriche e di coppia.

Gli autori concludono che, sebbene l'uniformità congiunta completa sia fuori portata per trascrizioni finite, le "famiglie di testimoni strutturati" permettono rivendicazioni di sicurezza significative riguardo a specifici modi di fallimento a bassa dimensionalità, a condizione che la dimensione del campione dell'audit sia sufficiente per la specifica deviazione testata.