Entropic Generation of Binary Words

Planteamiento del Problema
El artículo aborda la generación uniforme de palabras binarias de longitud $n$ con un peso de Hamming fijo $k$ (equivalente al muestreo de $k$-subconjuntos de $n$ elementos). Si bien la complejidad temporal de tales generadores ha sido ampliamente estudiada, los autores se centran en el consumo de bits aleatorios como un recurso crítico, particularmente en contextos que dependen de generadores de números aleatorios verdaderos (TRNG) por hardware, donde la aleatoriedad es costosa.

El límite inferior informacional para generar una muestra uniforme de un espacio de estados de tamaño $\binom{n}{k}$ es $H = \log_2 \binom{n}{k}$ bits. El objetivo es diseñar algoritmos donde el consumo esperado de bits aleatorios sea asintóticamente cercano a esta entropía $H$. El artículo apunta específicamente al "régimen de dispersión polinómica", definido por $k \sim n^\beta$ para un $\beta \in (0, 1)$ fijo. Los métodos existentes suelen bifurcarse: los embarullamientos (shuffles) parciales de Fisher-Yates son eficientes para entradas altamente dispersas ($k \ll n$), mientras que las adaptaciones del algoritmo MERGE funcionan bien para entradas más densas ($k = \Omega(n^{2/3+\epsilon})$). Sin embargo, ningún algoritmo previo logró simultáneamente una complejidad de tiempo lineal $O(n)$ y un costo entrópico casi óptimo en el régimen intermedio de dispersión donde $\beta \in (0, 2/3]$.

Metodología: Reciclaje de Bits Aleatorios
La innovación central es un paradigma de "reciclaje de bits aleatorios". Los autores observan que los métodos de generación estándar, como el embarullamiento de Fisher-Yates, generan implícitamente estructuras internas (como permutaciones) que se descartan después de que se forma el objeto combinatorio. Este proceso "desperdicia" entropía.

La metodología propuesta invierte el proceso de generación estándar:

1. Deconstrucción: En lugar de solo consumir bits para construir una estructura, el algoritmo extrae bits aleatorios independientes de la estructura generada (o de los estados intermedios) mediante la reversión conceptual del proceso generativo.
2. Reciclaje: Estos bits extraídos son luego reutilizados ("reciclados") para alimentar los pasos de generación subsiguientes, reduciendo el consumo neto de bits aleatorios frescos.

El artículo detalla dos mecanismos principales para esto:

• Palabras Binarias Balanceadas: Para palabras balanceadas ($k=n/2$), los autores revierten el procedimiento de "Merge Balanceado" (Balanced Merge). Al muestrear la condición de agotamiento (modelada por una distribución de Banach Matchbox) y revertir los pasos de inserción de Fisher-Yates, extraen una secuencia de bits uniformes independientes.
• Deconstrucción de Permutaciones: Para permutaciones generales, el algoritmo divide recursivamente una permutación de tamaño $n$ en una palabra binaria balanceada y dos permutaciones más pequeñas. La palabra binaria balanceada se deconstruye para obtener bits, y el proceso recursa sobre las sub-permutaciones. Esto logra una tasa de extracción de $n \log_2 n - O(n)$ bits de una permutación de tamaño $n$.

Contribuciones Clave y Algoritmos
El artículo presenta un nuevo generador de palabras binarias uniformes que cierra la brecha entre la complejidad de tiempo lineal y el costo entrópico casi óptimo en el régimen de dispersión polinómica.

1. Fisher-Yates Distinguible con Deconstrucción:
   Para generar una palabra con peso $k$, los autores inicializan el arreglo con identificadores distintos $1, \dots, k$ en lugar de elementos indistinguibles. Realizan un embarullamiento parcial de Fisher-Yates. Los índices del arreglo resultante definen la palabra binaria, mientras que la secuencia de elementos no nulos forma una permutación uniforme de tamaño $k$. Esta permutación es entonces alimentada al algoritmo DeconstructPermutation para recuperar la entropía "desperdiciada" ($\log_2 k!$ bits).

• Resultado: Esto produce un algoritmo de primer orden entrópico. El consumo neto de bits es $\log_2 \binom{n}{k} + O(k)$. Dado que $O(k) = o(\log_2 \binom{n}{k})$ en el régimen objetivo, el consumo coincide asintóticamente con el límite inferior de la entropía. Su tiempo de ejecución es $O(n)$.

2. Reciclaje en Cadena para la Generación Casi Entrópica:
   Para lograr la generación casi entrópica (donde el consumo es $(1+\epsilon)H$ para cualquier $\epsilon > 0$), los autores proponen un enfoque iterativo (Algoritmo 5: l-ChainedRecyclingFY).

• La generación se divide en $l+1$ pasos. En cada paso $i$, se inserta un subconjunto de $k_i$ elementos usando Fisher-Yates.
• La permutación formada por estos elementos es inmediatamente deconstruida para extraer bits aleatorios.
• Estos bits reciclados se utilizan para financiar las inserciones del siguiente paso ($i+1$).
• Al ajustar el parámetro $l$, el sobreconsumo multiplicativo de bits aleatorios puede acotarse arbitrariamente cerca de 1.
• Resultado: Este algoritmo se ejecuta en $O(n)$ de tiempo y logra una complejidad de bits de $\frac{1-\beta}{1-\beta^{l+1}} k \log_2 n + O(k)$, la cual se aproxima al límite de la entropía a medida que $l$ aumenta.

Resultados

• Complejidad Temporal: Los algoritmos propuestos se ejecutan en un tiempo esperado lineal, $O(n)$, en el régimen de dispersión polinómica ($k \sim n^\beta, \beta \in (0,1)$).
• Complejidad de Bits:
  • El método de inserción distinguible es de primer orden entrópico: el consumo es $\log_2 \binom{n}{k} + O(k)$.
  • El método de reciclaje en cadena es casi entrópico: para cualquier $\epsilon > 0$, el algoritmo puede configurarse para consumir $(1+\epsilon)\log_2 \binom{n}{k} + o(\log_2 \binom{n}{k})$ bits.
• Optimalidad: Los algoritmos son casi óptimos en términos de consumo de bits aleatorios, coincidiendo estrechamente con el límite inferior de la entropía de Shannon derivado de la teoría de la información.

Significancia y Reivindicaciones
El artículo afirma proporcionar el primer algoritmo que alcanza simultáneamente la complejidad de tiempo lineal y un costo entrópico casi óptimo para la generación de palabras binarias de peso de Hamming fijo en el régimen de dispersión polinómica.

Los autores enfatizan que tratar los bits aleatorios como un recurso escaso proporciona un marco analítico más preciso que el análisis de tiempo de ejecución estándar. Postulan que el paradigma de "deconstrucción de entropía" y reciclaje es generalizable. Específicamente, señalan que hay trabajos en curso para adaptar este mecanismo para reciclar la entropía "desperdiciada" de estructuras rechazadas en muestreadores de tipo Boltzmann para la generación de tamaño exacto. El artículo concluye que este enfoque permite la generación entrópica eficiente en grandes lotes (mediante la agrupación de bits recuperados) o la generación casi entrópica para instancias únicas (vía el encadenamiento recursivo).