Fast Algorithms for Exact Confidence Intervals in Randomized Experiments with Binary Outcomes

Resumen Técnico: Algoritmos Rápidos para Intervalos de Confianza Exactos en Experimentos Aleatorios con Resultados Binarios

1. Planteamiento del Problema

El artículo aborda un desafío fundamental en el análisis estadístico de experimentos aleatorios con resultados binarios (ej. éxito/fracaso, compra/no compra): la construcción de intervalos de confianza exactos para el efecto promedio del tratamiento (ATE) en poblaciones finitas.

• Limitaciones de los métodos actuales: Los métodos clásicos suelen basarse en aproximaciones asintóticas (Teorema del Límite Central), las cuales pueden ser inexactas con tamaños de muestra pequeños, distribuciones sesgadas o efectos heterogéneos.
• El obstáculo computacional: Los intervalos de confianza exactos basados en inferencia de aleatorización requieren "invertir" pruebas de aleatorización sobre todas las configuraciones compatibles de resultados potenciales faltantes. Dado que el espacio de búsqueda crece exponencialmente ($2^n$), las implementaciones ingenuas son computacionalmente prohibitivas.
• Estado del arte previo: Para diseños de aleatorización completa balanceada, los procedimientos más eficientes conocidos requieren $O(n \log n)$ pruebas de aleatorización (Aronow et al., 2023). Para diseños estratificados (como pares apareados), la complejidad era aún mayor, requiriendo hasta $O(n 2^n)$ pruebas en enfoques anteriores.

2. Metodología Propuesta

El autor propone algoritmos que aprovechan la estructura de independencia de ciertos diseños de asignación para reducir drásticamente el número de pruebas necesarias.

A. Diseño de Bernoulli Balanceado y Diseño de Pares Apareados:

• Estrategia de Búsqueda Binaria: Se demuestra que la función del valor $p$ máximo ($p_{max}$) es monótona en relación con el candidato del ATE ($\tau_0$) a ambos lados del estadístico observado. Esto permite utilizar una búsqueda binaria sobre el conjunto de candidatos finitos para identificar el intervalo de confianza, reduciendo el número de evaluaciones de $p_{max}$ a $O(\log n)$.
• Optimización del Valor $p$ Máximo ($p_{max}$): Para un candidato $\tau_0$ fijo, el cálculo de $p_{max}$ implica encontrar la configuración de resultados potenciales que maximice el valor $p$ (haciendo que el estadístico de prueba parezca menos extremo).
  • El autor demuestra que bajo diseños de Bernoulli balanceado y pares apareados, la distribución del estadístico de prueba centrado puede expresarse como una suma de variables aleatorias independientes (Rademacher y media-Rademacher).
  • Se prueba una propiedad de unimodalidad y monotonía en la distribución de esta suma. Esto implica que el valor $p$ máximo se alcanza en uno de los dos puntos de frontera del conjunto de vectores de conteo de resultados factibles.
  • Resultado clave: En lugar de buscar entre $O(n)$ o $O(n^4)$ configuraciones, solo se necesitan como máximo 2 pruebas de aleatorización para calcular $p_{max}(\tau_0)$.
• Cálculo Exacto de la Cola de Probabilidad: Para evaluar las pruebas de aleatorización sin simulaciones de Monte Carlo, el algoritmo calcula las probabilidades de cola de una distribución binomial de Poisson (o sumas de variables Rademacher ponderadas) utilizando la Transformada Rápida de Fourier (FFT). Esto permite un cálculo exacto en tiempo $O(n \log n)$.

B. Diseño General de Bernoulli (No Balanceado):

• Para el caso general donde la probabilidad de asignación $p \in (0,1)$ no es 0.5, el autor extiende el método reutilizando resultados de pruebas de aleatorización para configuraciones de resultados "cercanas", logrando una complejidad de $O(n^2)$ pruebas.

3. Contribuciones Clave y Teoremas Principales

1. Reducción Exponencial de Pruebas (Teorema 1.1):

   • Bajo diseños de Bernoulli balanceado o pares apareados, el intervalo de confianza exacto se puede construir utilizando a lo sumo $8 \log_2 n$ pruebas de aleatorización.
   • Esto representa una reducción exponencial respecto a la fuerza bruta y una mejora significativa frente a los $O(n \log n)$ requeridos para la aleatorización completa balanceada.

2. Límite Inferior de Información (Teorema 1.2):

   • Se establece un límite inferior de información: cualquier algoritmo determinista que construya estos intervalos exactos debe realizar al menos $\Omega(\log n)$ pruebas en el peor de los casos.
   • Esto demuestra que la tasa logarítmica lograda por el algoritmo propuesto es óptima.

3. Complejidad Computacional Total (Teorema 1.3):

   • La construcción completa del intervalo de confianza bajo Bernoulli balanceado o pares apareados se realiza en tiempo $O(n \log^2 n)$.
   • Esto es determinista y evita la incertidumbre de los métodos de Monte Carlo.

4. Separación de Diseños:

   • El trabajo revela una separación nítida en la complejidad computacional: los diseños con estructura de independencia (Bernoulli, Pares Apareados) son computacionalmente mucho más eficientes para inferencia exacta que el diseño de aleatorización completa balanceada, debido a la simetría y la independencia de las asignaciones.

5. Extensión a Pares Apareados:

   • Resuelve una pregunta abierta de la literatura (Aronow et al., 2023) sobre cómo generalizar las construcciones rápidas a diseños de pares apareados, demostrando que la independencia entre pares permite aplicar la misma lógica de optimización que en el diseño de Bernoulli.

4. Resultados Empíricos y Simulaciones

El autor valida los algoritmos mediante simulaciones comparativas:

• Precisión vs. Fuerza Bruta: Para tamaños de muestra pequeños, el algoritmo propuesto produce los mismos intervalos exactos que la fuerza bruta, pero con un número de pruebas drásticamente menor (ej. 7-9 pruebas frente a miles o millones).
• Comparación con Wald (Aproximación Normal):
  • En escenarios de resultados escasos (donde la distribución es altamente discreta y no normal), los intervalos de Wald tienden a tener una cobertura inferior (sub-estimación).
  • Los intervalos exactos propuestos garantizan la cobertura deseada ($1-\alpha$) para cualquier tamaño de muestra y configuración de resultados, aunque pueden ser ligeramente más conservadores (intervalos más anchos) en casos de datos muy escasos.
• Rendimiento: En una máquina estándar, el algoritmo para Bernoulli balanceado con $n=1000$ tarda menos de 1.5 minutos en 10,000 simulaciones. Para pares apareados, el tiempo es mayor (aprox. 2 horas) debido a la necesidad de resolver programas lineales enteros (ILP) de 9 variables para encontrar los vectores de conteo óptimos, pero sigue siendo factible.

5. Significado e Impacto

Este trabajo es significativo por varias razones:

1. Viabilidad Práctica: Hace que la inferencia causal exacta (sin suposiciones asintóticas) sea computacionalmente viable para experimentos de escala moderada a grande, algo que antes se consideraba prohibitivo.
2. Optimalidad Teórica: Establece que la velocidad logarítmica es el límite teórico, cerrando la brecha entre la complejidad inferior y superior.
3. Diferenciación de Diseños: Ilustra cómo la elección del diseño experimental (Bernoulli/Pares vs. Aleatorización Completa) tiene implicaciones directas no solo en la precisión estadística, sino también en la complejidad computacional de la inferencia exacta.
4. Herramienta Disponible: El autor proporciona una implementación en Python, facilitando la adopción de estos métodos en la práctica de la ciencia de datos y la investigación médica/económica.

En resumen, el artículo transforma un problema de optimización combinatoria intratable en un problema eficiente mediante el aprovechamiento inteligente de las propiedades de simetría e independencia de diseños experimentales específicos, utilizando técnicas de transformada de Fourier y búsqueda binaria.