Algoritmo ziggurat

L'algoritmo ziggurat è un algoritmo di rejection sampling utilizzato per il campionamento numerico pseudo-casuale. È stato sviluppato negli anni '60 da George Marsaglia e viene utilizzato per generare valori da una distribuzione di probabilità decrescente monotona partendo da una sorgente di numeri casuali uniformemente distribuiti (solitamente un generatore di numeri pseudo-casuali) e da una tabella precalcolata. Può anche essere applicato a distribuzioni unimodali simmetriche, come la distribuzione normale. L'algoritmo ziggurat è più veloce rispetto ad altri metodi di generazione di numeri casuali normalmente distribuiti, come il metodo polare di Marsaglia e la trasformazione di Box-Muller. Tuttavia, poiché questo algoritmo è anche più complesso da implementare, solitamente è utilizzato solo a fronte di una grande richiesta di numeri pseudo-casuali. Il termine ziggurat risale all'articolo scritto da Marsaglia e Wai Wan Tsang nel 2000, che lo chiamarono così per via del modo in cui distribuisce la probabilità, ovvero tramite segmenti rettangolari impilati in ordine decrescente, assomigliando così a una ziggurat. L'algoritmo Ziggurat utilizzato per generare valori campione con una distribuzione normale (solo i valori positivi sono mostrati per semplicità). I punti rosa sono inizialmente numeri casuali distribuiti uniformemente. La funzione di distribuzione desiderata viene prima segmentata in aree uguali "A". Uno strato i è selezionato a caso dalla fonte uniforme a sinistra. Quindi un valore casuale dalla sorgente viene moltiplicato per la larghezza del livello scelto e il risultato viene testato x volte per vedere in quale regione della fenditura cade. I possibili risultati sono: 1) (sinistra, regione nera) il campione è chiaramente sotto la curva e viene passato direttamente all'output, 2) (a destra, regione a strisce verticali) il valore del campione può trovarsi sotto la curva e deve essere ulteriormente testato. In tal caso, viene generato un valore y casuale all'interno del livello scelto e confrontato con f (x) . Se inferiore, il punto è sotto la curva e viene emesso il valore x . In caso contrario, il punto scelto x viene rifiutato e l'algoritmo viene riavviato dall'inizio.