Resumo Técnico: Auditoria de Aleatoriedade Combinatória a partir de Transcrições Finitas

Declaração do Problema

Serviços de aleatoriedade pública, como loterias, beacons de aleatoriedade e geradores de números pseudoaleatórios, produzem transcrições finitas de sorteios combinatórios (seleção de $k$ rótulos de $m$ sem reposição). O objetivo de segurança é auditar essas transcrições para detectar adulterações ou falhas de implementação. No entanto, existe uma barreira fundamental de informação-teórica: para um espaço de transcrição de tamanho $N = \binom{m}{k}$, o teste de uniformidade conjunta arbitrária exige um tamanho de amostra que escala como $\Theta(\sqrt{N}/\epsilon^2)$. Para parâmetros de loteria realistas (por exemplo, EuroMillions 5/50 ou 6/90), o tamanho do suporte $N$ é tão grande que transcrições históricas finitas não podem certificar a uniformidade conjunta total contra um adversário irrestrito. Além disso, uma distribuição pode preservar todas as probabilidades marginais de números individuais enquanto altera significativamente as probabilidades de pares, sobreposições seriais ou a estrutura geométrica dos sorteios, tornando os testes marginais padrão ineficazes.

Metodologia

Os autores propõem uma estrutura de auditoria "agnóstica ao gerador" que desloca o foco da uniformidade conjunta arbitrária para o teste contra famílias alternativas estruturadas nomeadas. Essas famílias modelam modos de falha específicos e de baixa dimensão, como rótulos quentes (hot labels), acoplamentos de pares, aderência serial (serial stickiness), blocos agrupados (clustered blocks) e repulsão de bandas (band repulsion).

Estrutura Estatística

A bateria de testes mapeia os sorteios para o hipersimpléx e avalia estatísticas de calibração nula combinatórias exatas:

1. Qui-Quadrado Marginal: Testa contagens de coordenadas únicas.
2. Máximos de Pares: Avalia o desvio máximo nas probabilidades de pares.
3. Sobreposição Serial: Analisa o tamanho da interseção entre sorteios consecutivos usando momentos hipergeométricos.
4. Discrepância de Caixa Ancorada (Anchored-Box): Mede o desvio das funções de distribuição cumulativa sobre um conjunto calibrado de limiares.
5. $H_0$/MST Geometria: Projeta vetores de incidência e analisa o espectro de arestas do mínimo árvore geradora euclidiana (Euclidean minimum-spanning-tree).

Calibração e Implementação

Para lidar com a natureza discreta do problema e evitar aproximações contínuas, os autores implementam a calibração de Monte Carlo nula exata.

• Geração de Nula Exata: Uma implementação em CUDA utiliza programação dinâmica para computar probabilidades exatas para sorteios ordenados sem depender de aproximações uniformes contínuas.
• Cálculo de P-valor: P-valores de ranking aleatorizado são derivados de replicações nulas i.i.d. geradas com os mesmos parâmetros $(m, k, n)$ da amostra observada.
• Hardware: Experimentos utilizam implementações em CPU e aceleração por GPU (NVIDIA RTX 5090 e A100 SXM4) para realizar até 300.000 replicações nulas e 60.000 replicações alternativas por condição.

Modelos Alternativos

O estudo introduz cinco distribuições alternativas controladas para testar o poder das estatísticas:

• Marginal Quente (Hot-marginal): Pesos de amostragem multiplicativos em um subconjunto.
• Injeção de Par (Pair-injection): Pares fixos injetados com probabilidade $\rho$.
• Agrupamento de Bloco (Block-cluster): Blocos inteiros de números retornados com probabilidade $\rho$ (preservando as marginais de números individuais).
• Repulsão de Banda (Band-repulsion): Um número selecionado de cada um de $k$ bandas iguais com probabilidade $\rho$ (preservando as marginais de números individuais).
• Aderência Serial (Serial-stickiness): Copiando um rótulo do sorteio anterior com probabilidade $\rho$.

Principais Resultados

1. Auditoria do Mundo Real (EuroMillions)

Os autores auditaram 1.956 sorteios principais do EuroMillions (2004–2026).

• Resultado: Nenhuma estatística sobreviveu ao ajuste de falsa descoberta. O valor-q mínimo de Benjamini–Hochberg foi 0,279.
• Conclusão: A trajetória do EuroMillions está dentro do intervalo de referência calibrado, não mostrando evidências das testadas desvios estruturados.

2. Pontos Cegos de Preservação Marginal

Experimentos em GPU demonstraram que testes marginais unidimensionais são cegos a certas estruturas conjuntas:

• Agrupamento de Bloco (Força 0,04): Para $n=1.956$, a estatística pair max-z alcançou um poder de detecção de 0,638, enquanto o qui-quadrado marginal permaneceu no tamanho nominal de 0,051.
• Repulsão de Banda (Força 0,08): A estatística anchored-box alcançou um poder de 0,741, enquanto o qui-quadrado marginal permaneceu em 0,051.
• Implicação: Uma distribuição pode parecer perfeitamente aleatória em termos de frequência de números individuais enquanto exibe anomalias estruturais significativas detectáveis apenas por estatísticas geométricas ou de pares.

3. Fronteira de Tamanho de Amostra

O estudo quantifica os tamanhos de amostra necessários para detectar modos de falha específicos:

• Para agrupamento de blocos com força 0,04, o poder de detecção subiu de 0,638 em $n=1.956$ para 0,999 em $n=5.000$.
• Para repulsão de banda com força 0,04, o poder da caixa ancorada aumentou de 0,186 em $n=1.956$ para 1,000 em $n=20.000$.
• Isso confirma que, embora a uniformidade arbitrária seja intestável, desvios estruturados específicos tornam-se detectáveis conforme o comprimento da transcrição aumenta, desde que a auditoria foque na família estrutural correta.

4. Escalabilidade de Formato

Experimentos em formatos maiores (6/54 e 6/90) confirmaram que o padrão se mantém: testes marginais permanecem próximos do tamanho nominal para alternativas estruturadas, enquanto estatísticas geométricas e de pares ganham poder. Para o agrupamento de blocos em 6/90 com $n=5.000$, o pair max-z alcançou poder 1,000.

Significância e Alegações

O artigo afirma estabelecer uma fronteira de auditabilidade de caixa-preta para a aleatoriedade combinatória pública. Suas principais contribuições são:

1. Limite Teórico: Caracteriza formalmente a impossibilidade de testar a uniformidade conjunta arbitrária para grandes espaços combinatórios com transcrições finitas, citando os limites inferiores de Paninski.
2. Alternativa Construtiva: Propõe um modelo de segurança viável baseado na auditoria de famílias estruturadas nomeadas em vez de desvios arbitrários. Esta abordagem evita a barreira de complexidade de amostra $\sqrt{N}$ ao depender do gap da testemunha e do número de famílias de teste ($L$).
3. Ferramental Metodológico: Fornece uma suíte de estatísticas agnósticas ao gerador calibradas contra a nula combinatória exata, implementadas com computação de alto desempenho para permitir uma análise de poder rigorosa.
4. Separação Empírica: Demonstra empiricamente que o ajuste de bondade de adequação marginal é insuficiente para auditoria de segurança, pois pode ser exatamente cego a falhas de estrutura conjunta que são detectáveis por estatísticas geométricas e de pares.

Os autores concluem que, embora a uniformidade conjunta total esteja fora de alcance para transcrições finitas, as "famílias de testemunhas estruturadas" permitem reivindicações de segurança significativas em relação a modos de falha de baixa dimensão específicos, desde que o tamanho da amostra de auditoria seja suficiente para o desvio específico sendo testado.