Resumen Técnico: Auditoría de la Aleatoriedad Combinatoria a partir de Transcripciones Finitas

Planteamiento del Problema

Los servicios de aleatoriedad pública, como las loterías, los faros de aleatoriedad (randomness beacons) y los generadores de números pseudoaleatorios, producen transcripciones finitas de extracciones combinatorias (selección de $k$ etiquetas de un total de $m$ sin reemplazo). El objetivo de seguridad es auditar estas transcripciones para detectar manipulaciones o fallos de implementación. Sin embargo, existe una barrera fundamental de información teórica: para un espacio de transcripción de tamaño $N = \binom{m}{k}$, probar la uniformidad conjunta arbitraria requiere un tamaño de muestra que escala como $\Theta(\sqrt{N}/\epsilon^2)$. Para parámetros de lotería realistas (por ejemplo, EuroMillions 5/50 o 6/90), el tamaño del soporte $N$ es tan grande que las transcripciones históricas finitas no pueden certificar la uniformidad conjunta completa contra un adversario sin restricciones. Además, una distribución puede preservar todas las probabilidades marginales de un solo número mientras altera significativamente las probabilidades de pares, los solapamientos seriales o la estructura geométrica de las extracciones, lo que hace que las pruebas marginales estándar sean ineficaces.

Metodología

Los autores proponen un marco de auditoría "agnóstico al generador" que desplaza el enfoque de la uniformidad conjunta arbitraria hacia la prueba contra familias de alternativas estructuradas con nombre. Estas familias modelan modos de fallo específicos y de baja dimensión, tales como etiquetas calientes (hot labels), acoplamientos de pares, pegajosidad serial, bloques agrupados y repulsión de bandas.

Marco Estadístico

La batería de auditoría mapea las extracciones al hipersimplex y evalúa estadísticas de calibración nula exacta-combinatoria:

1. Chi-cuadrado Marginal: Prueba los conteos de una sola coordenada.
2. Máximos de Pares (Pair Maxima): Evalúa la desviación máxima en las probabilidades de pares.
3. Solapamiento Serial: Analiza el tamaño de la intersección entre extracciones consecutivas utilizando momentos hipergeométricos.
4. Discrepancia de Caja Anclada (Anchored-Box Discrepancy): Mide la desviación de las funciones de distribución acumulativa sobre un conjunto calibrado de umbrales.
5. Geometría $H_0$/MST: Proyecta vectores de incidencia y analiza el espectro de aristas del árbol de expansión mínima euclidiana (MST).

Calibración e Implementación

Para manejar la naturaleza discreta del problema y evitar aproximaciones continuas, los autores implementan una calibración de Monte Carlo de la nulidad exacta.

• Generación de la Nulidad Exacta: Una implementación en CUDA utiliza programación dinámica para calcular las probabilidades exactas de las extracciones ordenadas sin depender de aproximaciones de uniformidad continua.
• Cálculo de P-valor: Los p-valores de rango aleatorizado se derivan de replicaciones de la nulidad exacta i.i.d. generadas con los mismos parámetros $(m, k, n)$ que la muestra observada.
• Hardware: Los experimentos utilizan implementaciones de CPU y aceleración de GPU (NVIDIA RTX 5090 y A100 SXM4) para realizar hasta 300,000 replicaciones nulas y 60,000 replicaciones alternativas por condición.

Modelos Alternativos

El estudio introduce cinco distribuciones alternativas controladas para probar la potencia de las estadísticas:

• Marginal Caliente (Hot-marginal): Pesos de muestreo multiplicativos sobre un subconjunto.
• Inyección de Pares (Pair-injection): Inyección de pares fijos con probabilidad $\rho$.
• Agrupación de Bloques (Block-cluster): Bloques enteros de números devueltos con probabilidad $\rho$ (preservando las marginales de un solo número).
• Repulsión de Bandas (Band-repulsion): Un número seleccionado de cada uno de $k$ bandas iguales con probabilidad $\rho$ (preservando las marginales de un solo número).
• Pegajosidad Serial (Serial-stickiness): Copia de una etiqueta de la extracción anterior con probabilidad $\rho$.

Resultados Clave

1. Auditoría del Mundo Real (EuroMillions)

Los autores auditaron 1,956 extracciones principales de EuroMillions (2004–2026).

• Resultado: Ninguna estadística sobrevivió al ajuste de falso descubrimiento. El valor q mínimo de Benjamini–Hochberg fue 0.279.
• Conclusión: La traza de EuroMillions cae dentro del rango de referencia calibrado, mostrando evidencia de no presentar las desviaciones estructuradas probadas.

2. Puntos Ciegos de Preservación Marginal

Los experimentos de GPU demostraron que las pruebas marginales unidimensionales son ciegas a estructuras conjuntas específicas:

• Agrupación de Bloques (Fuerza 0.04): Con $n=1,956$, la estadística pair max-z alcanzó una potencia de detección de 0.638, mientras que el chi-cuadrado marginal se mantuvo en su tamaño nominal de 0.051.
• Repulsión de Bandas (Fuerza 0.08): La estadística de caja anclada alcanzó una potencia de 0.741, mientras que el chi-cuadrado marginal se mantuvo en 0.051.
• Implicación: Una distribución puede parecer perfectamente aleatoria en términos de frecuencia de un solo número mientras exhibe anomalías estructurales significativas detectables solo mediante estadísticas geométricas o de pares.

el 3. Frontera del Tamaño de la Muestra

El estudio cuantifica los tamaños de muestra requeridos para detectar modos de fallo específicos:

• Para la agrupación de bloques con fuerza 0.04, la potencia de detección aumentó de 0.638 con $n=1,956$ a 0.999 con $n=5,000$.
• Para la repulsión de bandas con fuerza 0.04, la potencia de la caja anclada aumentó de 0.186 con $n=1,956$ a 1.000 con $n=20,000$.
• Esto confirma que, si bien la uniformidad arbitraria es inabordable, las desviaciones estructuradas específicas se vuelven detectables a medida que aumenta la longitud de la transcripción, siempre que la auditoría apunte a la familia estructural correcta.

4. Escalabilidad de Formato

Los experimentos en formatos más grandes (6/54 y 6/90) confirmaron que el patrón se mantiene: las pruebas marginales permanecen cerca de su tamaño nominal para las alternativas estructuradas, mientras que las estadísticas geométricas y de pares ganan potencia. Para la agrupación de bloques en 6/90 con $n=5,000$, el pair max-z alcanzó una potencia de 1.000.

Significado y Reivindicaciones

El artículo afirma establecer una frontera de auditabilidad de caja negra para la aleatoriedad combinatoria pública. Sus principales contribuciones son:

1. Límite Teórico: Caracteriza formalmente la imposibilidad de probar la uniformidad conjunta arbitraria para grandes espacios combinatorios con transcripciones finitas, citando los límites inferiores de Paninski.
2. Alternativa Constructiva: Propone un modelo de seguridad viable basado en la auditoría de familias estructuradas con nombre en lugar de desviaciones arbitrarias. Este enfoque evita la barrera de complejidad de muestra de $\sqrt{N}$ al depender de la brecha del testigo y el número de familias de prueba ($L$).
3. Herramientas Metodológicas: Proporciona un conjunto de estadísticas agnósticas al generador calibradas contra la nulidad combinatoria exacta, implementadas con computación de alto rendimiento para permitir un análisis de potencia riguroso.
4. Separación Empírica: Demuestra empíricamente que el ajuste de bondad de ajuste marginal es insuficiente para la auditoría de seguridad, ya que puede ser exactamente ciego a fallos de estructura conjunta que son detectables por estadísticas geométricas y de pares.

Los autores concluyen que, si bien la uniformidad conjunta completa está fuera del alcance para transcripciones finitas, las "familias de testigos estructurados" permiten realizar afirmaciones de seguridad significativas respecto a modos de fallo de baja dimensión, siempre que el tamaño de la muestra de auditoría sea suficiente para la desviación específica que se está probando.