Es el rechazo de muestreo La única manera de conseguir una distribución verdaderamente uniforme de números aleatorios?

Question

Supongamos que tenemos un generador aleatorio que las salidas números en el rango de $ [0..R-1] $ con una distribución uniforme y necesidad de generar números aleatorios en el rango de $ [0..N-1] $ con distribución uniforme.

Supongamos que $ N distribución uniforme de verdad podemos utilizar el rechazo muestreo método :

• si $ k $ es el mayor número entero tal que k $ N
• recoger un número aleatorio r $ $ en $ [0..R-1] $
• Si $ r

Es el rechazo de muestreo La única manera de conseguir una distribución discreta verdaderamente uniforme?

Si la respuesta es sí, ¿por qué?

Nota: si $ N> R $ la idea es la misma: generar un número aleatorio $ R '$ en $ [0..R ^ m-1], R ^ m> = N $, por ejemplo $ r '= R (... R (R r_1 + r_2) ...) + r_m $ donde $ $ r_i es un número aleatorio en el rango de $ [0..R-1] $

Answer 1

Sí y no, dependiendo de lo que quiere decir con “el único camino”. Sí, en la que no existe un método que está garantizado para terminar, lo mejor que puede hacer (para los valores genéricos de $ N $ y $ R $) es un algoritmo que termina con probabilidad 1. No, de que pueden hacer que el “ perder”tan pequeño como te gusta.

¿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 $ R $ -elemento conjunto $ [0..R-1] $. Su objetivo es generar un elemento de la N $ $ $ -elemento conjunto [0, N-1] $. La salida de su motor depende sólo de la secuencia de valores devueltos por el oráculo; es una función $ f $ de esa secuencia potencialmente infinito $ (r_0, r_1, r_2, \ ldots) $.

Supongamos que su motor llama el oráculo de la mayoría de las veces $ $ m. Puede haber rastros para el que el oráculo se llama veces menos de $ m $; si es así, llamando a los tiempos extras oráculo de modo que siempre se llama exactamente $ m $ tiempos no cambia la salida. Así que sin pérdida de generalidad, suponemos que el oráculo se llama exactamente $ m $ tiempos. Entonces, la probabilidad del resultado $ x $ es el número de secuencias $ (r_0, \ ldots, r_ {m-1}) $ tal que $ f (r_0, \ ldots, r_ {m-1}) = x $. Desde el oráculo es un generador aleatorio uniforme, cada secuencia es equiprobable y tiene la probabilidad $ 1 / R ^ m $. Por lo tanto la probabilidad de cada resultado es de la forma $ A / R ^ m $ donde $ A $ es un número entero entre $ 0 $ y $ R ^ m $.

Si $ N $ divide $ R ^ m $ por alguna $ m $, entonces se puede generar una distribución uniforme sobre los elementos $ N $ llamando el generador aleatorio $ m $ veces (esto se deja como ejercicio para el lector ). De lo contrario, esto es imposible: no hay manera de obtener un resultado con probabilidad $ 1 / N $. Tenga en cuenta que la condición es equivalente a decir que todos los factores primos $ N $ 's son también factores de $ R $ (esto es más permisiva que lo que escribió en su pregunta, por ejemplo, puede elegir un elemento de azar entre 4 con una justo matriz 6 lados, a pesar de que 4 no divide 6).

La reducción de los residuos

En su estrategia, cuando r $ \ ge k \, N $, que no tiene que volver a dibujar inmediatamente. Intuitivamente, hay un poco de entropía que queda en $ [k \, N .. R-1] $ que puede tener en la mezcla.

Supongamos por un momento que usted, de hecho, seguir generando números aleatorios por debajo de $ N $ para siempre, y que genere $ u $ de ellos a la vez que gana $ d $ dibuja. Si lo hace un rechazo directo de muestreo en esta generación agrupados, los residuos más de $ d $ atrae es $ \ dfrac {R ^ d - k \, N ^ u} {d} $, es decir, el resto $ R ^ d \ mathbin { \ mathrm {mod}} N ^ u $ dividido por el número de empates. Esto puede ser tan poco como $ \ mcd (R, N) $. Cuando R $ $ y $ $ N son primos entre sí, puede hacer que los residuos arbitrariamente pequeña escogiendo valores suficientemente grandes de $ d $. Para los valores generales de $ R $ y $ N $, el cálculo es más complicado porque hay que tener en cuenta la generación de $ \ mcd (R, N) $ y $ N / \ mcd (R, N) $ separado, pero de nuevo se puede hacer arbitrariamente pequeño de los residuos con grupos suficientemente grandes.

En la práctica, incluso con números aleatorios relativamente ineficientes (por ejemplo en la criptografía), rara vez es digno de hacer cualquier cosa menos sencilla toma de muestras de rechazo, a menos que $ N $ es pequeño. Por ejemplo, en la criptografía, donde $ R $ es típicamente una potencia de 2 y $ N $ es típicamente cientos o miles de bits, la generación de número aleatorio uniforme por lo general procede por muestreo rechazo recta en el intervalo deseado.

Answer 2

fuente de Shannon de codificación teorema demuestra que, en algún sentido exacto, necesita $ \ log N / \ samples log R $ (en promedio) del tipo $ [0, \ ldots, R-1] $ para generar un azar número del tipo $ [0, \ ldots, N-1] $. Más exactamente, Shannon da un algoritmo (ineficiente) que dado $ m $ muestras del primer tipo, las salidas $ m (\ log N / \ log R - \ epsilon) muestras $ del segundo tipo, con alta probabilidad. También muestra que la salida $ m (\ log N / \ log R + \ epsilon) $ muestras con alta probabilidad es imposible.

El teorema de Shannon también trabaja en el caso más general de una distribución sesgada de entrada (y probablemente también la distribución sesgada de salida). En ese caso, es necesario sustituir el logaritmo de la entropía. Mientras que el algoritmo dado por el teorema se define al azar, en algunos casos es posible derandomize que (a costa de algo peor rendimiento).

Answer 3

En realidad, no, el rechazo de muestreo está lejos de ser la única manera de proceder. Por desgracia, teniendo en cuenta que los ordenadores para almacenar toda la información en forma de bits, y por lo tanto sólo se pueden manipular bits aleatorios de información, cualquier algoritmo para dibujar una variable aleatoria uniforme de rango $ N $ será infinito, si el desarrollo de la base binaria de $ N $ es infinito.

Este teorema es un resultado clásico por Knuth y Yao (1976), que desarrolló el marco de DDG-árboles (árboles de generación de distribución discreta).

Los métodos expuestos por Gilles son el tipo típico de lo que se ha hecho para mitigar los residuos incurridos por el rechazo, pero por supuesto si se pueden generar siguiente Knuth y árboles de Yao es mucho, mucho más eficiente - en promedio 96% de bits aleatorios se guardan.

Me han dado más información al respecto en el siguiente CStheory posterior .