Rejection sampling: differenze tra le versioni

Versione delle 22:13, 22 lug 2024

Versione attuale delle 10:31, 16 mar 2025

(3 versioni intermedie di un altro utente non mostrate)

Riga 1:

In [[analisi numerica]] e in [[statistica computazionale]], '''rejection sampling''' è una tecnica di base utilizzata per generare osservazioni da una [[Variabile casuale#Distribuzione di probabilità|distribuzione]] . È anche comunemente chiamato il '''metodo di acceptance-rejection''' o "algoritmo di '''accept-rejection'''".

Rejection sampling si basa sul fatto che, per campionare una [[variabile casuale]] in una dimensione, si può eseguire un campionamento uniformemente casuale del grafico cartesiano bidimensionale e mantenere i campioni nella '''regione''' sotto il grafico della sua funzione di densità.<ref>{{Cita libro|autore=Casella|nome=George|autore2=Robert|nome2=Christian P.|nome3=Martin T.|autore3=Wells|titolo=Generalized Accept-Reject sampling schemes|url=https://archive.org/details/bub_gb_wnXtK_LRbO0C|anno=2004|editore=Institute of Mathematical Statistics|pp=[https://archive.org/details/bub_gb_wnXtK_LRbO0C/page/n360 342]–347|ISBN=9780940600614|DOI=10.1214/lnms/1196285403}}</ref><ref name="radford03">{{Cita pubblicazione|autore=Neal|nome=Radford M.|anno=2003|titolo=Slice Sampling|url=https://archive.org/details/sim_annals-of-statistics_2003-06_31_3/page/705|rivista=[[Annals of Statistics]]|volume=31|numero=3|pp=705–767705-767|doi=10.1214/aos/1056562461}}</ref><ref name="bishop06">{{Cita libro|autore=Bishop|nome=Christopher|titolo=Pattern Recognition and Machine Learning|url=https://archive.org/details/patternrecogniti0000bish|anno=2006|editore=Springer|capitolo=11.4: Slice sampling|ISBN=978-0-387-31073-2}}</ref> Si noti che questa proprietà può essere estesa a funzioni in N-dimensioni.

== Descrizione ==

Riga 14:

Questo algoritmo può essere utilizzato per campionare dall'area sotto qualsiasi curva, indipendentemente dal fatto che l'integrale della funzione abbia valore 1. In effetti, il ridimensionamento di una funzione con una costante non ha alcun effetto sulle posizioni x campionate. Pertanto, l'algoritmo può essere utilizzato per campionare da una distribuzione la cui [[Normalizzazione (matematica)|costante di normalizzazione]] è sconosciuta, che è comune nella [[statistica computazionale]].

Come semplice esempio geometrico, supponiamo di voler generare un punto casuale all'interno del cerchio unitario. Il primo step è generare un punto candidato (<math>(x,y)</math><math>x,y </math>) dove <math>x </math> <math>x </math>e <math>y </math> <math>y </math> sono indipendenti e uniformemente distribuiti tra -1 e 1. Se <math>x^2+y^2 \leq 1 </math> allora il punto è all'interno del cerchio unitario ed è accettato, altrimenti è rifiutato e viene generato un nuovo candidato.

Un esempio più complicato utilizzato per generare in modo efficiente [[Numeri pseudo-casuali|numeri pseudocasuali]] [[Distribuzione normale|normalmente distribuiti]] è l'[[algoritmo ziggurat]].

== Algoritmo ==

L'algoritmo di rejection sampling genera valori di campionamento da una distribuzione target <math>X </math> con [[funzione di densità di probabilità]] arbitraria <math>f(x) </math> utilizzando una [[proposal distribution]] <math>Y </math> con densità di probabilità <math>g(x) </math>.

L'algoritmo (usato da [[John von Neumann]] e risalente a Buffon e al [[Ago di Buffon|suo ago]]) per ottenere un campione dalla distribuzione <math>X </math> con densità <math>f(x)</math> utilizzando campioni dalla distribuzione <math>Y </math> con densità <math>g(x) </math> è il seguente:

* Campiona <math display="inline">y</math> dalla distribuzione <math>Y </math>e un campione <math display="inline">u </math> a partire da <math>\mathrm{Unif}(0,1)</math> (distribuzione uniforme sull'intervallo <math>[0,1]</math>).