Supongamos que tenemos un generador aleatorio que genera números en el rango con distribución uniforme y necesitamos generar números aleatorios en el rango con distribución uniforme.[ 0 .. N - 1 ]
Supongamos que y no dividen equitativamente a ; Para obtener una distribución verdaderamente uniforme , podemos utilizar el método de muestreo de rechazo :N R
- si es el mayor entero tal que k N < R
- escoja un número aleatorio en
- si entonces emite , de lo contrario siga intentando con otros números aleatorios r ', r ", ... hasta que se cumpla la condición
¿Es el muestreo de rechazo la única forma de obtener una distribución discreta verdaderamente uniforme?
Si la respuesta es sí, ¿por qué?
Nota: si la idea es la misma: generar un número aleatorio en , por ejemplo donde es un número aleatorio en el rango
Respuestas:
Sí y no, dependiendo de lo que quiere decir con "la única manera". Sí, en el sentido de que no hay un método que garantice la terminación, lo mejor que puede hacer (para valores genéricos de y ) es un algoritmo que termina con la probabilidad 1. No, ya que puede hacer que el "desperdicio" sea pequeño como quieras.RN R
¿Por qué la terminación garantizada es imposible en general?
Suponga que tiene un motor de cálculo determinista (una máquina de Turing o lo que flota su barco), además de un oráculo que genera elementos aleatorios de la conjunto -elemento . Su objetivo es generar un elemento del conjunto de elementos . La salida de su motor depende solo de la secuencia de valores devueltos por el oráculo; es una función de esa secuencia potencialmente infinita .R N [ 0 , N - 1 ] f ( r 0 , r 1 , r 2 , ... )[0..R−1] N [0,N−1] f (r0,r1,r2,…)
Suponga que su motor llama al oráculo la mayoría de las veces . Puede haber rastros para los cuales el oráculo se llama menos de veces; si es así, llamar al oráculo veces adicionales para que siempre se llame exactamente veces no cambia la salida. Entonces, sin pérdida de generalidad, asumimos que el oráculo se llama exactamente veces. Entonces la probabilidad del resultado es el número de secuencias tal que . Como el oráculo es un generador aleatorio uniforme, cada secuencia es equiprobable y tiene la probabilidad . Por lo tanto, la probabilidad de cada resultado es de la formam m m x ( r 0 , … , r m - 1 ) f ( rm m m m x (r0,…,rm−1) 1 / R m A / R m A 0 R mf(r0,…,rm−1)=x 1/Rm A/Rm donde es un número entero entre y .A 0 Rm
Si divide durante algunos , entonces puede generar una distribución uniforme sobre elementos llamando al generador aleatorio veces (esto se deja como ejercicio para el lector). De lo contrario, esto es imposible: no hay manera de obtener un resultado con una probabilidad de . Tenga en cuenta que la condición es equivalente a decir que todos los factores primos de también son factores de (esto es más permisivo que lo que escribió en su pregunta; por ejemplo, puede elegir un elemento aleatorio entre 4 con un valor justo de 6 lados morir, a pesar de que 4 no divide a 6).R m m N m 1 / N N RN Rm m N m 1/N N R
Reduciendo el desperdicio
En su estrategia, cuando , no tiene que volver a dibujar inmediatamente. Intuitivamente, queda un poco de entropía en que puedes mantener en la mezcla.[ kr≥kN [kN..R−1]
Supongamos por un momento que usted, de hecho, seguir generando números aleatorios por debajo de para siempre, y se genera de ellos a la vez, haciendo dibuja. Si realiza un muestreo de rechazo directo en esta generación agrupada, el desperdicio sobre sorteos es , es decir, el resto dividido por el número de sorteos. Esto puede ser tan pequeño como . Cuando y son coprimos, puede hacer que el desperdicio sea arbitrariamente pequeño seleccionando valores suficientemente grandes de . Para valores generales de yu d d R d - kN u d d RdmodNugcd(R,N)Rd−kNud RdmodNu gcd(R,N) N d R N gcd ( R , N ) N / gcd ( R , N )R N d R N , el cálculo es más complicado porque debe tener en cuenta la generación de y separado, pero nuevamente puede hacer que el desperdicio sea arbitrariamente pequeño con grupos suficientemente grandes.gcd(R,N) N/gcd(R,N)
En la práctica, incluso con números aleatorios relativamente ineficientes (por ejemplo, en criptografía), rara vez vale la pena hacer algo más que un simple muestreo de rechazo, a menos que sea pequeño. Por ejemplo, en criptografía, donde es típicamente una potencia de 2 y es típicamente cientos o miles de bits, la generación uniforme de números aleatorios generalmente se realiza mediante muestreo de rechazo directo en el rango deseado.R NN R N
fuente
El teorema de codificación fuente de Shannon muestra que, en cierto sentido, necesita samples (en promedio) del tipo para generar un número aleatorio del tipo . Más exactamente, Shannon da un algoritmo (ineficiente) que da muestras del primer tipo, emite muestras del segundo tipo, con alta probabilidad. También muestra que la salida de muestras con alta probabilidad es imposible.[ 0 , … , R - 1 ] [ 0 , … , N - 1 ]logN/logR [0,…,R−1] [0,…,N−1] m ( log N / log R - ϵ ) m ( log N / log R + ϵ )m m(logN/logR−ϵ) m(logN/logR+ϵ)
El teorema de Shannon también funciona en el caso más general de una distribución de entrada sesgada (y probablemente también en una distribución de salida sesgada). En ese caso, debe reemplazar el logaritmo con la entropía. Si bien el algoritmo dado por el teorema se define al azar, en algunos casos es posible desrandomizarlo (a costa de un rendimiento algo peor).
fuente
En realidad, no, el muestreo de rechazo está lejos de ser la única forma de proceder. Desafortunadamente, considerando que las computadoras almacenan toda la información como bits y, por lo tanto, solo pueden manipular bits aleatorios de información, cualquier algoritmo para dibujar una variable aleatoria uniforme de rango será infinito, si el desarrollo de la base binaria de es infinito.NN N
Este teorema es un resultado clásico de Knuth y Yao (1976), quienes desarrollaron el marco de los árboles DDG (árboles generadores de distribución discreta).
Los métodos expuestos por Gilles son el tipo típico de cosas que se han hecho para mitigar el desperdicio incurrido por el rechazo, pero, por supuesto, si uno puede generar el seguimiento de los árboles de Knuth y Yao, es mucho, mucho más eficiente, en promedio 96% de bits aleatorios son salvados
He dado más información sobre esto en la siguiente publicación de CStheory .
fuente