numeros - Un código de generador de números aleatorios binomial eficiente en Java

math.random java

Question

La pregunta relevante es: Algoritmo para generar Poisson y números aleatorios binomiales?

Acabo de tomar su descripción para el número aleatorio Binomial:

Por ejemplo, considere números aleatorios binomiales. Un número aleatorio binomial es el número de cabezas en N lanzamientos de una moneda con probabilidad p de cabezas en cualquier lanzamiento. Si genera N números aleatorios uniformes en el intervalo (0,1) y cuenta el número menor que p, entonces el recuento es un número aleatorio binomial con los parámetros N y p.

Hay una solución trivial en Algoritmo para generar Poisson y números aleatorios binomiales? mediante el uso de iteraciones:

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;
}

Sin embargo, mi propósito de buscar un generador binomial de números aleatorios es solo para evitar los bucles ineficientes (i de 0 a n). Mi n puede ser muy grande. Y p a menudo es muy pequeño.

Un ejemplo de juguete de mi caso podría ser: n = 1 * 10 ^ 6, p = 1 * 10 ^ (- 7).

El n puede variar de 1 * 10 ^ 3 a 1 * 10 ^ 10.

Answer 1

Podría imaginar una forma de acelerarlo por un factor constante (por ejemplo, 4).

Después de 4 lanzamientos arrojarás una cabeza 0,1,2,3 o 4.

Las probabilidades para esto son algo así como [0.6561, 0.2916, 0.0486, 0.0036, 0.0001].

Ahora puedes generar un número aleatorio y simular 4 lanzamientos originales. Si no está claro cómo puedo elaborar un poco más.

De esta forma, después de algunos cálculos previos originales, puede acelerar el proceso casi 4 veces. El único requisito para que sea preciso es que la granularidad de su generador aleatorio es al menos p ^ 4.

Answer 2

Si tiene valores pequeños de p , le gustará esta mejor que la implementación ingenua que citó. Aún se repite, pero el número esperado de iteraciones es O(np) por lo que es bastante rápido para valores de p pequeños. Si está trabajando con valores p grandes, reemplace p con q = 1-p y reste el valor de retorno de n . Claramente, será peor cuando p = q = 0.5 .

public static int getBinomial(int n, double p) {
   double log_q = Math.log(1.0 - p);
   int x = 0;
   double sum = 0;
   for(;;) {
      sum += Math.log(Math.random()) / (n - x);
      if(sum < log_q) {
         return x;
      }
      x++;
   }
}

La implementación es una variante del "Segundo método de tiempo de espera" de Luc Devroye en la página 522 de su texto "Generación de Variedades aleatorias no uniformes".

Existen métodos más rápidos basados ​​en técnicas de aceptación / rechazo, pero son sustancialmente más complejos de implementar.