Metode for avvisning

Den avvisning metode er en metode som brukes på området sannsynlighet .

Mål

Avvisningsmetoden brukes til indirekte å generere en tilfeldig variabel , av sannsynlighetstetthet når man ikke vet hvordan man direkte skal simulere loven om sannsynlighetstetthet (dette er for eksempel tilfellet hvis det ikke er en klassisk tetthet, men også for Gauss lov ) . X{\ displaystyle X} f,{\ displaystyle f,} f{\ displaystyle f}f{\ displaystyle f}

La være et par uavhengige tilfeldige variabler tegnet i henhold til en ensartet lov , dvs. er et punkt tegnet jevnt i enhetsfeltet. Vi kan da vise at fordelingen av er den betingede fordelingen av å kjenne hendelsen (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) \}.}

Med andre ord,

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

For å simulere en serie med reelle tilfeldige variabler med identisk fordeling som den, er det derfor tilstrekkelig, i en serie tegninger av uavhengige ensartede par , å velge de som tilsvarer trekkene som bekrefter og å avvise de andre. (Xikke)ikke≥1{\ displaystyle \ left (X_ {n} \ right) _ {n \ geq 1}}X,{\ displaystyle X,}(YJeg,UJeg){\ displaystyle (Y_ {i}, U_ {i})}YJeg{\ displaystyle Y_ {i}} (YJeg,UJeg){\ displaystyle (Y_ {i}, U_ {i})}M,{\ displaystyle M,}

Algoritme

Vi vil gjerne simulere en reell tilfeldig variabel med sannsynlighetstetthet . Vi antar X{\ displaystyle X} f{\ displaystyle f}

• at det er en annen sannsynlighetstetthet slik at forholdet er avgrenset, si av (dvs. ),g{\ displaystyle g}fg{\ displaystyle {\ frac {f} {g}}}vs.{\ displaystyle c}f≤vs.g{\ displaystyle f \ leq cg}
• at vi vet hvordan vi kan simulere tetthetY{\ displaystyle Y}g.{\ displaystyle g.}

Den grunnleggende versjonen av avvisningsmetoden har følgende form:

1. Spenne :
   • Trekk tetthetY{\ displaystyle Y}g;{\ displaystyle g;}
   • Tegn i henhold til den ensartede loven U (0; 1), uavhengig avU{\ displaystyle U}Y;{\ displaystyle Y;}
2. Så lenge gjenoppta i 1;U>f(Y)vs.g(Y),{\ displaystyle U> {\ tfrac {f (Y)} {c \, g (Y)}},}
3. Godta som en tilfeldig tegning av sannsynlighetstetthetY{\ displaystyle Y}f.{\ displaystyle f.}

Merk at algoritmen består av en sløyfe hvis tilstand er relatert til tilfeldige variabler. Den antall gjentakelser , la oss oppmerksom på det, er derfor i seg selv tilfeldig. Vi kan vise at følger den geometriske loven til parameteren, dvs. IKKE,{\ displaystyle N,}IKKE{\ displaystyle N}1vs.,{\ displaystyle {\ frac {1} {c}},}

P(IKKE=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}.}

Faktisk,

1vs. = ∫Rf(y)vs.g(y) g(y)dy = ∫RP(U≤f(y)vs.g(y)) g(y)dy = P(U≤f(Y)vs.g(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)}} \ høyre) \ g (y) \, dy \ = \ \ mathbb {P} \ venstre (U \ leq {\ tfrac {f (Y)} {c \, g (Y)}} \ høyre)}

er sannsynligheten for at, i løpet av en iterasjon, for å fullføre sløyfen, og derfor til å akseptere Y . Derfor er forventningen om (dvs. gjennomsnittlig antall iterasjoner som skal utføres før man oppnår en realisering av tettheten f ) . IKKE{\ displaystyle N}vs.{\ displaystyle c}

E[IKKE] = vs..{\ displaystyle \ mathbb {E} \ left [N \ right] \ = \ c.}

Vi har derfor all interesse i å velge c så lite som mulig. I praksis, når funksjonen g er valgt, er det beste valget av c derfor den minste konstanten som øker forholdet f / g , det vil si:

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

Merk at enten c er større enn 1, eller f = g , den andre løsningen er ganske teoretisk: faktisk somvs.g-f≥0,{\ displaystyle cg-f \ geq 0,}

0 ≤ ∫R(vs.g-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.}

Det er derfor i interessen å velge c så nær 1 som mulig, slik at gjennomsnittlig antall iterasjoner også er nær 1. Kort sagt, valg av konvolutt g er viktig:

• tegningen av loven g må være enkel;
• evalueringen av f ( x ) / g ( x ) må være enkel;
• konstanten c må være så liten som mulig;
• funksjonen cg må øke tettheten f .

De to siste punktene fører til å lete etter en funksjon g hvis graf nøye "samsvarer" med f .

Generaliseringer

Det faktum som kan skrives som hvor h er en funksjon med verdier i [0; 1]. Vi erstatter trinn 2 i den opprinnelige algoritmen med tilstanden: f(x)≤vs.g(x){\ displaystyle f (x) \ leq cg (x)}f(x)=vs.g(x)h(x){\ displaystyle f (x) = cg (x) h (x)}

Så lenge , gjenoppta om 1U/h(X)>1{\ displaystyle U / h (X)> 1}

En annen generalisering kan vurderes når vurderingen av forholdet f / g er delikat. Vi prøver deretter å ramme funksjonen f av to funksjoner som er lette å evaluere:

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

mens vi antar at det er en tetthet g slik at . Ingen annen antagelse er nødvendig; spesielt bør man ikke pålegge det . Algoritmen tar deretter følgende form: f(x)≤vs.g(x){\ displaystyle f (x) \ leq cg (x)}h2(x)≤vs.g(x){\ displaystyle h_ {2} (x) \ leq cg (x)}

1. Fortsettelse: = sant
2. Mens Suite
   • trekk Y langs g ;
   • tegne U i henhold til den enhetlige loven U (0; 1), uavhengig av Y ;
   • Z  : = U cg ( Y );
   • Fortsettelse: = IF ( , true, false);Z≤h1(Y){\ displaystyle Z \ leq h_ {1} (Y)}
   • Hvis fortsetter da
     • Hvis deretter Fortsettelse: = HVIS ( , sant, usant) slutter hvisZ≤h2(Y){\ displaystyle Z \ leq h_ {2} (Y)} Z≤f(Y){\ displaystyle Z \ leq f (Y)}
   • Slutt om
3. slutt mens
4. returnerer Y som et trekk av f .

I denne algoritmen gjør funksjonene h det mulig å ty til en sammenligning med f (og derfor til dens evaluering) bare veldig sjelden.

Se også

Bibliografi

• Robert, CP og Casella, G. "Monte Carlo Statistical Methods" (andre utgave). New York: Springer-Verlag, 2004.
• J. von Neumann, "Ulike teknikker brukt i forbindelse med tilfeldige sifre. Monte Carlo-metoder", Nat. Bureau Standards, 12 (1951), s. 36–38.
• Komla Domelevo [1]
• Luc Devroye. Ikke-enhetlig tilfeldig variasjonsgenerering. New York: Springer-Verlag, 1986. ( side ) Se kapittel 2 , seksjon 3, s. 40

Relaterte artikler

• Invers transformasjonsmetode og dens graf
• Metropolis-Hastings algoritme

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