C #: algorithme numérique pour générer des nombres à partir de la dissortingbution binomiale

J’ai besoin de générer des nombres aléatoires à partir de la dissortingbution binomiale (n, p).

Une variable aléatoire binomiale (n, p) est la sum de n variables uniformes qui prennent 1 avec une probabilité p. En pseudo-code, x=0; for(i=0; i<n; ++i) x+=(rand()<p?1:0); x=0; for(i=0; i<n; ++i) x+=(rand()<p?1:0); va générer un binôme (n, p).

J’ai besoin de générer ceci pour les petits comme pour les très grands n, par exemple n = 10 ^ 6 et p = 0,02. Existe-t-il un algorithme numérique rapide pour le générer?

MODIFIER –

À l’heure actuelle, c’est ce que j’ai comme approximation (avec les fonctions de dissortingbution exacte de Poisson et normale) –

  public long Binomial(long n, double p) { // As of now it is an approximation if (n < 1000) { long result = 0; for (int i=0; i<n; ++i) if (random.NextDouble() < p) result++; return result; } if (n * p < 10) return Poisson(n * p); else if (n * (1 - p) < 10) return n - Poisson(n * p); else { long v = (long)(0.5 + nextNormal(n * p, Math.Sqrt(n * p * (1 - p)))); if (v  n) v = n; return v; } }

Si vous êtes prêt à payer, jetez un coup d’œil à NMath by Centerspace.

Sinon, le code C utilisé par le programme Stats R est ici et devrait pouvoir être facilement transféré en C #.

EDIT: Il existe des détails (code inc.) Sur la création d’une méthode à cette fin sur la page 178 de Méthodes numériques pratiques avec C # de Jack Xu.

UN AUTRE ÉDIT: Une bibliothèque gratuite C # qui fait ce que vous voulez.

Une autre option serait d’échantillonner à partir de Normal ou de Poisson, puis d’append une étape Metropolis-Hastings pour accepter ou rejeter votre échantillon. Si vous acceptez, vous avez terminé, si vous refusez, vous devez à nouveau effectuer un nouvel échantillonnage. Je suppose que, étant donné que l’approximation est si proche, vous obtiendrez presque toujours une étape d’acceptation, que vous pourriez parfois rejeter.

Le livre de Luc Devroye contient également d’excellents algorithmes d’échantillonnage binomial.

PS Si vous vous retrouvez avec un bon algorithme; cela vous dérangerait-il de le partager sur Math.Net Numerics ?

Il n’y a pas de moyen évident de le faire efficacement. Pour les petits n, vous pouvez également nous indiquer la formule permettant de calculer le PDF inverse. Pour les plus grands n, vous feriez probablement mieux d’utiliser l’une des approximations d’autres dissortingbutions plus faciles à calculer.