¿Cómo generar números basados ​​en una distribución discreta arbitraria?

¿Cómo genero números basados ​​en una distribución discreta arbitraria?

Por ejemplo, tengo un conjunto de números que quiero generar. Digamos que están etiquetados de 1-3 de la siguiente manera.

1: 4%, 2: 50%, 3: 46%

Básicamente, los porcentajes son probabilidades de que aparezcan en la salida del generador de números aleatorios. Tengo un generador de números al azar que generará una distribución uniforme en el intervalo [0, 1]. ¿Hay alguna forma de hacer esto?

No hay límites en la cantidad de elementos que puedo tener, pero el% agregará hasta el 100%.

Uno de los mejores algoritmos para el muestreo de una distribución discreta es el método de alias .

El método de alias (eficientemente) calcula previamente una estructura de datos bidimensional para dividir un rectángulo en áreas proporcionales a las probabilidades.

En este esquema del sitio referenciado, un rectángulo de altura unitaria se ha dividido en cuatro tipos de regiones, diferenciadas por color, en las proporciones , , y , en para muestrear repetidamente desde una distribución discreta con estas probabilidades. Las tiras verticales tienen un ancho constante (unidad). Cada uno se divide en solo una o dos piezas. Las identidades de las piezas y las ubicaciones de las divisiones verticales se almacenan en tablas accesibles a través del índice de columna.1 / 3 1 / 12 1 /$1/2$$1/3$$1/12$$1/12$

La tabla se puede muestrear en dos pasos simples (uno para cada coordenada) que requieren generar solo dos valores uniformes independientes y cálculo . Esto mejora el cálculo de necesario para invertir el CDF discreto como se describe en otras respuestas aquí.$O(1)$$O(\log(n))$

Puede hacerlo fácilmente en R, solo especifique el tamaño que necesita:

sample(x=c(1,2,3), size=1000, replace=TRUE, prob=c(.04,.50,.46))

En su ejemplo, supongamos que dibuja su valor de uniforme pseudoaleatorio [0,1] y lo llama U. Luego, genera:

1 si U <0.04

2 si U> = 0.04 y U <0.54

3 si U> = 0.54

Si el% especificado es a, b, ..., simplemente envíe

valor 1 si U

valor 2 si U> = a y U <(a + b)

etc.

Esencialmente, estamos mapeando el% en subconjuntos de [0,1], y sabemos que la probabilidad de que un valor aleatorio uniforme caiga en cualquier rango es simplemente la longitud de ese rango. Poner los rangos en orden parece la forma más simple, si no única, de hacerlo. Esto supone que solo está preguntando sobre distribuciones discretas; para continuo, puede hacer algo como "muestreo de rechazo" ( entrada de Wikipedia ).

Supongamos que hay posibles resultados discretos. Divide el intervalo [ 0 , 1 ] en subintervalos basados ​​en la función de masa de probabilidad acumulativa, F , para dar el intervalo dividido ( 0 , 1 $m$$[0,1]$$F$$(0,1)$

donde y F ( 0 ) ≡ 0 . En tu ejemplo m = 3 y$I_{j} = (F(j-1), F(j))$$F(0) \equiv 0$$m = 3$

ya que y F ( 2 ) = .54 y F ( 3 ) = 1 .$F(1) = .04$$F(2) = .54$$F(3) = 1$

Entonces puede generar con distribución F usando el siguiente algoritmo:$X$$F$

(1) generar $U \sim {\rm Uniform}(0,1)$

(2) Si , entonces X = j .$U \in I_{j}$$X = j$

• Este paso se puede lograr observando si es menor que cada una de las probabilidades acumuladas y viendo dónde ocurre el punto de cambio (de a ), que debería ser una cuestión de usar un operador booleano en cualquier lenguaje de programación que esté usando y encontrar dónde ocurre lo primero en el vector.$U$TRUEFALSEFALSE

Tenga en cuenta que estará exactamente en uno de los intervalos I j ya que son disjuntos y partición [ 0 , 1 ] .$U$$I_{j}$$[0,1]$

Un algoritmo simple es comenzar con su número aleatorio uniforme y en un bucle primero restar la primera probabilidad, si el resultado es negativo, devuelve el primer valor, si aún es positivo, pasa a la siguiente iteración y resta la siguiente probabilidad , verifique si es negativo, etc.

Esto es bueno porque el número de valores / probabilidades puede ser infinito, pero solo necesita calcular las probabilidades cuando se acerca a esos números (para algo como generar a partir de una distribución binomial negativa o de Poisson).

Si tiene un conjunto finito de probabilidades, pero generará muchos números a partir de ellos, entonces podría ser más eficiente clasificar las probabilidades para que reste el primero más grande, luego el segundo más grande, y así sucesivamente.

En primer lugar, permítame llamar su atención sobre una biblioteca de Python con clases listas para usar para la generación de números aleatorios de números enteros o de punto flotante que siguen una distribución arbitraria.

En términos generales, hay varios enfoques para este problema. Algunos son lineales en el tiempo, pero requieren un gran almacenamiento de memoria, algunos se ejecutan en tiempo O (n log (n)). Algunos están optimizados para números enteros y otros están definidos para histogramas circulares (por ejemplo: generar puntos de tiempo aleatorios durante un día). En la biblioteca mencionada anteriormente, utilicé este documento para casos de números enteros y esta receta para números de coma flotante. (Todavía) carece de soporte de histograma circular y generalmente es desordenado, pero funciona bien.

Yo tuve el mismo problema. Dado un conjunto en el que cada elemento tiene una probabilidad y cuyas probabilidades de los elementos suman uno, quería dibujar una muestra de manera eficiente, es decir, sin clasificar nada y sin repetir repetidamente sobre el conjunto .

La siguiente función dibuja el más bajo de números aleatorios distribuidos uniformemente dentro del intervalo [ a , 1 ) . Sea r un número aleatorio de [ 0 , 1 ) .$N$$[a,1)$$r$$[0,1)$

Puede utilizar esta función para dibujar una serie ascendente de N números aleatorios distribuidos uniformemente en [0,1]. Aquí hay un ejemplo con N = 10 :$(a_i)$$N$$N = 10$

$a_0 = \text{next}(10, 0)$
$a_1 = \text{next}(9, a_0)$
$a_2 = \text{next}(8, a_1)$
$\dots$
$a_9 = \text{next}(1, a_8)$

$(a_i)$$P$$0 \leq k < |P|$$p_k \in P$$a_i$$k$$\sum p_0 \dots p_k > a_i$$p_k$$a_{i+1}$

$\{(1, 0.04), (2, 0.5), (3, 0.46)\}$$N = 10$

i a_i k Sum Draw
0 0.031 0 0.04 1
1 0.200 1 0.54 2
2 0.236 1 0.54 2
3 0,402 1 0,54 2
4 0.488 1 0.54 2
5 0.589 2 1.0 3
6 0.625 2 1.0 3
7 0.638 2 1.0 3
8 0,738 2 1,0 3
9 0.942 2 1.0 3

$(1, 2, 2, 2, 2, 3, 3, 3, 3, 3)$

$\text{next}$$N$$[a, x)$$x \leq 1$