Replanteemos un poco la pregunta. Está buscando una función que tome como entrada un número entero de bits uniformemente aleatorios; en otras palabras, una muestra de una distribución de probabilidad discreta con 2 ^ n eventos. Cada evento tiene la misma probabilidad: 1 / (2 ^ n).
Se supone que la salida de esta función son muestras de una función de masa de probabilidad uniforme diferente, en este caso, una con exactamente diez resultados y una probabilidad de 1/10 para cada una.
La función es determinista: nuestra única fuente de aleatoriedad es la entrada. En otras palabras, cada evento de entrada posible (hay 2 ^ n de ellos) se asigna a uno de los diez eventos de salida posibles.
- ¿Es la matemática un buen título para un programador?
- ¿Cuál es la longitud esperada de la subsecuencia creciente más larga?
- ¿Cuál es un ejemplo de un montón que requiere exactamente n * log (n) pasos? Sé que el límite superior de un montón es O (n log n), pero ¿cómo hago para mostrar un ejemplo donde requiera exactamente n * log (n) pasos?
- ¿Cuál es la diferencia entre datos continuos y discretos?
- ¿Por qué debería elegir especializarme en ciencias de la computación en lugar de las matemáticas?
Visto de esta manera, la respuesta es clara: no puedes hacerlo exactamente con ninguna n finita. Sin embargo, si asigna las 2 ^ n entradas a las diez salidas, algunas de las salidas terminarán con más de una décima parte de las entradas y otras terminarán con menos de una décima parte. Esto se debe a que 2 ^ n nunca es divisible por 10.
Sin embargo, puede obtener un arbitrario cercano al uniforme a medida que aumenta el valor de n (la cantidad de bits que toma). Entonces, para cualquier tolerancia que esté dispuesto a permitir que la distribución de salida difiera de exactamente uniforme, hay una cantidad de bits (an) que garantiza que cumplirá con esa restricción.
Por diversión, hagamos los cálculos. Digamos que nuestro objetivo es que cada salida tenga exactamente una décima parte de las entradas (y, por lo tanto, una probabilidad de 1/10), pero estamos dispuestos a dejar que sea tan baja como 1/10-e o tan alta como 1/10 + e. Una manera simple de hacer el mapeo es encontrar el piso de 2 ^ n / 10, es decir, el entero más grande menor o igual a 2 ^ n / 10. Asignamos este número de entradas a las primeras nueve salidas, y el resto a La décima salida.
Los primeros nueve chicos terminan “bajos”, ¿por cuánto? Por lo que queda cuando divide 2 ^ 20 por 10: es decir, por (2 ^ n% 10) / 10 entradas de 2 ^ n en total, así que por (2 ^ n% 10) / (10 * 2 ^ n)) probabilidad. La probabilidad del último tipo termina “alta” – en 9 veces ese mismo valor. Siempre que sea menor que e (la tolerancia a divergir de la uniformidad exacta), estamos listos para comenzar. En otras palabras, puede hacer coincidir una distribución decimal uniforme con tolerancia +/- e utilizando no más de n bits, donde (9/10) * (2 ^ -n) * (2 ^ n% 10) -lg (e / 9 ) (Definitivamente hay algunos límites más estrictos).
Para resumir: si desea hacer coincidir una distribución uniforme de los dígitos del 0 al 9 con probabilidad uniforme 0.1 y tolerancia e, y tiene más de -lg (e / 9) bits, puede hacerlo. Si desea hacer coincidir exactamente una distribución uniforme, es decir, si e es cero, no hay n finito que pueda hacerlo.
