¿Cómo generar un número aleatorio a partir de la distribución discreta especificada?

Question

Digamos que tenemos una distribución discreta con un número finito de resultados posibles, ¿es posible generar un número aleatorio a partir de esta distribución más rápido que en O (logn), donde n es posible el número de resultados?

Cómo hacer en O (log n):
- Hacer una matriz con probabilidad acumulada (Array [i] = Probabilidad de que el número al azar será menor o igual a i)
- Generar número aleatorio desde distribución uniforme (permite denotarlo por k)
- Encuentra el más pequeño i de manera que k < Matriz [i]. Se puede hacer usando la búsqueda binaria.
- soy nuestro número aleatorio.

Answer 1

El método del alias de Walker puede dibujar una muestra en el peor de los casos constante, usando algunas matrices auxiliares de tamaño n que necesitan ser precalculadas. Este método se describe en el Capítulo 3 de Devroye's book on sampling y se implementa en la función R sample(). Puede obtener el código del código fuente de R o this thread. A 1991 paper by Vose afirma reducir el costo de inicialización.

Tenga en cuenta que su pregunta no está bien definida a menos que especifique la forma exacta de la entrada y cuántos números aleatorios desea dibujar. Por ejemplo, si la entrada es una matriz que da la probabilidad de cada resultado, entonces su algoritmo no es O (log n) porque primero se requiere calcular las probabilidades acumuladas que toman O (n) el tiempo de la matriz de entrada.

Si tiene la intención de dibujar muchas muestras, el costo de generar una muestra no es tan importante. En cambio, lo que importa es el costo total para generar m resultados y la memoria pico requerida. En este sentido, el método de alias es muy bueno. Si desea generar todas las muestras a la vez, use el algoritmo O (n + m) publicado en here y luego mezcle los resultados.