En respuesta a una pregunta en los comentarios, he aquí un resumen de algunos potencialmente* maneras más rápidas de hacer distribuciones discretas de la cdf método.
* Digo "posiblemente" porque para algunos casos discretos de un bien implementado inversa-cdf enfoque puede ser muy rápido. El caso general es más difícil de hacer rápidamente sin la introducción de trucos adicionales.
Para el caso de los cuatro resultados diferentes, como en el ejemplo de la pregunta, la versión ingenua de la inversa de la cdf enfoque (o equivalente enfoques) están bien; pero si hay cientos (o miles, o millones) de las categorías que puede ser lento, sin ser un poco más inteligente (que sin duda no quieren ser secuencialmente la búsqueda a través de la cdf hasta encontrar la primera categoría en la que la cdf supera aleatorio uniforme). Hay algunos enfoques más rápido que eso.
[Se podían ver las primeras cosas que menciono a continuación s de tener una conexión más rápida de lo secuencial enfoques para la localización de un valor de uso de un índice y lo son de una manera "más inteligente versión de la utilización de la cdf". Uno puede, por supuesto, buscar en "estándar" enfoques para resolver problemas como "la búsqueda de un archivo ordenado", y terminan con métodos mucho más rápido que el rendimiento secuencial; si se le puede llamar adecuado de las funciones, enfoques estándar a menudo puede ser todo lo que usted necesita.]
De todos modos, para algunos métodos eficaces para la generación de distribuciones discretas.
1) el "método de Tabla" (Como Dougal notas en los comentarios, también conocido como el 'alias' el método). En lugar de ser $O(n)$ $n$ categorías, una vez establecido, el "simple" la versión de este en (a) (si la distribución es adecuada) es $O(1)$.
a) enfoque Simple - suponiendo racional de probabilidades (de hecho en el anterior ejemplo de datos):
- configurar una matriz con 10 células, que contiene un '1', cuatro '2, 'dos 3 tres 4. Muestra que el uso de un uniforme discreta (fácil de hacer en un continuo uniforme), y consigue simple código rápido.
b) caso Más complejo - no necesita 'bonito' de probabilidades. El uso de $2^k$ células, o más bien, usted terminará para arriba con un par de menos. Así, por ejemplo, considerar el siguiente:
x 0 1 2 3 4 5 6
P(X=x) 0.4581 0.0032 0.1985 0.3298 0.0022 0.0080 0.0002
(Podríamos haber 10000 células y utilizar el anterior enfoque exacto, por supuesto, pero lo que si estas probabilidades son irracionales, por ejemplo?)
Vamos a usar $k=8$. Se multiplican las probabilidades por $2^k$ y truncar para averiguar cuántos de cada tipo de célula necesitamos:
x 0 1 2 3 4 5 6 Tot
P(X=x) 0.4581 0.0032 0.1985 0.3298 0.0022 0.0080 0.0002 1.0000
[256p(x)] 117 0 50 84 0 2 0 253
A continuación, los últimos 3 células son, básicamente, "generar en lugar de esta otra distribución":
x* 0 1 2 3 4 5 6 Tot
P(X=x*) 0.091200 0.273067 0.272000 0.142933 0.187733 0.016000 0.017067 1.000000
Los "efectos colaterales" de la tabla puede ser realizada por cualquier método razonable (sólo llegar aquí alrededor de 1% del tiempo, no necesita ser tan rápido). Por lo $\frac{253}{256}$ del tiempo que se genera un aleatoria uniforme, en uso de sus primeros 8 bits para elegir una al azar de la célula, y la salida el valor de la celda; después de la configuración inicial de todo esto se puede hacer muy rápido. El otro $\frac{3}{256}$ del tiempo llegamos a una celda que dice "generar a partir de la segunda tabla". Casi siempre, se genera un
único y uniforme en $(0,1)$ y obtiene un discreto número aleatorio a partir de una multiplicar, el truncamiento y el costo de acceso a un elemento de la matriz.
2) "Ajustar el histograma" método; este es el tipo de relación con (1), pero cada célula puede generar uno de dos valores, dependiendo de la (continua) uniforme. De modo de generar un valor discreto de 1 a n, luego dentro de cada uno de ellos, ya sea para generar su principal valor o su segundo valor. Funciona con delimitadas las variables aleatorias. No hay desbordamiento de la tabla, y generalmente se utiliza mucho tablas más pequeñas que el método (1). Por lo general, es configurado de modo que la elección de la 1:n utiliza los primeros bits de un número aleatorio uniforme, y el resto de lo que nos dice cuál de los dos valores para que la bandeja de salida.
Tal vez la manera más fácil de contorno el método es hacerlo en el ejemplo de arriba:
Pensar en la distribución como un histograma con 4 bandejas:
![original 'histogram']()
Cortamos la parte superior de las más altas de los bares y los pusieron en los más pequeños, 'ajustarlo off'. El promedio de la "altura" de un bar de 0.25. Así que cortamos 0.15 fuera de la segunda barra y lo puso en la primera y 0,05 en la cuarta y la puso en la tercera:
!['squaring off' the histogram]()
Siempre es posible organizar de tal manera que no hay bin termina con más de 2 colores, a pesar de que un color puede terminar en varios contenedores.
Así que ahora que usted elija uno de los 4 contenedores al azar (requiere 2 bits aleatorios en la parte superior de un uniforme). A continuación, utilizar el resto de los bits para especificar un distribuida uniformemente en posición vertical y comparar con la ruptura entre los colores para ver cuál de los dos valores de salida. A la vez, muy rápido por lo general no es tan rápido como el de la mesa del método (método alias).
--
Estos métodos pueden ser adaptadas para tratar con ilimitada de variables, donde, de nuevo, es sobre todo rápido".
Referencia: http://www.jstatsoft.org/v11/i03/paper
El relativamente lento parte de estos es la creación de las tablas de valores; que es conveniente cuando usted sabe lo que usted va a ser capaz de generar ("tenemos que muestra los valores de esta distribución muchas veces en el futuro") en lugar de tratar de crear como de ir. "Tenemos que tomar una muestra de un millón de valores a partir de esto lo antes posible, pero nunca más tendremos que hacerlo de nuevo" crea diferentes prioridades; en muchas situaciones, algunas de las "estándar de computación enfoques" para buscar ordenan los valores (es decir, para hacer el cdf método más rápido) en realidad puede ser de tu mejor elección.
Hay todavía otra rápida enfoques para la generación de distribuciones discretas. Cuidadosamente codificado, usted puede hacer algunas muy rápido generación. Por ejemplo:
3) el rechazo de un método ("aceptar-rechazar") se puede hacer con distribuciones discretas; si usted tiene un discreto majorizing función ("sobre") y una distribución discreta de que ya se puede generar a partir de una forma rápida, se adapta directamente, y en algunos casos puede ser muy rápido. Más generalmente, usted puede tomar ventaja de ser capaz de generar a partir de distribuciones continuas (por ejemplo, mediante la discretización el resultado a un sobre discreto).
