Algoritmo per generare numeri casuali di Poisson e binomiali?

mi sono guardato intorno, ma non sono sicuro di come farlo.

ho trovato questa pagina che, nell’ultimo paragrafo, dice:

Un semplice generatore di numeri casuali presi da una distribuzione di Poisson si ottiene usando questa semplice ricetta: se x 1 , x 2 , … è una sequenza di numeri casuali con distribuzione uniforms tra zero e uno, k è il primo intero per cui il prodotto x 1 · x 2 · … · x k + 1 <e

Ho trovato un’altra pagina che descrive come generare numeri binomiali, ma penso che stia usando un’approssimazione della generazione di Poisson, che non mi aiuta.

Ad esempio, considera i numeri casuali binomiali. Un numero casuale binomiale è il numero di teste in N lanci di una moneta con probabilità p di teste su ogni singolo lancio. Se si generano N numeri casuali uniformi nell’intervallo (0,1) e si conta il numero inferiore a p, il conteggio è un numero casuale binomiale con i parametri N e p.

so che ci sono biblioteche per farlo, ma non posso usarli, solo i generatori standard uniformi forniti dalla lingua (java, in questo caso).

Distribuzione di Poisson

Ecco come Wikipedia dice che Knuth dice di farlo :

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. 

In Java, sarebbe:

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

Distribuzione binomiale

Passando al capitolo 10 di Non-Uniform Random Variate Generation (PDF) di Luc Devroye (che ho trovato collegato all’articolo di Wikipedia ) fornisce questo:

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

notare che

Nessuno di questi algoritmi è ottimale. Il primo è O (λ), il secondo è O (n). A seconda dell'ampiezza di questi valori e della frequenza con cui è necessario chiamare i generatori, potrebbe essere necessario un algoritmo migliore. Il documento che ho linkato sopra ha algoritmi più complicati che funzionano in tempo costante, ma lascerò quelle implementazioni come un esercizio per il lettore. 🙂

Per questo e altri problemi numerici la bibbia è il libro di ricette numeriche.

C’è una versione gratuita per C qui: http://www.nrbook.com/a/bookcpdf.php (plugin richiesto)

Oppure puoi vederlo su Google Libri: 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

Il codice C dovrebbe essere molto facile da trasferire in Java.

Questo libro vale il suo peso in oro per molti problemi numerici. Sul sito sopra puoi anche acquistare l’ultima versione del libro.

Sebbene la risposta pubblicata da Kip sia perfettamente valida per generare RV di Poisson con una piccola percentuale di arrivi (lambda), il secondo algoritmo pubblicato in Wikipedia che genera variabili di Poisson è meglio per una maggiore velocità di arrivi dovuta alla stabilità numerica.

Ho dovuto affrontare problemi durante l’implementazione di uno dei progetti che richiedevano la generazione di Poisson RV con lambda molto alto a causa di questo. Quindi suggerisco l’altro modo.

Esistono diverse implementazioni dal CERN nella seguente libreria (codice Java):

http://acs.lbl.gov/~hoschek/colt/

Riguardo ai numeri casuali binomiali, è basato sul documento del 1988 “Binomial Random Variate Generation”, che vi raccomando dato che usano un algoritmo ottimizzato.

Saluti