¿Qué es este algoritmo de generación de números aleatorios y por qué funciona (o no)?

Question

Encontré el siguiente algoritmo (Monte Carlo) RNG en cierto artículo. Sea $f(x),f:\mathbb{R}^n \rightarrow \mathbb{R}$ sea la función de la que se desean obtener las muestras.

1. Dibujar un punto al azar $x \in \Omega$ (distribución uniforme en $\mathbb{R}^n$ ), donde $\Omega$ es la región deseada $\Omega \subset \mathbb{R}^n$ .
2. Evaluar la probabilidad $p(x) = \int_{\omega(x)} f(x) d x$ , donde $\omega(x) \subset \Omega$ es una región de integración finita pero pequeña alrededor de $x$ similar (con el mismo volumen) para cada dibujado $x$ .
3. Extraer un número al azar $0 \leq q \leq 1$ (distribución uniforme para $q \in \mathbb{R}$ ). La dirección punto $x$ se incluye en el conjunto de muestras $S$ si $q \leq p(x)/p_m$ donde $p_m = \max_{x \in \Omega} p(x)$ .
4. Volver a 1 hasta $S$ es lo suficientemente grande.

En la fuente no se explica cómo $\omega(x)$ y debemos suponer al menos que $f(x)>0$ sólo en conjunto compacto $\Omega$ (y cero en el resto) y que $f$ está limitada por arriba.

Así que no he diseñado el algoritmo. Sólo quiero averiguar si el algoritmo es válido método para generar muestras aleatorias de la distribución $f$ (y en qué condiciones).

Hasta ahora no he podido demostrar rigurosamente que el algoritmo funciona, pero he hecho el siguiente intento de solución:

Supongamos que $f$ es cierta densidad en $\Omega = [a,b] \subset \mathbb{R}$ y para cada $x\in\Omega$ deje $\omega(x)=[x-\epsilon,x+\epsilon]$ para algunos pequeños $\epsilon > 0$ .

Entonces $p(x) = \int_{x-\epsilon}^{x+\epsilon}f(x')dx' \approx \int_{x-\epsilon}^{x+\epsilon}f(x)dx' = 2\epsilon f(x)$ (y esto se cumple exactamente si $f$ es casi constante cerca de $x$ ) y aceptamos el punto $x$ si $q \leq \frac{2\epsilon f(x)}{p_m}$ (y tenemos que $q \sim \text{Uniform}([0,1])$ ). Si ahora comparamos esto con el muestreo de rechazo habitual en el que la distribución instrumental es uniforme, es decir $g(x)$ es pdf uniforme, vemos que la diferencia es la multiplicación adicional por $2\epsilon$ . Así pues, parece que el algoritmo es válido en cierto sentido aproximativo siempre que $2\epsilon \leq 1$ y los límites no causan problemas (es decir, la densidad llega a cero el tiempo suficiente antes de que los límites $x=a,x=b$ ). También si $\epsilon$ se elige muy pequeña, entonces es obvio que la probabilidad de aceptación será muy pequeña, haciendo que el algoritmo sea aún más ineficiente de lo que podría ser el muestreo de rechazo.

Entonces, ¿es el algoritmo anterior alguna variante conocida del método de aceptación-rechazo? ¿Podría alguien proporcionar una prueba o un enlace a una prueba donde se explique si el algoritmo funciona o no?

Answer 1

Su descripción del método es un poco impar. Su $p(x)$ es sólo $f(x)$ multiplicado por un factor de $2\epsilon$ con un poco de suavizado de $f(x)$ . No está claro por qué $f(x)$ necesita suavizarse.

Tampoco está claro por qué quiere generar una muestra grande de valores aleatorios para que la distribución típica de la muestra coincida con $f(x)$ . Es más habitual generar simplemente tantas muestras de la distribución de probabilidad como sea necesario.

Sin embargo, el método que has descrito pertenece a la clase general de métodos de aceptación-rechazo. Éstos se tratan en muchos libros de texto sobre simulación y generación de variantes aleatorias. Por ejemplo, véase el libro de Averill M. Law Modelado y análisis de simulación libro de texto.