Exact Online Rank Recycling in Floyd's Uniform Subset Sampler

Resumen Técnico: Reciclaje de Rango en Línea Exacto en el Muestreador de Subconjuntos Uniforme de Floyd

Planteamiento del Problema
El artículo aborda el problema del muestreo uniforme exacto de un subconjunto de tamaño $m$ de un conjunto $[n] = \{0, \dots, n-1\}$ sin reemplazo. Mientras que los algoritmos estándar (como Fisher–Yates) generan una secuencia ordenada, descartar el orden para devolver solo el conjunto desperdicia la entropía asociada con las $k!$ permutaciones de la muestra. En el modelo de bits aleatorios, un muestreador exacto debe consumir al menos $\log_2 \binom{n}{m}$ bits de entropía. El desafío radica en "reciclar" la aleatoriedad asociada con el ordenamiento (el factor de permutación) durante el proceso de muestreo en lugar de descartarla, asegurando que el estado reciclado permanezca independiente de la salida parcial y de las extracciones futuras.

Metodología
El artículo propone una modificación al muestreador de subconjuntos de Floyd que integra un mecanismo de "reciclaje de rango en línea". La metodología central se basa en una factorización combinatoria específica:

1. Biyectión Local de Ronda: Los autores demuestran que en cualquier ronda $r$ del muestreador de Floyd, la transición de un estado previo $(S, T)$ a un nuevo estado $(S', D)$ es una biyección. Aquí, $S$ es un $(r-1)$-subconjunto, $T$ es un dibujo aleatorio de $[j+1]$, $S'$ es el subconjunto actualizado y $D$ es el rango de base cero de $T$ dentro de $S'$.
2. Invariante de Independencia: Esta biyección establece que $S'$ (el subconjunto actualizado) y $D$ (el dígito de rango) son estadísticamente independientes. Además, $D$ está distribuido uniformemente sobre $[r]$.
3. Mecanismo de Reciclaje: Debido a que $D$ es independiente del conjunto retenido $S'$, puede integrarse inmediatamente en el estado aleatorio uniforme residual (el "pool") utilizando una operación de fusión estándar ($Z, D \to rZ + D$). Esto permite que la entropía del ordenamiento se preserve y se reutilice para rondas subsecuentes sin sesgar la salida.
4. Implementación: El algoritmo utiliza un árbol de estadísticas de orden para mantener el subconjunto, soportando membresía, inserción y consultas de rango en $O(\log k)$ de tiempo. La fase de muestreo se ejecuta en $O(k \log k)$ de tiempo con $O(k)$ de espacio auxiliar, donde $k = \min(m, n-m)$.

Contribuciones Clave
El artículo realiza cuatro contribuciones específicas:

1. Biyección de Producto Explícita: Expresa cada ronda del muestreador de Floyd como una biyección de producto explícita $(S, T) \leftrightarrow (S', D)$, identificando el dígito de rango $D$ como la coordenada específica que puede ser reciclada.
2. Prueba de Exactitud e Independencia: Utiliza esta biyección para demostrar que el muestreador devuelve un subconjunto perfectamente uniforme y que el subconjunto parcial permanece independiente del estado aleatorio residual después de cada paso de reciclaje.
3. Contraejemplo al Reciclaje Ingenuo: Proporciona un contraejemplo finito ($n=6, k=3$) que demuestra que el reciclaje inmediato de rango en un arreglo parcial de Fisher–Yates es inválido. En Fisher–Yates, el sufijo no seleccionado retiene un ordenamiento correlacionado, lo que hace que los dígitos intermedios no sean seguros para reutilizar. Esto resalta que la factorización global (conjunto $\times$ permutación) no justifica el reciclaje en línea sin verificar la independencia local.
   4.Separación de Preocupaciones: El trabajo separa la transformación combinatoria sin pérdida (recuperación del factor completo de $k!$) de la implementación del estado de rango acotado. Acota la pérdida de entropía debido a la aritmética de palabra finita o al rechazo por ramificación de forma separada de la lógica combinatoria.

Resultados y Validación

• Teóricos: Se demuestra que la capa combinatoria es sin pérdida, recuperando exactamente el factor completo del espacio de estados de $k!$. El factor de espacio de estados neto consumido es exactamente $\binom{n}{m}$.
• Enumeración de Estado Finito: La implementación fue verificada exhaustivamente para todos los $n \le 8$ y $0 \le m \le n$. Estas pruebas confirmaron que cada subconjunto ocurre con la multiplicidad correcta y que cada par salida-residuo es único, verificando la estructura de producto cartesiano.
• Traza a Gran Escala: Para $n=30,000$ y $m=20,000$ (muestreando 10,000 elementos), una traza de contabilidad de entropía mostró que el algoritmo lee 3,449 bytes de entropía de origen, retiene un estado con $\approx 50.8$ bits de entropía y deja solo $\approx 5.76 \times 10^{-7}$ bits sin contabilizar. La "eficiencia de salida más pool" se calculó en $99.9999999979\%$.
• Complejidad: El algoritmo logra $O(k \log k)$ de tiempo y $O(k)$ de espacio. Los autores señalan explícitamente que esto no es una pretensión de superioridad de tiempo de ejecución sobre otros muestreadores, ya que los costos de representación (por ejemplo, ordenar la salida) dominan en muchos escenarios prácticos.

Significancia y Reivindicaciones
El artículo afirma su significancia no en la invención del reciclaje de aleatoriedad o el muestreo de Floyd, sino en la identificación de una factorización local de ronda que permite un reciclaje inmediato y seguro del dígito de ordenamiento.

• Modestia: Los autores declaran explícitamente que no reclaman novedad para el reciclaje de aleatoriedad, el muestreo de Floyd o la generación eficiente de entropía como campos generales. No reclaman superioridad en tiempo de ejecución.
• Percepción Central: La contribución principal es la demostración de que la transición de Floyd elimina el "estado oculto" (el ordenamiento del arreglo candidato) que afecta a Fisher–Yates, permitiendo así una prueba de independencia local. Esto permite recuperar exactamente el factor completo de $k!$ sin recurrir a la aritmética de coeficientes binomiales o a la lógica de ranking global.
• Restricción: El trabajo ilustra una restricción general sobre el reciclaje en línea: una coordenada redundante en la salida final no es necesariamente segura para reutilizar durante la computación, a menos que sea independiente de todos los estados internos relevantes para el futuro.