Generación de variables aleatorias mediante composición e inversión

Question

¿Cuáles son los principales pros y contras de cada método y cuándo usar cada uno?

Law [2007] menciona que:

"Una vez más, se anima al lector a desarrollar el método de transformación inversa para generar una variable aleatoria de la distribución trapezoidal derecha en el Ejemplo 8.4. Nótese que especialmente si a es grande, el método de composición será más rápido que el método de transformación inversa, ya que éste siempre requiere tomar una raíz cuadrada, mientras que es bastante probable (con probabilidad a) que el primero simplemente devuelva $X= U_2 \sim U(0, 1)$. Este aumento en velocidad debe ser sopesado por el analista frente a la posible desventaja de tener que generar dos o tres números aleatorios para obtener un valor de X."

Por lo tanto, básicamente, para la distribución trapezoidal derecha (mencionada en la cita) podría ser útil utilizar la composición ya que es probable que sea más rápido. Sin embargo, ¡no estoy totalmente segura de por qué es así?

Supongamos que estoy generando una variable aleatoria utilizando el método inverso. Tengo una función de distribución acumulativa y necesito encontrar su inversa. Si es imposible, es probable que utilice el muestreo por transformación inversa utilizando el hecho de que las funciones de distribución acumulativa son débilmente monótonas y continuas por la derecha y generalizaré la inversa de la función de distribución acumulativa a una forma de $F^{-1}_X (u) = \inf\{ x|F_X(x)\geq u\}$ para $0. Puede ser un poco laborioso pero supongamos que obtenemos la inversa de la distribución acumulativa. Luego estoy creando una variable uniforme $U$ y la utilizo para generar la variable aleatoria utilizando la inversa de la distribución acumulativa.

No entiendo cómo el método de composición es más rápido. Porque para la composición, primero necesito identificar que de hecho puedo usar la composición a partir de su PDF. Luego creo la primera variable uniforme $U_1$ y la utilizo para decidir sobre la distribución (en caso de composición asumo que hay al menos dos). Y luego creo otra variable uniforme $U_2$ y la utilizo para generar la variable aleatoria. Pero aún necesito saber la inversa para saber qué producirá como salida. Simplemente me parece que en el método de composición aún necesito calcular la inversa para saber cuál será la variable aleatoria.

LAW, A. M. [2007], Modelado y Análisis por Simulación, 4ª ed., McGraw-Hill, Nueva York.

---

El ejemplo mínimo de trabajo que puedo pensar es $f(x) = 0.5 f_A(x) + 0.5 f_B(x)$, donde A es exponencial con parámetro $0.5$ y B es exponencial con parámetro $2$. Al observar la PDF $f(x)$ puedo ver que aquí podemos utilizar el método de composición. Y el método de generación será algo así:

1. Generar $U_1,U_2 \sim U(0,1)$.
2. Si $U_1 < 0.5$, entonces producir $X = -\frac{\log(U_2)}{0.5}$
3. Sino, producir $X = -\frac{\log(U_2)}{2}$

Pero si no supiera cuál es la inversa de la distribución exponencial, no sabría qué producir. Y el método de composición también implicaría la parte de inversión. ¿Estoy en lo correcto? No veo cómo sería más rápido en ese escenario.

Answer 1

En general, no deberías preocuparte por la eficiencia (rendimiento) entre los métodos de generación de variables aleatorias, a menos que hayas escrito una implementación de ellos, comparado su tiempo de ejecución, los hayas utilizado en tu aplicación y hayas encontrado que el tiempo de ejecución es inaceptable en tu aplicación. Este es un problema general en la programación que obviamente no se limita a la generación de variables aleatorias, un problema comúnmente conocido como "optimización prematura".

La mayor preocupación es la facilidad de implementación o de muestreo, o más bien la disponibilidad de algoritmos que muestrean la distribución en cuestión. (La precisión del muestreo de la distribución también suele ser importante). Aunque ahora hay numerosos algoritmos disponibles para muestrear distribuciones "estándar", como la normal, gamma y beta, muchas otras distribuciones que ocurren en la práctica tienen funciones de probabilidad no triviales (como la función de densidad de probabilidad, la función de distribución acumulada y/o la función de distribución acumulada inversa), y muchas de ellas tienen funciones de densidad de probabilidad cuya constante de normalización es intratable, por ejemplo. Un ejemplo notable son ciertos posteriores bayesianos cuyas funciones de densidad de probabilidad no se pueden evaluar punto por punto.

La siguiente pregunta muestra un ejemplo que involucra la distribución beta:

• https://stackoverflow.com/questions/65975300/speed-of-random-sampling-from-distribution-in-r

Answer 2

Aquí hay un código R rudimentario que compara composición versus inversión para una mezcla de $K$ distribuciones exponenciales:

library(rbenchmark)
#creación de objetivo
K=100
we=sort(runif(K),d=T) #peso de la mezcla
we=we/sum(we)
wes=cumsum(we) #suma acumulada
la=rexp(K)     #tasas exponenciales
lah=median(la)
F=function(x)sum(we*exp(-la*x)) #cdf de la cola

benchmark("compo"={
#composición
  x=rexp(1,la[1+sum(runif(1)>wes)])
},
"inve"={
#Inversión de Newton
u=runif(e<-1)
x0=-log(u)/lah
#precisión de 1e-3
while(abs((f<-u-F(x0)))>1e-3)x0=x0-f/lah
},
replicación=1e3,
columnas = c("prueba","transcurrido"))

devolviendo los tiempos como

         prueba transcurrido
1       compo   0.001
2        ïnve   0.231

Incluso utilizando un algoritmo de inversión mucho más eficiente, se mantiene la comparación: con

Q = function(u) uniroot((function(x) F(x) - u), lower = 0, 
    upper = qexp(.99,rate=min(la)))[1] #cuantil de cola numérico
x=Q(runif(1))

los tiempos comparados son

         prueba transcurrido
1       compo   0.001
2        ïnve   0.235
3     uniroot   0.017

Moverse a K=99999 componentes en la mezcla lleva a

         prueba transcurrido
1       compo   0.057
2        inve  45.736
3     uniroot   5.814

lo que favorece el caso de la composición versus la inversión...