Bonsai: A class of effective methods for independent sampling of graph partitions

Resumen Técnico: Bonsai para el Muestreo Independiente de Planos de Distritos

1. El Problema

En el contexto del redistritamiento electoral (redistricting), los tribunales y los investigadores utilizan "ensembles" (conjuntos) de miles o millones de mapas aleatorios para determinar si un mapa electoral aprobado es sesgado (gerrymandering).

• Limitaciones de los métodos actuales: La mayoría de los algoritmos existentes, como ReCom y Forest ReCom, se basan en Cadenas de Markov. Estos métodos generan mapas secuenciales modificando fronteras entre distritos.
• Desafíos teóricos y prácticos:
  • Ergodicidad y Mezcla (Mixing): No se sabe con certeza si estas cadenas son ergódicas (capaces de visitar todos los estados posibles) ni cuánto tardan en mezclarse (tiempo de mezcla). En algunos casos, se ha demostrado que ReCom mezcla lentamente o no es ergódico.
  • Autocorrelación: Debido a la dependencia secuencial, el "tamaño de muestra efectivo" es mucho menor que el tamaño de la muestra real, requiriendo cadenas extremadamente largas para lograr precisión estadística.
  • Paralelización: Los métodos basados en cadenas son difíciles de paralelizar masivamente.

El objetivo del artículo es desarrollar métodos que permitan muestrear planos de distritos de forma independiente, evitando los problemas de las cadenas de Markov.

2. Metodología: El Algoritmo "Bonsai"

Los autores proponen una clase de algoritmos llamados Bonsai (inspirado en el arte japonés de dar forma a los árboles) que construyen particiones de grafos mediante un enfoque recursivo y de "corte" (cutting), en lugar de un enfoque de "recombinación" (recombining).

Conceptos Clave:

• Grafo de Entrada: Un grafo $G$ donde los nodos son distritos electorales (precintos) y las aristas representan adyacencia.
• Árbol de Recubrimiento (Spanning Tree): Se utiliza un árbol de recubrimiento uniforme (o mínimo) del grafo como estructura base.
• Corte Validado: Se identifican aristas en el árbol cuya eliminación divide el subgrafo en componentes con poblaciones que cumplen con los requisitos de equilibrio poblacional.

Algoritmos Propuestos:

1. Complete Cut (Corte Completo): Un algoritmo simple que busca un árbol de recubrimiento que pueda ser cortado completamente en $k$ distritos de tamaño exacto.
   • Problema: En grafos grandes, la probabilidad de encontrar tal árbol es extremadamente baja (cercana a cero), lo que lo hace ineficiente en la práctica.
2. Bonsai (Algoritmo Principal): Una mejora sobre "Complete Cut" que no espera a encontrar un árbol perfectamente cortable de una sola vez.
   • Funcionamiento Recursivo:
     1. Se genera un árbol de recubrimiento en el grafo actual.
     2. Se identifican todas las aristas de corte válidas (que dividen la población en múltiplos enteros del tamaño ideal).
     3. Se realiza un corte (o múltiples cortes simultáneos) para dividir el grafo en subgrafos más pequeños.
     4. El proceso se repite recursivamente en cada subgrafo hasta que todos los componentes tienen el tamaño de un solo distrito.
   • Retroceso (Backtracking): Si el algoritmo se queda atascado (no puede encontrar cortes válidos en una subdivisión), retrocede al paso anterior, descarta el corte problemático y genera un nuevo árbol para intentar una partición diferente.
   • Equilibrio Imperfecto ($\epsilon > 0$): Para casos donde se permite una desviación poblacional, el algoritmo utiliza una función multiplicadora de tolerancia ($\phi$) para definir qué cortes son "válidos" y una estrategia para elegir el "mejor" corte (generalmente el que maximiza el equilibrio).

Distribución de Muestreo:

• Para el caso de equilibrio perfecto ($\epsilon = 0$), los autores proporcionan una descripción explícita de la distribución de probabilidad de la que muestrea Bonsai. Esta distribución es proporcional al producto de los números de árboles de recubrimiento de los distritos y del grafo cociente.
• Para el caso imperfecto, se garantiza que cualquier plano válido tiene una probabilidad no nula de ser generado (bajo ciertas condiciones de la función $\phi$), lo que asegura la irreducibilidad teórica.

3. Contribuciones Clave

1. Muestreo Independiente: Bonsai genera cada plano de forma independiente, eliminando la necesidad de calcular tiempos de mezcla y evitando la autocorrelación.
2. Paralelización Masiva: Al no depender de cadenas secuenciales, el algoritmo se puede ejecutar en paralelo de manera trivial, acelerando drásticamente la generación de ensembles.
3. Eficiencia Estadística: El tamaño de muestra efectivo es igual al tamaño de muestra real, lo que permite lograr la misma precisión estadística con muestras mucho más pequeñas en comparación con ReCom.
4. Marco Teórico: Se establece una descripción matemática precisa de la distribución subyacente en el caso de equilibrio perfecto y se demuestra la capacidad de explorar todo el espacio de soluciones válidas.

4. Resultados Empíricos

Los autores compararon dos variantes de Bonsai (usando árboles de recubrimiento uniformes y árboles de recubrimiento mínimos) contra cuatro variantes de ReCom (combinando tipos de árboles y estrategias de selección de pares).

Datos de Prueba:

• Grafos de Rejilla (Grids): 7x7 y 50x50 con diferentes números de distritos.
• Datos Reales:
  • Pensilvania (2010): 18 distritos del Congreso ($\epsilon = 0.01$).
  • Carolina del Norte (2010): 99 distritos de la Cámara Estatal ($\epsilon = 0.05$).

Hallazgos:

• Estadísticas de Compacidad: Las estadísticas de los ensembles generados por Bonsai (número de aristas cortadas, perímetros de distritos) se sitúan entre las de las dos variantes principales de ReCom (selección de arista de corte vs. selección de par de distritos), tendiendo a ser más cercanas a la variante de selección de par de distritos.
• Equidad Partidista: En los análisis de votación (Pensilvania 2016 y Carolina del Norte 2016), las distribuciones de votos por distrito generadas por Bonsai son extremadamente similares a las de ReCom.
• Robustez: Los resultados sugieren que muchas estadísticas a nivel de ensemble son robustas frente a diferencias metodológicas sustanciales dentro de la familia de métodos basados en árboles de recubrimiento.

5. Significado e Impacto

El algoritmo Bonsai ofrece una alternativa práctica y matemáticamente transparente a los métodos basados en cadenas de Markov para el análisis de redistritamiento.

• Ventaja Legal y Científica: Al eliminar las dudas sobre la ergodicidad y los tiempos de mezcla, Bonsai proporciona una base más sólida para los argumentos legales sobre sesgo electoral.
• Herramienta de Validación: La capacidad de generar ensembles independientes permite la validación cruzada de resultados obtenidos con otros algoritmos (como ReCom), fortaleciendo la confianza en los análisis de mapas electorales.
• Eficiencia: La capacidad de paralelización y la reducción del tamaño de muestra necesario hacen que el análisis de grandes conjuntos de datos sea más rápido y computacionalmente viable.

En conclusión, Bonsai representa un avance significativo en la metodología de simulación de mapas electorales, combinando rigor teórico con eficiencia computacional práctica.