java - transformada - ¿Algoritmo para generar números aleatorios de Poisson y binomiales?
metodo de la transformada inversa en java (4)
He estado mirando alrededor, pero no estoy seguro de cómo hacerlo.
He encontrado esta página que, en el último párrafo, dice:
Un simple generador de números aleatorios tomados de una distribución de Poisson se obtiene usando esta receta simple: si x 1 , x 2 , ... es una secuencia de números aleatorios con una distribución uniforme entre cero y uno, k es el primer entero para el cual producto x 1 · x 2 · ... · x k + 1 <e -λ
Encontré otra página que describe cómo generar números binomiales, pero creo que está utilizando una aproximación de la generación de Poisson, que no me ayuda.
Por ejemplo, considere los números aleatorios binomiales. Un número aleatorio binomial es el número de caras en N lanzamientos de una moneda con probabilidad p de cabezas en un solo lanzamiento. Si genera N números aleatorios uniformes en el intervalo (0,1) y cuenta el número menor que p, entonces el conteo es un número aleatorio binomial con los parámetros N y p.
Sé que hay bibliotecas para hacerlo, pero no puedo usarlas, solo los generadores uniformes estándar proporcionados por el lenguaje (java, en este caso).
distribución de veneno
Así es como dice Wikipedia que dice Knuth para hacerlo :
init:
Let L ← e^(−λ), k ← 0 and p ← 1.
do:
k ← k + 1.
Generate uniform random number u in [0,1] and let p ← p × u.
while p > L.
return k − 1.
En Java, eso sería:
public static int getPoisson(double lambda) {
double L = Math.exp(-lambda);
double p = 1.0;
int k = 0;
do {
k++;
p *= Math.random();
} while (p > L);
return k - 1;
}
Distribución binomial
El capítulo 10 de la Generación aleatoria de variaciones no uniformes (PDF), de Luc Devroye (que encontré vinculado en el artículo de Wikipedia ) da esto:
public static int getBinomial(int n, double p) {
int x = 0;
for(int i = 0; i < n; i++) {
if(Math.random() < p)
x++;
}
return x;
}
tenga en cuenta
Ninguno de estos algoritmos es óptimo. El primero es O (λ), el segundo es O (n). Dependiendo de qué tan grandes sean estos valores, y con qué frecuencia necesita llamar a los generadores, es posible que necesite un mejor algoritmo. El documento que vinculo arriba tiene algoritmos más complicados que se ejecutan en un tiempo constante, pero dejaré esas implementaciones como un ejercicio para el lector. :)
Aunque la respuesta publicada por Kip es perfectamente válida para generar RV de Poisson con una tasa de llegada pequeña (lambda), el segundo algoritmo publicado en Wikipedia que genera las variables aleatorias de Poisson es mejor para una tasa de llegada mayor debido a la estabilidad numérica.
Me enfrenté a problemas durante la implementación de uno de los proyectos que requieren la generación de Poisson RV con muy alta lambda debido a esto. Así que sugiero la otra manera.
Hay varias implementaciones de CERN en la siguiente biblioteca (código Java):
http://acs.lbl.gov/~hoschek/colt/
Con respecto a los números aleatorios binomiales, se basa en el documento de 1988 "Generación de Variables Aleatorias Binomiales", que le recomiendo ya que utilizan un algoritmo optimizado.
Saludos
Para este y otros problemas numéricos, la Biblia es el libro de recetas numéricas.
Hay una versión gratuita para C aquí: http://www.nrbook.com/a/bookcpdf.php (se requiere complemento)
O puede verlo en Google Books: http://books.google.co.uk/books?id=4t-sybVuoqoC&lpg=PP1&ots=5IhMINLhHo&dq=numerical%20recipes%20in%20c&pg=PP1#v=onepage&q=&f=false
El código C debería ser muy fácil de transferir a Java.
Este libro vale su peso en oro para muchos problemas numéricos. En el sitio anterior también puedes comprar la última versión del libro.