Algorithms, Complexity, and Entropy of the Bernard-Letac Fair-Sampling Construction

Imagina un mundo donde cada vez que lanzas una moneda esta está trucada, quizás cayendo más a menudo en cara que en cruz, o quizás favoreciendo un lado de forma tan extrema que el otro parece casi no aparecer nunca. Durante décadas, matemáticos e informáticos se han planteado una pregunta engañosamente simple: si solo tienes acceso a una fuente de aleatoriedad tan defectuosa y sesgada, ¿puedes generar un resultado perfectamente justo? ¿Puedes forzar el lanzamiento de una moneda justa, o una elección justa entre muchas opciones, utilizando nada más que un flujo de estas señales imperfectas y erráticas? La respuesta es sí, pero el camino hacia la equidad no es sencillo. Requiere un método que no conozca el sesgo, que funcione para cualquier tipo de sesgo y que se detenga en el momento justo para asegurar que el resultado sea verdaderamente aleatorio. Este es el problema del muestreo justo, un desafío que se sitúa en la intersección de la probabilidad, la teoría de números y la naturaleza misma de la información.

En un estudio reciente, Claude Gravel, investigador de la Universidad Metropolitana de Toronto, ha profundizado en una solución específica a este problema, propuesta originalmente en 1971 por Bernard y Letac. Si bien el trabajo original proporcionó una ingeniosa receta matemática para la equidad, dejó muchas preguntas prácticas sin respuesta. El artículo de Gravel transforma esa receta abstracta en un conjunto de algoritmos concretos y operativos, demostrando rigurosamente que funcionan y analizando exactamente cuánto esfuerzo requieren. El estudio revela que el coste de generar un resultado justo no es solo un número simple, sino que está profundamente ligado a la estructura oculta de la fuente sesgada. Al tratar el problema a través de la lente de la teoría de la información moderna, la investigación descubre fórmulas precisas sobre cuánto tiempo toma el proceso y muestra que la forma más eficiente de utilizar estas señales sesgadas depende de un tipo específico de "temperatura" matemática conocida como entropía.

El núcleo del método de Bernard–Letac es un proceso de acumulación. Imagina a un viajero caminando a través de una cuadrícula, dando pasos basados en los símbolos extraídos de la fuente sesgada. Si la fuente es una moneda, el viajero se mueve a la derecha por cara y hacia arriba por cruz. El viajero sigue caminando, registrando el número total de pasos en cada dirección, hasta que alcanza un punto de parada específico. Este punto de parada no se elige arbitrariamente; es una ubicación donde una compleja regla de conteo, que involucra cuántas formas diferentes podría haber llegado el viajero allí, resulta en un número que es perfectamente divisible por el número de resultados que deseas generar. Por ejemplo, si quieres una elección justa entre cinco opciones, el proceso se detiene en el momento en que el número de caminos posibles hacia la ubicación actual es un múltiplo de cinco. La magia del método es que, sin importar cómo esté trucada la moneda, los caminos que conducen a este punto de parada pueden dividirse en cinco grupos de tamaño exactamente igual. Esto asegura que, cuando el proceso se detenga, el resultado final sea perfectamente justo, a pesar de que la entrada fuera fuertemente sesgada.

El trabajo de Gravel comienza convirtiendo esta elegante idea matemática en cinco algoritmos informáticos distintos y paso a paso. Cada algoritmo está diseñado para manejar la tarea con garantías formales de corrección. El estudio proporciona instrucciones detalladas sobre cómo computar los conteos necesarios de manera eficiente, mostrando que el proceso puede llevarse a cabo sin necesidad de conocer el sesgo de antemano. Una de las contribuciones más significativas es el análisis de cuánto tarda este proceso. Los investigadores descubrieron que el número promedio de extracciones requeridas para detenerse no es un valor fijo, sino que depende de la distribución específica de la fuente sesgada. Derivaron una fórmula exacta para este tiempo promedio, la cual involucra un producto infinito de términos relacionados con las probabilidades de la fuente. Esta fórmula revela que el coste está gobernado por una familia de medidas llamadas entropías de Rényi, que capturan diferentes aspectos de la aleatoriedad de la fuente.

Un hallazgo sorprendente en el artículo es que una suposición simple e intuitiva sobre el coste es siempre errónea. Muchos podrían asumir que el coste está determinado aproximadamente por la medida más básica de aleatoriedad, conocida como entropía de Shannon. Sin embargo, el estudio demuestra que esta aproximación simple sobreestima consistentemente el coste real. El coste real es siempre menor que la suposición simple, pero la diferencia no es trivial. Los investigadores demostraron que, a medida que el número de resultados deseados crece mucho, el coste no se reduce al mínimo teórico predicho por la teoría de la información básica. En su lugar, se establece en un valor que es estrictamente superior al límite teórico. Esto significa que, si bien el método de Bernard–Letac es justo, no es perfectamente eficiente; inevitablemente desperdicia algo de la aleatoriedad disponible en la fuente. La cantidad de desperdicio depende de la distribución completa de la fuente, no solo de su entropía general.

El artículo también aborda la cuestión de cómo hacer que el proceso sea más rápido en un ordenador. El método original requiere una cantidad significativa de cálculo para determinar a qué grupo pertenece un camino específico, un paso que puede volverse muy lento a medida que aumenta el número de extracciones. Para el caso específico de generar un bit justo (una elección entre dos opciones) a partir de una fuente binaria, Gravel descubrió una forma de evitar por completo el pesado cálculo. Al analizar la estructura de los caminos, el investigador construyó una máquina simple con solo siete estados que puede determinar el resultado leyendo los dígitos binarios de las coordenadas del camino. Esta máquina reduce el esfuerzo computacional de un crecimiento cuadrático, que se vuelve inmanejable para números grandes, a un crecimiento casi lineal, haciendo que el proceso sea mucho más práctico para aplicaciones del mundo real.

El estudio explora además qué sucede cuando el número de resultados no es un número primo, sino uno compuesto, como seis o diez. En estos casos, la estructura matemática se vuelve mucho más irregular. Los investigadores encontraron que, para números compuestos, el proceso puede quedar atrapado en situaciones donde ciertos puntos de parada son inalcanzables, y los grupos de caminos no siempre son de igual tamaño. Esta irregularidad impide que los investigadores encuentren una fórmula simple de forma cerrada para el coste en estos casos, dejándolo como una pregunta abierta para trabajos futuros. El artículo sugiere que, para fines prácticos, podría ser mejor redondear al número primo más cercano para evitar estas complicaciones, aunque esto no ha sido probado rigurosamente.

En última instancia, esta investigación proporciona un mapa exhaustivo del terreno para el muestreo justo a partir de fuentes sesgadas. Confirma que la construcción de Bernard–Letac es un método robusto y correcto, pero también resalta sus limitaciones y las razones matemáticas precisas detrás de ellas. El trabajo demuestra que el coste de la equidad es una cantidad compleja, moldeada por los detalles intrincados de la distribución de la fuente. Al proporcionar fórmulas exactas, algoritmos eficientes y una comprensión clara de los compromisos involucrados, el estudio mueve el campo de la posibilidad abstracta a la implementación concreta, ofreciendo una comprensión más profunda de cómo la aleatoriedad puede ser extraída y purificada de fuentes imperfectas. Los hallazgos sugieren que, si bien podemos lograr una equidad perfecta, el precio que pagamos es una ineficiencia sutil e inevitable que es intrínseca a la naturaleza de la propia fuente sesgada.