Metodo di rigetto

Il metodo di rigetto è un metodo utilizzato nel campo della probabilità .

Obbiettivo

Il metodo di rigetto viene utilizzato per generare indirettamente una variabile casuale , di densità di probabilità quando non si sa come simulare direttamente la legge della densità di probabilità (questo è il caso ad esempio se non è una densità classica, ma anche per la legge di Gauss ) . X{\ displaystyle X} f,{\ displaystyle f,} f{\ displaystyle f}f{\ displaystyle f}

Sia una coppia di variabili casuali indipendenti tracciate secondo una legge uniforme , cioè un punto disegnato uniformemente nel quadrato unitario. Possiamo quindi mostrare che la distribuzione di è la distribuzione condizionale della conoscenza dell'evento (Y,U){\ displaystyle (Y, U)}(Y,U){\ displaystyle (Y, U)}X{\ displaystyle X}Y{\ displaystyle Y}

M={U≤fX(Y)}.{\ displaystyle M = \ {U \ leq f_ {X} (Y) \}.}

In altre parole,

fX(X)=fY(X|M).{\ displaystyle {f_ {X} (x) = f_ {Y} (x | M)}.}

Per simulare una serie di variabili aleatorie reali con distribuzione identica a quella di, è quindi sufficiente, in una serie di estrazioni di coppie uniformi indipendenti, selezionare quelle corrispondenti alle estrazioni verificanti e scartare le altre. (Xnon)non≥1{\ displaystyle \ left (X_ {n} \ right) _ {n \ geq 1}}X,{\ displaystyle X,}(Yio,Uio){\ displaystyle (Y_ {i}, U_ {i})}Yio{\ displaystyle Y_ {i}} (Yio,Uio){\ displaystyle (Y_ {i}, U_ {i})}M,{\ displaystyle M,}

Algoritmo

Vorremmo simulare una variabile casuale reale con densità di probabilità . Noi assumiamo X{\ displaystyle X} f{\ displaystyle f}

• che esiste un'altra densità di probabilità tale che il rapporto sia limitato, ad esempio da (cioè ),g{\ displaystyle g}fg{\ displaystyle {\ frac {f} {g}}}vs{\ displaystyle c}f≤vsg{\ displaystyle f \ leq cg}
• che sappiamo come simulare la densitàY{\ displaystyle Y}g.{\ displaystyle g.}

La versione base del metodo di rifiuto assume la forma seguente:

1. Fibbia :
   • Tirare la densitàY{\ displaystyle Y}g;{\ displaystyle g;}
   • Disegna secondo la legge uniforme U (0; 1), indipendentemente daU{\ displaystyle U}Y;{\ displaystyle Y;}
2. Finché riprendi in 1;U>f(Y)vsg(Y),{\ displaystyle U> {\ tfrac {f (Y)} {c \, g (Y)}},}
3. Accetta come estrazione casuale della densità di probabilitàY{\ displaystyle Y}f.{\ displaystyle f.}

Notare che l'algoritmo include un ciclo la cui condizione si riferisce a variabili casuali. Il numero di iterazioni , notiamolo, è quindi esso stesso casuale. Possiamo mostrare che segue la legge geometrica del parametro, ad es. NON,{\ displaystyle N,}NON{\ displaystyle N}1vs,{\ displaystyle {\ frac {1} {c}},}

P(NON=K) = (1-1vs)K-11vs 1K≥1.{\ Displaystyle \ mathbb {P} \ left (N = k \ right) \ = \ \ left (1 - {\ tfrac {1} {c}} \ right) ^ {k-1} \, {\ tfrac { 1} {c}} \ 1_ {k \ geq 1}.}

In effeti,

1vs = ∫Rf(y)vsg(y) g(y)dy = ∫RP(U≤f(y)vsg(y)) g(y)dy = P(U≤f(Y)vsg(Y)){\ displaystyle {\ frac {1} {c}} \ = \ \ int _ {\ mathbb {R}} \, {\ tfrac {f (y)} {c \, g (y)}} \ g ( y) \, dy \ = \ \ int _ {\ mathbb {R}} \, \ mathbb {P} \ left (U \ leq {\ tfrac {f (y)} {c \, g (y)}} \ right) \ g (y) \, dy \ = \ \ mathbb {P} \ left (U \ leq {\ tfrac {f (Y)} {c \, g (Y)}} \ right)}

è la probabilità che, durante un'iterazione, per completare il ciclo, e quindi ad accettare Y . Quindi, l' aspettativa di (cioè il numero medio di iterazioni da eseguire prima di ottenere una realizzazione della densità f ) è valida . NON{\ displaystyle N}vs{\ displaystyle c}

E[NON] = vs.{\ displaystyle \ mathbb {E} \ sinistra [N \ destra] \ = \ c.}

Abbiamo quindi tutto l'interesse a scegliere c il più piccolo possibile. In pratica, una volta scelta la funzione g , la scelta migliore di c è quindi la più piccola costante che aumenta il rapporto f / g , ovvero:

vs=supf(X)g(X).{\ Displaystyle c = \ sup {\ frac {f (x)} {g (x)}}.}

Nota che, o c è maggiore di 1, oppure f = g , essendo la seconda soluzione abbastanza teorica: infatti, comevsg-f≥0,{\ displaystyle cg-f \ geq 0,}

0 ≤ ∫R(vsg-f) = vs ∫Rg - ∫Rf = vs-1.{\ Displaystyle 0 \ \ leq \ \ int _ {\ mathbb {R}} \ left (cg-f \ right) \ = \ c \ \ int _ {\ mathbb {R}} g \ - \ \ int _ { \ mathbb {R}} f \ = \ c-1.}

È quindi nell'interesse di scegliere c il più vicino possibile a 1, in modo che anche il numero medio di iterazioni sia vicino a 1. Insomma, la scelta della busta g è fondamentale:

• il disegno della legge g deve essere facile;
• la valutazione di f ( x ) / g ( x ) deve essere facile;
• la costante c deve essere la più piccola possibile;
• la funzione cg deve aumentare la densità f .

Gli ultimi due punti portano alla ricerca di una funzione g il cui grafico "coincide" strettamente con quello di f .

Generalizzazioni

Il fatto che può essere scritto come dove h è una funzione con valori in [0; 1]. Sostituiamo il passaggio 2 dell'algoritmo iniziale con la condizione: f(X)≤vsg(X){\ displaystyle f (x) \ leq cg (x)}f(X)=vsg(X)h(X){\ displaystyle f (x) = cg (x) h (x)}

Finché , riprendi tra 1U/h(X)>1{\ displaystyle U / h (X)> 1}

Un'altra generalizzazione può essere presa in considerazione quando la valutazione del rapporto f / g è delicata. Proviamo quindi a inquadrare la funzione f con due funzioni facilmente valutabili:

h1(X)≤f(X)≤h2(X){\ displaystyle h_ {1} (x) \ leq f (x) \ leq h_ {2} (x)}

pur assumendo che esista una densità g tale che . Non sono necessarie altre ipotesi; in particolare, non si dovrebbe imporlo . L'algoritmo assume quindi la seguente forma: f(X)≤vsg(X){\ displaystyle f (x) \ leq cg (x)}h2(X)≤vsg(X){\ displaystyle h_ {2} (x) \ leq cg (x)}

1. Continuazione: = vero
2. Mentre Suite
   • disegnare Y lungo g ;
   • disegnare U secondo la legge uniforme U (0; 1), indipendentemente da Y ;
   • Z  : = U cg ( Y );
   • Continuazione: = IF ( , true, false);Z≤h1(Y){\ displaystyle Z \ leq h_ {1} (Y)}
   • Se Continua allora
     • If then Continuazione: = IF ( , true, false) end ifZ≤h2(Y){\ displaystyle Z \ leq h_ {2} (Y)} Z≤f(Y){\ displaystyle Z \ leq f (Y)}
   • Finisci se
3. finire mentre
4. restituisce Y come pull di f .

In questo algoritmo, le funzioni h consentono di ricorrere a un confronto con f (e quindi alla sua valutazione) solo molto raramente.

Vedi anche

Bibliografia

• Robert, CP e Casella, G. "Monte Carlo Statistical Methods" (seconda edizione). New York: Springer-Verlag, 2004.
• J. von Neumann, "Varie tecniche usate in connessione con cifre casuali. Metodi Monte Carlo", Nat. Bureau Standards, 12 (1951), pagg. 36–38.
• Komla Domelevo [1]
• Luc Devroye. Generazione di variabili casuali non uniformi. New York: Springer-Verlag, 1986. ( sito ) Vedi capitolo 2 , sezione 3, p. 40

Articoli Correlati

• Metodo della trasformazione inversa e suo grafico
• Algoritmo di Metropolis-Hastings

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">