Para un n dado, ¿es posible elegir uniformemente un número del 1 al n usando un número fijo de bits aleatorios uniformes?

Answer 1

No Esto no es posible incluso en el caso especial [matemática] n = 3 [/ matemática], ni para cualquier otra [matemática] n [/ matemática] que no sea una potencia de 2.

Si tiene algún algoritmo para elegir entre 1, 2, 3 de manera uniforme al azar usando como máximo 1,000 bits aleatorios, puede convertirlo trivialmente en un algoritmo que haga lo mismo usando exactamente 1,000 bits aleatorios: cada vez que el algoritmo original termina después de usar solo 967 bits, solo tienes que pedir 23 adicionales y no hacer nada con ellos.

Entonces, ahora tiene un algoritmo que accede a 1,000 bits aleatorios y termina con una opción de 1, 2 o 3. Por lo tanto, haga lo que haga el algoritmo, hay un subconjunto de los posibles resultados [matemáticos] 2 ^ {1000} [/ matemáticos] de los bits que producen la opción 1, y hay otro subconjunto que produce 2, y otro que produce 3. Se supone que esos subconjuntos tienen el mismo tamaño y son disjuntos, pero desafortunadamente [math] 2 ^ {1000} [/ math] es no es divisible por 3, entonces eso es imposible.

Como señaló, puede lograr fácilmente el resultado deseado utilizando un algoritmo como este:

– Elige dos bits aleatorios

– Si son 00, diga “1”

– Si son 01, diga “2”

– Si son 10, diga “3”

– Si tienen 11 años, intente nuevamente.

Este algoritmo termina con probabilidad 1, generalmente muy rápidamente, y produce un valor uniforme entre 1, 2, 3, pero no se garantiza que use un número fijo de bits. Si no tiene suerte, puede requerir 10, o 10,000, o un billón, o más.