Simular un dado de 7 caras a partir de uno de 5

A.S.: Sí, aparentemente el singular de ‘dado’ es ‘die’. 😉

Ha circulado por Internet una complicada tarea de programación que, como habrás adivinado por mi intento de título pragmático, se puede formalizar de la siguiente manera:

Dada una función que devuelve un número uniformemente aleatorio entre 1 y 5 (inclusive), diseña una función que devuelva un número uniformemente aleatorio entre 1 y 7 (inclusive).

Si la intersección de algoritmos y estadística es lo tuyo, ¡no dudes en intentarlo! Un reto adicional es hacer que tu algoritmo esté acotado en el tiempo. Me pareció un ejercicio divertido, sólo para darme cuenta de que hay limitaciones fundamentales en juego aquí.

Por supuesto, un dado aquí significa un generador aleatorio perfectamente uniforme que existe sólo en teoría. Los dados del mundo real se rigen por las leyes naturales y las imperfecciones del entorno de tal manera que sólo son una aproximación (aunque buena) de este modelo abstracto.

Una solución sin límites

Veamos una familia de algoritmos sin límites. Para crear un generador aleatorio que tenga al menos 7 resultados, tendremos que lanzar el dado de 5 caras al menos dos veces. Al lanzarlo dos veces se crean 5^2=25 resultados posibles, y aunque esto no es un factor de 7, podemos asignar los primeros 21 resultados a 7 grupos de igual tamaño 3. Sin embargo, si terminamos en uno de los 4 resultados restantes, el procedimiento debe reiniciarse. No podemos simplemente asignar cualquiera de estos 4 estados finales desafortunados a una salida, ya que esto estropearía la propiedad de aleatoriedad uniforme.

En el gráfico anterior, los círculos representan ‘estados’ de nuestro programa, y el texto dentro es el valor más reciente del dado lanzado. Los recuadros verdes representan la salida que asignamos en función del estado final (= después de lanzar el dado dos veces). El 84% de las veces, obtenemos una salida después de dos tiradas y el algoritmo termina. Como puedes ver, un bucle está presente y hace que el algoritmo sea ilimitado. Esto significa que para cada número entero, por muy grande que sea, hay una pequeña pero no nula probabilidad de que el número total de tiradas supere esa cantidad para calcular un valor de salida. Por lo tanto, las aplicaciones en tiempo real con estrictos requisitos de tiempo están fuera de la cuestión, a menos que esté dispuesto a hacer concesiones en la precisión estadística del algoritmo.

Una variante de esta solución inicialmente tira hasta tres dados antes de reiniciar: esto crea 5^3=125 estados finales, y podemos asignar como máximo 119 de ellos a 7 grupos de igual tamaño 17. Ahora, hay un 95,2% de probabilidades de terminar después de un máximo de tres tiradas. Nótese que tenemos que tirar menos veces de media que antes (280/119 ≈ 2,35 frente a 50/21 ≈ 2,38), porque la mayoría de las veces ya podemos tomar un atajo después de las dos primeras tiradas, y asignar directamente estos estados intermedios a una salida. Esta cantidad media de tiradas sigue bajando a medida que continuamos la tendencia.

Si estás familiarizado con la teoría de la información, entonces considera el hecho de que una tirada de un dado de 5 caras (= rand5) genera log2(5) ≈ 2,32 bits de información, y una tirada de un dado de 7 caras (= rand7) genera log2(7) ≈ 2,81 bits de información. Resulta que en el caso límite, sólo necesitamos log(7)/log(5) ≈ 1,21 llamadas de rand5 por cada valor de rand7 que queramos obtener. La implementación exacta que funciona arbitrariamente cerca de este límite es bastante complicada y está fuera del alcance de este artículo. Necesitaríamos almacenar información de estado entre las múltiples llamadas de rand7, y el algoritmo que tengo en mente no sólo es ilimitado en tiempo, sino también en memoria. Les invito a que me informen de un método que resuelva este último problema.

Una solución acotada

No existe un algoritmo acotado que calcule un valor aleatorio perfectamente uniforme entre 1 y 7, dado un generador aleatorio entre 1 y 5 solamente. Consideremos la familia de soluciones no acotadas anterior. Como he insinuado, en cada punto siempre habrá una cantidad de estados «sobrantes» (que van de 1 a 6) que hacen que el algoritmo se reinicie. Esto se debe a que 5 y 7 son números primos, y ninguna potencia de 5 puede ser nunca un múltiplo de 7. Por muy tentador que sea utilizar el pequeño teorema de Fermat, tales intentos darán lugar a errores de uno en uno, ya que la teoría básica de los números hace imposible una solución acotada en esta familia.

Podrías señalar, con razón, que el número de estados finales no es siempre una potencia de 5, por ejemplo en el caso de «hasta tres tiradas», donde podemos tomar atajos después de dos tiradas ya. ¿Quizás podríamos organizar la tabla de estados como para crear un algoritmo acotado con caminos de longitud variable y 7n estados finales? Sin embargo, considere lo siguiente:

1. Estos estados finales no serán igualmente probables porque no todos los caminos tienen la misma longitud (= cantidad de llamadas a rand5).
2. Podemos ampliar muy fácilmente el árbol para que todos los caminos sean igualmente largos, llamando inútilmente a rand5 una cantidad adecuada de veces cada vez que estemos en un estado final prematuro. Ahora la cantidad de estados finales vuelve a ser una potencia de 5, y todos los estados finales son igualmente probables.

Por supuesto, esto no es una prueba formal, pero espero haberte dado alguna intuición sobre el problema. Como vemos, a veces un problema puede parecer muy realista, sólo para tropezar con hechos matemáticos como estos. Después de este análisis, ¿puedes averiguar si es posible simular un dado de 8 caras partiendo de un dado de 4 caras?