Métodos de Monte Carlo

Nivel UniversitarioDificultad ★★★★★Aplicación⌖ Ver en el mapa

¿Qué es?

Estimar una integral (una esperanza) promediando una función en puntos aleatorios. El error es $\sigma/\sqrt N$ sea cual sea la dimensión, lo que lo convierte en el único método práctico para integrales de dimensión alta: renderizado, estadística bayesiana, física, finanzas.

¿Por qué existe?

La cuadratura en rejilla con $n$ puntos por eje necesita $n^d$ evaluaciones en $d$ dimensiones: imposible para los caminos de luz de 10 dimensiones de un renderizador o las posteriores de un millón de dimensiones de la estadística. A los puntos aleatorios no les importa la dimensión (Ulam y von Neumann, Los Álamos, 1946).

Fórmulas

$\int_\Omega f(x)\,\dd x \approx \frac{|\Omega|}{N}\sum_{i=1}^N f(x_i), \qquad \varepsilon_N \approx \frac{\sigma}{\sqrt N}$; $\int f(x)\,\dd x = \E_{x\sim q}\Big[\frac{f(x)}{q(x)}\Big]$
muestreo por importancia

¿Por qué importa?

El path tracing del cine, los modelos de riesgo financiero, el transporte de partículas en reactores y el MCMC de la IA bayesiana son Monte Carlo.

Las matemáticas que hay detrás

Integral definida★★★★★fundamental
Monte Carlo estima $\int f$ como la media de $f$ en puntos aleatorios; error $O(N^{-1/2})$ en cualquier dimensión.
Integrales múltiples y cambio de variables★★★★★fundamental
La cuadratura en rejilla en $d$ dimensiones necesita $n^d$ puntos; el error $O(N^{-1/2})$ de Monte Carlo no depende de $d$ .
Función de distribución acumulada★★★★★fundamental
Muestreo por transformada inversa: por ejemplo, $-\ln(1 - U)/\lambda$ es exponencial de tasa $\lambda$ .
Esperanza★★★★★fundamental
Monte Carlo estima esperanzas con medias muestrales.
Varianza★★★★★fundamental
El error de Monte Carlo es $\sigma/\sqrt N$ ; reducir la varianza (muestreo por importancia, variables de control) es la palanca principal.
Funciones inversas★★★★★frecuente
Muestreo por transformada inversa: si $U$ es uniforme en $(0,1)$ , $F^{-1}(U)$ tiene distribución $F$ .
Notación asintótica (O, o, Ω, Θ)★★★★★frecuente
El error de Monte Carlo es $O(N^{-1/2})$ en cualquier dimensión: 100 veces más muestras por cada cifra más.
Variables aleatorias continuas★★★★★frecuente
Los métodos de Monte Carlo extraen muestras de variables aleatorias continuas para estimar integrales.
Sumas de Riemann★★★★★frecuente
La integración de Monte Carlo es una suma tipo Riemann con puntos de muestra aleatorios en vez de una rejilla.
Cambio de variable★★★★★frecuente
El muestreo por importancia y por transformada inversa son cambios de variable en la integral que se estima.

¿Dónde se utiliza?

Temas de informática a los que se llega desde aquí, con la cadena de ideas que lleva a ellos:

3D Gráficos por computador

La ecuación de renderizado★★★★★

Qué depende de él

La ecuación de renderizado

Esta página tiene lo esencial. Un desarrollo más completo (intuición, definición formal, ejemplo resuelto) está en camino.