El muestreo de números pseudoaleatorios o la generación de variables pseudoaleatorias no uniformes es la práctica numérica de generar números pseudoaleatorios que se distribuyen de acuerdo con una distribución de probabilidad dada .
Los métodos de muestreo de una distribución no uniforme se basan típicamente en la disponibilidad de un generador de números pseudoaleatorios que produce números X que se distribuyen uniformemente. A continuación, se utilizan algoritmos computacionales para manipular una única variable aleatoria , X , o con frecuencia varias de estas variables, en una nueva variable aleatoria Y de modo que estos valores tengan la distribución requerida.
Históricamente, se desarrollaron métodos básicos de muestreo de números pseudoaleatorios para las simulaciones de Montecarlo en el proyecto Manhattan ; [ cita requerida ] fueron publicados por primera vez por John von Neumann a principios de la década de 1950. [1]
Distribuciones discretas finitas
Para una distribución de probabilidad discreta con un número finito n de índices en los que la función de masa de probabilidad f toma valores distintos de cero, el algoritmo de muestreo básico es sencillo. El intervalo [0, 1) se divide en n intervalos [0, f (1)), [ f (1), f (1) + f (2)), ... El ancho del intervalo i es igual a la probabilidad f ( i ). Se extrae un número X pseudoaleatorio uniformemente distribuido y se busca el índice i del intervalo correspondiente. El i así determinado tendrá la distribución f ( i ).
Formalizar esta idea se vuelve más fácil mediante el uso de la función de distribución acumulativa
Es conveniente establecer F (0) = 0. Los n intervalos son simplemente [ F (0), F (1)), [ F (1), F (2)), ..., [ F ( n - 1), F ( n )). La principal tarea computacional es entonces determinar i para la cual F ( i - 1) ≤ X < F ( i ).
Esto se puede hacer mediante diferentes algoritmos:
- Búsqueda lineal , tiempo computacional lineal en n .
- Búsqueda binaria , el tiempo computacional va con log n .
- Búsqueda indexada , [2] también llamado método de punto de corte . [3]
- Método de alias , el tiempo computacional es constante, usando algunas tablas precalculadas.
- Hay otros métodos que cuestan tiempo constante. [4]
Distribuciones continuas
Métodos genéricos para generar muestras independientes :
- Muestreo de rechazo para funciones de densidad arbitrarias
- Muestreo por transformada inversa para distribuciones cuya CDF es conocida
- Muestreo de rebanadas
- Algoritmo Zigurat , para funciones de densidad decrecientes monótonamente, así como distribuciones unimodales simétricas
- Generador de números aleatorios de convolución , no es un método de muestreo en sí mismo: describe el uso de aritmética además de uno o más métodos de muestreo existentes para generar distribuciones más complicadas.
Métodos genéricos para generar muestras correlacionadas (a menudo necesarios para distribuciones de forma inusual o de alta dimensión):
- Cadena de Markov Monte Carlo , el principio general
- Algoritmo de Metropolis-Hastings
- Muestreo de Gibbs
- Muestreo de rebanadas
- Monte Carlo de cadena de Markov de salto reversible , cuando el número de dimensiones no es fijo (por ejemplo, al estimar un modelo de mezcla y al mismo tiempo estimar el número de componentes de mezcla)
- Filtros de partículas , cuando los datos observados están conectados en una cadena de Markov y deben procesarse secuencialmente
Para generar una distribución normal :
Para generar una distribución de Poisson :
Bibliotecas de software
La Biblioteca Científica GNU tiene una sección titulada "Distribuciones de números aleatorios" con rutinas para muestrear bajo más de veinte distribuciones diferentes.
Notas al pie
- ^ Von Neumann, John (1951). "Varias técnicas utilizadas en relación con dígitos aleatorios" (PDF) . Revista de Investigación de la Oficina Nacional de Estándares, Serie de Matemáticas Aplicadas . 3 : 36–38.
Cualquiera que considere métodos aritméticos para producir dígitos aleatorios, por supuesto, está en un estado de pecado.
También en línea hay un escaneo de baja calidad de la publicación original . - ^ Ripley (1987) [ página necesaria ]
- ^ Fishman (1996) [ página necesaria ]
- ^ Fishman (1996) [ página necesaria ]
Literatura
- Devroye, L. (1986) Generación variable aleatoria no uniforme . Nueva York: Springer
- Fishman, GS (1996) Montecarlo. Conceptos, algoritmos y aplicaciones . Nueva York: Springer
- Hörmann, W .; J Leydold, G Derflinger (2004,2011) Generación variable aleatoria no uniforme automática . Berlín: Springer.
- Knuth, DE (1997) El arte de la programación informática , vol. 2 Algoritmos seminuméricos , Capítulo 3.4.1 (3ª edición).
- Ripley, BD (1987) Simulación estocástica . Wiley.