Cursul 4. Simulare: metoda Monte Carlo, metoda inversă, metoda respingerii, transformări

Slide-urile cursului 4
Deschide slide-urile pe tot ecranul În prezentare: ← → navigare, F ecran complet, M meniu, O privire de ansamblu.
Planul cursului

A simula o variabilă aleatoare înseamnă a produce, cu ajutorul calculatorului, numere care se comportă ca realizări independente ale ei. Simularea este un instrument de lucru cotidian al statisticianului: cu ea aproximăm repartiția de eșantionare a unei statistici atunci când calculul exact este prea dificil, comparăm estimatori prin eroarea lor pătratică medie, estimăm probabilitatea de acoperire a unui interval de încredere sau puterea unui test și calculăm integrale. În Cursul 3 am demonstrat că există șiruri de variabile aleatoare independente cu orice repartiții date, plecând de la un șir de uniforme independente și de funcția cuantilă. Azi facem acest rezultat constructiv: arătăm cum se transformă, efectiv și eficient, uniforme independente în variabile (și vectori) cu repartiția dorită și de ce media empirică a unor simulări independente aproximează o medie teoretică.

Obiectivele cursului sunt următoarele:

  1. să înțelegem ce sunt numerele pseudo-aleatoare și să demonstrăm principiul Monte Carlo: estimatorul, nedeplasarea, consistența, eroarea standard \(\sigma/\sqrt N\), intervalul aproximativ și volumul simulării;
  2. să aplicăm metoda inversă (bazată pe funcția cuantilă din Cursul 3) pentru repartiții discrete și continue: exponențială, Cauchy, geometrică, Poisson și altele;
  3. să demonstrăm corectitudinea metodei respingerii: repartiția uniformă pe o mulțime, repartiția primului punct dintr-un șir care cade într-o mulțime dată, cazul repartițiilor cu densitate, numărul mediu de încercări și alegerea propunerii;
  4. să simulăm prin transformări: criteriul de factorizare a densității comune, metoda Box–Muller pentru repartiția normală, sume de exponențiale (Gamma) și de pătrate de normale (\(\chi^2\));
  5. să recunoaștem, pentru o repartiție dată, metoda potrivită (ce trebuie cunoscut despre repartiție și cât costă o observație) și să verificăm în R, prin simulare, rezultatele teoretice: rate de acceptare, medii, cuantile, histograme.

Secțiunile: recapitulare; numere pseudo-aleatoare și principiul Monte Carlo; metoda inversă; metoda respingerii; simulare prin transformări; exerciții rezolvate. Referințe: (Casella and Berger 2002, sec. 5.6), (Knight 2000, sec. 2.3, §2.6), (Robert and Casella 2004, cap. 2–3), (Devroye 1986).

1 Recapitulare

Folosim notațiile din Cursul 1: \(U\sim\Unif(0,1)\) are funcția de repartiție \(F_U(t)=t\) pentru \(t\in[0,1]\); \(\phi\) și \(\Phi\) sunt densitatea și funcția de repartiție ale lui \(\Norm(0,1)\), iar \(z_\gamma=\Phi^{-1}(\gamma)\) este cuantila ei de ordin \(\gamma\); \(\Exp(\lambda)\), \(\GammaD(\alpha,\lambda)\) și \(\Norm(\mu,\sigma^2)\) au densitățile din tabelele Cursului 1.

Rezultate din cursurile anterioare folosite azi

Din Cursul 1:

  • LNM tare (Teorema 61 din Cursul 1): dacă \(Y_1,Y_2,\dots\) sunt i.i.d. cu \(\E|Y_1|<\infty\), atunci \(\bar Y_N=\frac1N\sum_{i=1}^NY_i\asto\E[Y_1]\); TLC (Teorema 64 din Cursul 1): dacă \(\sigma^2=\Var(Y_1)\in(0,\infty)\), atunci \(\sqrt N(\bar Y_N-\E Y_1)/\sigma\dto\Norm(0,1)\); în plus \(\Var(\bar Y_N)=\sigma^2/N\) (Corolarul 43 din Cursul 1); lema lui Slutsky (Teorema 58 din Cursul 1): \(A_N\dto A\) și \(B_N\pto b\) implică \(A_NB_N\dto bA\); teorema aplicațiilor continue (Teorema 57 din Cursul 1);
  • funcții de blocuri disjuncte de v.a. independente sunt independente (Propoziția 39 din Cursul 1); criteriul de factorizare (Propoziția 38 din Cursul 1): v.a. cu densitățile \(f_{X_1},\dots,f_{X_n}\) sunt independente dacă și numai dacă vectorul \((X_1,\dots,X_n)\) are densitatea \(\prod_if_{X_i}(x_i)\);
  • Teorema schimbării de variabilă pentru vectori aleatori (Teorema 52 din Cursul 1), reamintită în Secțiunea 5;
  • f.g.m. a unei sume de v.a. independente este produsul f.g.m. (Propoziția 46 din Cursul 1), iar f.g.m. finită pe o vecinătate a lui \(0\) determină repartiția (Teorema 33 din Cursul 1).

Din Cursul 3, pentru o funcție de repartiție \(F\) pe \(\R\):

  • funcția cuantilă (Definiția 7 din Cursul 3): \(F^{-1}(u)=\inf\{x\in\R:\ F(x)\ge u\}\), \(u\in(0,1)\); lema fundamentală (Lema 8 din Cursul 3): \(F^{-1}(u)\le x\iff u\le F(x)\); dacă \(F\) este continuă și strict crescătoare pe intervalul unde \(0<F<1\), atunci \(F^{-1}(u)\) este unica soluție a ecuației \(F(x)=u\) (Propoziția 9 din Cursul 3);
  • universalitatea uniformei (Teorema 12 din Cursul 3): dacă \(U\sim\Unif(0,1)\), atunci \(F^{-1}(U)\) are funcția de repartiție \(F\), pentru orice \(F\) (discretă, continuă sau mixtă);
  • există un șir de v.a. independente \(\Unif(0,1)\) și, pentru orice șir de repartiții \(\mu_1,\mu_2,\dots\) pe \(\R\), un șir de v.a. independente \(X_n\sim\mu_n\) (Teorema 14 din Cursul 3).

Teorema de existență din Cursul 3 răspunde la o întrebare de principiu: modelul „eșantion i.i.d. din \(F\)” nu este vid. Azi ne interesează întrebarea practică: cum producem, cu un calculator, realizări ale unui astfel de eșantion și cum le folosim pentru a calcula (aproximativ) medii, probabilități și integrale? Începem cu sursa de „hazard” a calculatorului și cu principiul Monte Carlo, care justifică folosirea simulărilor; apoi construim, pe rând, cele trei familii de metode: inversă, respingere și transformări.

2 Numere pseudo-aleatoare și principiul Monte Carlo

2.1 Numere pseudo-aleatoare

Un calculator este o mașină deterministă, deci nu poate produce „hazard” adevărat. Ceea ce folosim în practică sunt numere pseudo-aleatoare: un generator este un algoritm care, pornind de la o valoare inițială numită sămânță (engl. seed), produce printr-o relație de recurență deterministă un șir \(u_1,u_2,\dots\in(0,1)\) care trece cu succes un număr mare de teste statistice de uniformitate și de independență. Primele generatoare folosite pe scară largă au fost cele congruențiale liniare (fiecare termen se obține din precedentul printr-o înmulțire, o adunare și reducerea modulo un întreg mare); generatorul implicit din R este Mersenne-Twister (Matsumoto și Nishimura, 1998), cu perioada \(2^{19937}-1\) (Robert and Casella 2004, cap. 2).

În R, funcția runif(n) întoarce \(n\) numere pseudo-aleatoare uniforme pe \((0,1)\), iar set.seed() fixează sămânța și face simulările reproductibile: aceeași sămânță produce același șir. De aceea fiecare simulare din aceste note începe cu un apel set.seed(...). În restul cursului presupunem, ca idealizare, că runif produce realizări ale unui șir \(U_1,U_2,\dots\) de variabile aleatoare independente și repartizate \(\Unif(0,1)\) — șirul a cărui existență matematică este asigurată de Teorema 14 din Cursul 3.

Notă istorică

Denumirea de metodă Monte Carlo a fost propusă la Los Alamos, în jurul anului 1946, de S. Ulam, J. von Neumann și N. Metropolis, pentru calculele legate de difuzia neutronilor; von Neumann a introdus și metoda respingerii (1951).

2.2 Principiul Monte Carlo

Fie \(X\) o variabilă aleatoare (sau un vector aleator) cu densitatea \(f\) și \(h\) o funcție măsurabilă; vrem să calculăm \[ I=\E[h(X)]=\int h(x)f(x)\dd x . \] Dacă știm să simulăm \(X_1,\dots,X_N\) independente, cu repartiția lui \(X\), estimatorul Monte Carlo al lui \(I\) este media empirică \[ \hat I_N=\frac1N\sum_{i=1}^N h(X_i). \tag{1}\] În particular, o probabilitate \(\PP(X\in A)=\E[\Ind_A(X)]\) se estimează prin frecvența relativă \(\frac1N\sum_{i=1}^N\Ind_A(X_i)\), iar o integrală \(\int_0^1g(x)\dd x=\E[g(U)]\) prin \(\frac1N\sum_ig(U_i)\).

Propoziția 1 (Principiul Monte Carlo)

Fie \(X_1,X_2,\dots\) variabile aleatoare (sau vectori aleatori) \(\iid\) cu repartiția lui \(X\) și \(h\) măsurabilă cu \(\E|h(X)|<\infty\). Atunci:

  1. \(\E[\hat I_N]=I\) și \(\hat I_N\asto I\) când \(N\to\infty\);
  2. dacă, în plus, \(\sigma^2=\Var(h(X))\in(0,\infty)\), atunci \(\Var(\hat I_N)=\sigma^2/N\) și \[ \sqrt N\,\frac{\hat I_N-I}{\hat\sigma_N}\dto\Norm(0,1),\qquad \hat\sigma_N^2=\frac{1}{N-1}\sum_{i=1}^N\big(h(X_i)-\hat I_N\big)^2 ; \]
  3. în consecință, pentru \(\alpha\in(0,1)\), intervalul \[ \Big[\hat I_N-z_{1-\alpha/2}\frac{\hat\sigma_N}{\sqrt N},\ \hat I_N+z_{1-\alpha/2}\frac{\hat\sigma_N}{\sqrt N}\Big] \tag{2}\] conține valoarea \(I\) cu o probabilitate care tinde la \(1-\alpha\) când \(N\to\infty\).

Demonstrație. Ideea demonstrației. Estimatorul \(\hat I_N\) este media empirică a variabilelor \(Y_i=h(X_i)\), care sunt i.i.d. cu media \(I\); toate afirmațiile sunt consecințe ale rezultatelor limită din Cursul 1 aplicate șirului \((Y_i)\). Nedeplasarea vine din liniaritatea mediei, convergența a.s. din LNM tare, iar normalitatea asimptotică din TLC. Înlocuirea lui \(\sigma\) cu estimatorul consistent \(\hat\sigma_N\) este permisă de lema lui Slutsky, iar intervalul se obține rescriind evenimentul „intervalul conține \(I\)” cu ajutorul statisticii standardizate.

Pasul 0: variabilele \(Y_i\). Deoarece \(X_1,X_2,\dots\) sunt independente și identic repartizate, iar \(h\) este măsurabilă, și \(Y_1,Y_2,\dots\) sunt independente (Propoziția 39 din Cursul 1) și identic repartizate (pentru orice borelian \(B\), \(\PP(Y_i\in B)=\PP(X_i\in h^{-1}(B))\) nu depinde de \(i\)), cu \(\E|Y_1|=\E|h(X)|<\infty\) și \(\E[Y_1]=I\). Cu această notație \(\hat I_N=\bar Y_N\).

Pasul 1: nedeplasarea și convergența a.s. Din liniaritatea mediei, \[ \E[\hat I_N]=\frac1N\sum_{i=1}^N\E[Y_i]=\frac1N\cdot N\cdot I=I . \] Cum \(Y_i\) sunt \(\iid\) și integrabile, LNM tare (Teorema 61 din Cursul 1) dă \(\bar Y_N\asto\E[Y_1]=I\). Pentru acest punct este suficientă ipoteza \(\E|h(X)|<\infty\).

Pasul 2: varianța lui \(\hat I_N\). Dacă \(\sigma^2=\Var(Y_1)<\infty\), atunci, din formula varianței sumei și din faptul că \(\Cov(Y_i,Y_j)=0\) pentru \(i\ne j\) (independență), \[ \Var(\hat I_N)=\frac{1}{N^2}\Var\Big(\sum_{i=1}^NY_i\Big)=\frac{1}{N^2}\Big(\sum_{i=1}^N\Var(Y_i)+\sum_{i\neq j}\Cov(Y_i,Y_j)\Big)=\frac{1}{N^2}\big(N\sigma^2+0\big)=\frac{\sigma^2}{N} \] (este Corolarul 43 din Cursul 1).

Pasul 3: normalitatea asimptotică cu \(\sigma\) cunoscut. TLC (Teorema 64 din Cursul 1) pentru șirul \(\iid\) \((Y_i)\), de medie \(I\) și varianță \(\sigma^2\in(0,\infty)\), dă \[ \sqrt N\,\frac{\hat I_N-I}{\sigma}=\frac{\sum_{i=1}^NY_i-NI}{\sigma\sqrt N}\dto\Norm(0,1). \]

Pasul 4: consistența lui \(\hat\sigma_N^2\). Dezvoltând pătratul și folosind \(\sum_iY_i=N\bar Y_N\), \[ \hat\sigma_N^2=\frac{1}{N-1}\Big(\sum_{i=1}^NY_i^2-2\bar Y_N\sum_{i=1}^NY_i+N\bar Y_N^2\Big)=\frac{N}{N-1}\Big(\frac1N\sum_{i=1}^NY_i^2-\bar Y_N^2\Big). \] Variabilele \(Y_i^2\) sunt \(\iid\) (funcții boreliene de \(X_i\), ca la Pasul 0) și integrabile: din \(\Var(Y_1)=\E[Y_1^2]-(\E Y_1)^2\) avem \(\E[Y_1^2]=\sigma^2+I^2<\infty\). Din LNM tare (Teorema 61 din Cursul 1), \(\frac1N\sum_iY_i^2\asto\sigma^2+I^2\); din Pasul 1 și teorema aplicațiilor continue (Teorema 57 din Cursul 1, cu \(t\mapsto t^2\)), \(\bar Y_N^2\asto I^2\). Cele două convergențe au loc simultan pe intersecția a două evenimente de probabilitate \(1\), care are tot probabilitatea \(1\); pe ea, șirul numeric \(\frac{N}{N-1}\big(\frac1N\sum_iY_i^2-\bar Y_N^2\big)\) converge la produsul limitelor factorilor, iar \(\frac{N}{N-1}\to1\). Deci \[ \hat\sigma_N^2\asto 1\cdot\big(\sigma^2+I^2-I^2\big)=\sigma^2 , \] iar, cu funcția continuă \(t\mapsto\sqrt t\) pe \([0,\infty)\), \(\hat\sigma_N\asto\sigma\). Cum \(\sigma>0\), pe evenimentul de convergență avem \(\hat\sigma_N>0\) de la un rang încolo și \(\sigma/\hat\sigma_N\to1\) (funcția \(t\mapsto\sigma/t\) este continuă în \(t=\sigma\)); în particular \(\sigma/\hat\sigma_N\pto1\), deoarece convergența a.s. implică convergența în probabilitate (Teorema 56 din Cursul 1). Raportul din enunț este deci bine definit pentru \(N\) suficient de mare; pe evenimentul \(\{\hat\sigma_N=0\}\), a cărui probabilitate tinde la \(0\), îi putem da o valoare arbitrară, fără a schimba limita în repartiție.

Pasul 5: înlocuirea lui \(\sigma\) cu \(\hat\sigma_N\). Scriem \[ \sqrt N\,\frac{\hat I_N-I}{\hat\sigma_N}=\underbrace{\sqrt N\,\frac{\hat I_N-I}{\sigma}}_{\dto\Norm(0,1)}\cdot\underbrace{\frac{\sigma}{\hat\sigma_N}}_{\pto1}\ \dto\ \Norm(0,1), \] din lema lui Slutsky (Teorema 58 din Cursul 1).

Pasul 6: intervalul. Fie \(Z\sim\Norm(0,1)\), \(z=z_{1-\alpha/2}\) și \(W_N=\sqrt N\,(\hat I_N-I)/\hat\sigma_N\). Pe \(\{\hat\sigma_N>0\}\), înmulțind cu \(\sqrt N/\hat\sigma_N>0\), \[ \hat I_N-z\frac{\hat\sigma_N}{\sqrt N}\le I\iff W_N\le z,\qquad I\le\hat I_N+z\frac{\hat\sigma_N}{\sqrt N}\iff W_N\ge-z , \] deci evenimentul „intervalul (2) conține \(I\)” se rescrie \[ \Big\{\hat I_N-z\frac{\hat\sigma_N}{\sqrt N}\le I\le\hat I_N+z\frac{\hat\sigma_N}{\sqrt N}\Big\}=\Big\{\Big|\sqrt N\,\frac{\hat I_N-I}{\hat\sigma_N}\Big|\le z\Big\}. \] Egalitatea are loc pe \(\{\hat\sigma_N>0\}\); cele două evenimente pot diferi doar pe \(\{\hat\sigma_N=0\}\), a cărui probabilitate tinde la \(0\) (Pasul 4), deci diferența probabilităților lor tinde la \(0\). Din Pasul 5, \(W_N\dto Z\), iar funcția \(|\cdot|\) este continuă, deci \(|W_N|\dto|Z|\) (Teorema 57 din Cursul 1). Funcția de repartiție a lui \(|Z|\) este \(\PP(|Z|\le t)=\Phi(t)-\Phi(-t)=2\Phi(t)-1\) pentru \(t\ge0\) (din \(\Phi(-t)=1-\Phi(t)\)), continuă în orice punct, iar convergența în repartiție înseamnă convergența funcțiilor de repartiție în punctele de continuitate ale limitei (Definiția 55 din Cursul 1). Deci \[ \PP\Big(\Big|\sqrt N\,\frac{\hat I_N-I}{\hat\sigma_N}\Big|\le z\Big)\ \xrightarrow[N\to\infty]{}\ \PP(|Z|\le z)=2\Phi(z_{1-\alpha/2})-1=2\Big(1-\frac\alpha2\Big)-1=1-\alpha , \] unde am folosit \(\Phi(z_{1-\alpha/2})=1-\frac\alpha2\) (definiția cuantilei). Am obținut astfel toate cele trei afirmații ale propoziției.■

Observație

Consecințe practice ale Propoziției 1:

  • eroarea Monte Carlo (abaterea standard a lui \(\hat I_N\)) este \(\sigma/\sqrt N\): pentru a câștiga o zecimală exactă trebuie să mărim numărul de simulări de \(100\) de ori; rata \(N^{-1/2}\) nu depinde de dimensiunea lui \(X\), ceea ce face metoda competitivă pentru integrale în dimensiune mare (cuadraturile deterministe pierd precizie rapid când dimensiunea crește);
  • pentru a obține, cu probabilitate aproximativ \(1-\alpha\), o eroare cel mult \(\varepsilon\), este suficient ca \[ N\ge\Big(\frac{z_{1-\alpha/2}\,\sigma}{\varepsilon}\Big)^2 ; \tag{3}\] într-adevăr, din TLC, \(\PP(|\hat I_N-I|\le\varepsilon)=\PP\big(\sqrt N|\hat I_N-I|/\sigma\le\varepsilon\sqrt N/\sigma\big)\approx2\Phi(\varepsilon\sqrt N/\sigma)-1\), iar această cantitate este \(\ge1-\alpha\) dacă și numai dacă \(\Phi(\varepsilon\sqrt N/\sigma)\ge1-\frac\alpha2\), adică \(\varepsilon\sqrt N/\sigma\ge z_{1-\alpha/2}\). În practică \(\sigma\) este necunoscut și se înlocuiește cu estimația \(\hat\sigma_{N_0}\) dintr-o simulare-pilot de volum mic \(N_0\).

Ipotezele Propoziției 1 sunt esențiale. Dacă \(\E|h(X)|=\infty\), media \(I\) nu există și media empirică nu se stabilizează (repartiția Cauchy, Exemplul 8). Dacă \(\E|h(X)|<\infty\), dar \(\Var(h(X))=\infty\), estimatorul converge încă a.s., dar eroarea nu mai este de ordinul \(N^{-1/2}\), iar intervalul (2) nu mai are nivelul asimptotic \(1-\alpha\). De exemplu, \(I=\int_0^1x^{-2/3}\dd x=\big[3x^{1/3}\big]_0^1=3=\E[U^{-2/3}]\), dar \(\E[U^{-4/3}]=\int_0^1x^{-4/3}\dd x=\lim_{\varepsilon\searrow0}\big[-3x^{-1/3}\big]_\varepsilon^1=\lim_{\varepsilon\searrow0}3\big(\varepsilon^{-1/3}-1\big)=\infty\): estimatorul este consistent, dar foarte instabil, cu „salturi” mari produse de valorile \(U_i\) apropiate de \(0\), iar repartiția estimațiilor are o coadă dreaptă lungă.

Înainte de exemplul clasic al estimării lui \(\pi\), parcurgem toți pașii metodei pe un caz în care fiecare număr poate fi refăcut cu un calculator de buzunar: scrierea mărimii căutate ca medie, estimația, eroarea standard, intervalul și volumul necesar.

Exemplul 1 (O probabilitate normală calculată prin simulare)

Vrem să estimăm \(I=\PP(0\le Z\le2)\), unde \(Z\sim\Norm(0,1)\), folosind doar numere uniforme. Valoarea din tabele, \(\Phi(2)-\Phi(0)\approx0.4772\), ne servește numai pentru control.

Pasul 1: scriem \(I\) ca medie. Avem \(I=\int_0^2\phi(x)\dd x\). Fie \(V\sim\Unif(0,2)\), cu densitatea \(\frac12\Ind_{[0,2]}\). Din formula de transport (Teorema 22 din Cursul 1), \[ \E\big[2\phi(V)\big]=\int_0^22\phi(x)\cdot\frac12\dd x=\int_0^2\phi(x)\dd x=I , \] deci \(I=\E[h(V)]\), cu \(h(x)=2\phi(x)=\frac{2}{\sqrt{2\pi}}e^{-x^2/2}\approx0.7979\,e^{-x^2/2}\), iar \(V\) se obține dintr-o uniformă standard prin \(V=2U\). (La fel, pentru orice interval mărginit, \(\int_a^bg(x)\dd x=(b-a)\,\E\big[g\big(a+(b-a)U\big)\big]\).)

Pasul 2: estimatorul și ipotezele. Pentru \(U_1,\dots,U_N\) \(\iid\) \(\Unif(0,1)\), estimatorul (1) este \(\hat I_N=\frac1N\sum_{i=1}^Nh(2U_i)\). Funcția \(h\) este descrescătoare pe \([0,2]\), deci \(h(2)\le h(V)\le h(0)\), adică \(0.1080\le h(V)\le0.7979\): variabila \(h(V)\) este mărginită, are medie și varianță finite, iar Propoziția 1 se aplică în întregime.

Pasul 3: un calcul de mână, cu \(N=8\). Să presupunem că generatorul produce cele opt numere \(u_i\) din primul rând al tabelului; calculăm \(v_i=2u_i\) și \(y_i=h(v_i)=0.7979\,e^{-v_i^2/2}\).

\[ \begin{array}{l|cccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ \hline u_i & 0.37 & 0.82 & 0.55 & 0.12 & 0.25 & 0.91 & 0.68 & 0.04\rule{0pt}{2.6ex}\\ v_i=2u_i & 0.74 & 1.64 & 1.10 & 0.24 & 0.50 & 1.82 & 1.36 & 0.08\\ y_i=h(v_i) & 0.6068 & 0.2079 & 0.4357 & 0.7752 & 0.7041 & 0.1523 & 0.3164 & 0.7953 \end{array} \] Suma valorilor \(y_i\) este \(3.9937\), deci estimația este \(\hat I_8=3.9937/8\approx0.4992\). Pentru eroarea ei avem nevoie de abaterea standard empirică: \(\sum_{i=1}^8(y_i-\hat I_8)^2\approx0.4601\), deci \[ \hat\sigma_8^2=\frac{0.4601}{7}\approx0.0657,\qquad\hat\sigma_8\approx0.2564,\qquad\frac{\hat\sigma_8}{\sqrt8}\approx0.0906 . \] Ultimul număr este eroarea standard a estimației: ordinul de mărime al abaterii lui \(\hat I_8\) de la \(I\). Intervalul (2) de nivel aproximativ \(0.95\) este \(0.4992\pm1.96\cdot0.0906\), adică \([0.322,\,0.677]\). El conține valoarea adevărată \(0.4772\), dar este mult prea larg pentru a fi util (iar pentru \(N=8\) nivelul \(0.95\), fiind asimptotic, este doar orientativ): cu opt simulări nu putem garanta nici prima zecimală.

Pasul 4: \(N=10^4\), în R. Repetăm același calcul cu \(10^4\) uniforme.

set.seed(41)
N <- 1e4
y <- 2 * dnorm(2 * runif(N))                 # y_i = h(V_i), cu V_i = 2 U_i
est <- mean(y); se <- sd(y) / sqrt(N)        # estimația și eroarea standard
c(estimatie = est, se = se, IC_inf = est - 1.96 * se,
  IC_sup = est + 1.96 * se, exact = pnorm(2) - 0.5)
#> estimatie        se    IC_inf    IC_sup     exact 
#>  0.474299  0.002304  0.469782  0.478816  0.477250

Citim rezultatul astfel: estimația este \(0.4743\), cu eroarea standard \(0.0023\), deci scriem \(I\approx0.474\pm0.005\) (două erori standard); intervalul \([0.4698,\,0.4788]\) conține valoarea exactă \(0.4772\), iar eroarea efectiv comisă, \(|0.4743-0.4772|=0.0029\), este de aproximativ \(1.3\) erori standard — o abatere cu totul obișnuită. Față de Pasul 3, volumul a crescut de \(1250\) de ori, iar eroarea standard a scăzut de \(0.0906/0.0023\approx39\) de ori, aproximativ \(\sqrt{1250}\approx35\) (diferența vine din faptul că \(\hat\sigma_8\) și \(\hat\sigma_{10^4}\) sunt estimații diferite ale lui \(\sigma\)).

Pasul 5: cât de mare trebuie să fie \(N\)? Aici putem calcula \(\sigma\) exact. Cu schimbarea de variabilă \(x=t/\sqrt2\), \[ \begin{aligned} \E\big[h(V)^2\big]&=\int_0^24\phi(x)^2\cdot\frac12\dd x=\frac1\pi\int_0^2e^{-x^2}\dd x=\frac{1}{\pi\sqrt2}\int_0^{2\sqrt2}e^{-t^2/2}\dd t\\ &=\frac{\sqrt{2\pi}}{\pi\sqrt2}\Big(\Phi(2\sqrt2)-\frac12\Big)=\frac{\Phi(2\sqrt2)-\frac12}{\sqrt\pi}\approx0.2808 , \end{aligned} \] deci \(\sigma^2=\Var(h(V))\approx0.2808-0.4772^2\approx0.0530\) și \(\sigma\approx0.2302\); eroarea standard teoretică pentru \(N=10^4\) este \(\sigma/\sqrt N\approx0.0023\), exact valoarea estimată în R. Pentru o eroare de cel mult \(\varepsilon=0.001\) cu probabilitatea \(0.95\), relația (3) cere \[ N\ge\Big(\frac{1.96\cdot0.2302}{0.001}\Big)^2\approx2.04\cdot10^5 . \] În practică \(\sigma\) nu este cunoscut. Avem două soluții. (i) O margine sigură: dacă \(m\le Y\le M\) și \(c=\frac{m+M}{2}\) este mijlocul intervalului, atunci \(|Y-c|\le\frac{M-m}{2}\) și, din identitatea \(\E[(Y-c)^2]=\Var(Y)+(\E[Y]-c)^2\) (Propoziția 25 din Cursul 1), \(\Var(Y)\le\E[(Y-c)^2]\le\big(\frac{M-m}{2}\big)^2\); aici \(\sigma\le\frac{0.7979-0.1080}{2}\approx0.345\), deci \(N\ge(1.96\cdot0.345/0.001)^2\approx4.6\cdot10^5\) este cu siguranță suficient. (ii) O simulare-pilot: cu \(\hat\sigma_8\approx0.256\) din Pasul 3 am obține \(N\approx(1.96\cdot0.256/0.001)^2\approx2.5\cdot10^5\), apropiat de valoarea corectă.

Ce am aflat. O probabilitate normală a fost calculată fără a simula vreo variabilă normală. Dacă am ști să simulăm \(Z_1,\dots,Z_N\) (vom ști la sfârșitul cursului), estimatorul „natural” ar fi frecvența relativă a evenimentului \(\{0\le Z_i\le2\}\), adică media unor variabile \(\Bern(I)\), cu varianța \(I(1-I)\approx0.2495\) — de \(0.2495/0.0530\approx4.7\) ori mai mare, deci cu de \(4.7\) ori mai multe simulări pentru aceeași precizie. Aceeași mărime se poate scrie ca medie în mai multe feluri, iar reprezentarea cu varianța mai mică este cea preferată; exemplul următor compară sistematic două astfel de reprezentări.

Exemplul 2 (Estimarea lui \(\pi\))

Fie \(U_{i1},U_{i2},V_i\), \(i\ge1\), variabile \(\iid\) \(\Unif(0,1)\) și \[ X_i=\Ind_{\{U_{i1}^2+U_{i2}^2<1\}},\qquad Y_i=\sqrt{1-V_i^2},\qquad \hat\pi_1=\frac4N\sum_{i=1}^NX_i,\qquad \hat\pi_2=\frac4N\sum_{i=1}^NY_i . \]

Primul estimator. Din independența lui \(U_{i1}\) și \(U_{i2}\), cuplul \((U_{i1},U_{i2})\) are densitatea \(\Ind_{[0,1]}(u)\Ind_{[0,1]}(v)\) (Propoziția 38 din Cursul 1), deci \[ \begin{aligned} \PP(X_i=1)&=\iint_{\{u^2+v^2<1\}\cap[0,1]^2}\dd u\dd v=\int_0^1\Big(\int_0^{\sqrt{1-u^2}}\dd v\Big)\dd u=\int_0^1\sqrt{1-u^2}\dd u\\ &\overset{u=\sin t}{=}\int_0^{\pi/2}\cos^2t\dd t=\int_0^{\pi/2}\frac{1+\cos2t}{2}\dd t=\frac\pi4+\Big[\frac{\sin2t}{4}\Big]_0^{\pi/2}=\frac\pi4 , \end{aligned} \] aria sfertului de disc unitate; am folosit teorema lui Fubini pentru integrala dublă (pentru \(u\in[0,1]\) fixat, condiția \(u^2+v^2<1\), \(v\in[0,1]\), înseamnă \(0\le v<\sqrt{1-u^2}\)), apoi schimbarea de variabilă \(u=\sin t\), \(\dd u=\cos t\dd t\), cu \(t\in[0,\frac\pi2]\) și \(\sqrt{1-\sin^2t}=\cos t\ge0\). Așadar \(X_i\sim\Bern(\pi/4)\), iar \(T=\sum_{i=1}^NX_i\sim\Bin(N,\pi/4)\), ca sumă de \(N\) variabile Bernoulli independente, cu \(\E[T]=N\frac\pi4\) și \(\Var(T)=N\frac\pi4\big(1-\frac\pi4\big)\). Cum \(\hat\pi_1=\frac4NT\), \[ \E[\hat\pi_1]=\frac4N\cdot\frac{N\pi}{4}=\pi,\qquad \Var(\hat\pi_1)=\frac{16}{N^2}\cdot N\frac\pi4\Big(1-\frac\pi4\Big)=\frac{\pi(4-\pi)}{N}\approx\frac{2.697}{N}. \]

Al doilea estimator. Variabilele \(Y_i\) sunt \(\iid\), cu valori în \([0,1]\), iar \[ \E[Y_i]=\int_0^1\sqrt{1-v^2}\dd v=\frac\pi4,\qquad \E[Y_i^2]=\int_0^1(1-v^2)\dd v=\Big[v-\frac{v^3}{3}\Big]_0^1=\frac23 , \] (prima integrală a fost calculată mai sus; ambele sunt formula de transport, Teorema 22 din Cursul 1, pentru \(V_i\sim\Unif(0,1)\)). Deci \(\Var(Y_i)=\E[Y_i^2]-(\E[Y_i])^2=\frac23-\frac{\pi^2}{16}\approx0.0498\) și, din liniaritatea mediei și din Propoziția 1 (varianța mediei empirice a \(N\) variabile i.i.d.), \[ \E[\hat\pi_2]=4\cdot\frac\pi4=\pi,\qquad \Var(\hat\pi_2)=\frac{16}{N^2}\cdot N\Big(\frac23-\frac{\pi^2}{16}\Big)=\frac{32/3-\pi^2}{N}\approx\frac{0.797}{N}. \]

Comparația. Ambii estimatori sunt nedeplasați și consistenți tare (Propoziția 1). Varianțele au același numitor, iar \[ \Var(\hat\pi_2)<\Var(\hat\pi_1)\iff\frac{32}{3}-\pi^2<4\pi-\pi^2\iff\frac{32}{3}<4\pi , \] adevărat deoarece \(\frac{32}{3}<12<4\pi\). Raportul varianțelor este \(\frac{\pi(4-\pi)}{32/3-\pi^2}\approx3.38\): pentru aceeași precizie, \(\hat\pi_2\) are nevoie de aproximativ \(3.4\) ori mai puține simulări. Pentru o eroare de cel mult \(0.01\) cu probabilitatea \(0.95\), relația (3), cu \(z_{0.975}=1.96\) și abaterile standard ale unui termen \(\sigma_1=\sqrt{\pi(4-\pi)}\approx1.642\) (pentru \(4X_i\)), respectiv \(\sigma_2=\sqrt{32/3-\pi^2}\approx0.893\) (pentru \(4Y_i\)), cere \(N\ge(1.96\cdot1.642/0.01)^2\approx1.04\cdot10^5\) simulări pentru \(\hat\pi_1\) și doar \(N\ge(1.96\cdot0.893/0.01)^2\approx3.06\cdot10^4\) pentru \(\hat\pi_2\). Motivul: pentru \(v\in[0,1]\) fixat, \(\PP\big(U_{i2}^2<1-v^2\big)=\PP\big(U_{i2}<\sqrt{1-v^2}\big)=\sqrt{1-v^2}\), deci \(Y_i=\PP\big(U_{i2}^2<1-V_i^2\mid V_i\big)\) „integrează” exact una dintre coordonate, în loc să o simuleze; media condiționată a unui indicator de tipul lui \(X_i\) are varianța mai mică (ideea metodei Monte Carlo condiționat).

set.seed(1)
N <- 1e5
x <- (runif(N)^2 + runif(N)^2 < 1)          # X_i: punct în sfertul de disc
y <- sqrt(1 - runif(N)^2)                    # Y_i
est <- c(pi1 = 4 * mean(x), pi2 = 4 * mean(y))
se  <- c(4 * sd(x), 4 * sd(y)) / sqrt(N)     # erori standard Monte Carlo
rbind(estimatie = est, se = se,
      IC_inf = est - 1.96 * se, IC_sup = est + 1.96 * se,
      se_teoretic = sqrt(c(pi * (4 - pi), 32 / 3 - pi^2) / N))
#>                  pi1      pi2
#> estimatie   3.146320 3.140061
#> se          0.005183 0.002830
#> IC_inf      3.136162 3.134514
#> IC_sup      3.156478 3.145609
#> se_teoretic 0.005193 0.002823

Citim rezultatul pe coloane: \(\hat\pi_1\approx3.1463\), cu eroarea standard \(0.0052\) și intervalul \([3.1362,\,3.1565]\); \(\hat\pi_2\approx3.1401\), cu eroarea standard \(0.0028\) și intervalul \([3.1345,\,3.1456]\). Erorile efectiv comise, \(|\hat\pi_1-\pi|\approx0.0047\) și \(|\hat\pi_2-\pi|\approx0.0015\), sunt în ambele cazuri sub o eroare standard. Cu \(N=10^5\) simulări, ambele intervale aproximative de nivel \(0.95\) din (2) conțin valoarea \(\pi\), iar erorile standard estimate sunt foarte apropiate de valorile teoretice \(\sqrt{\pi(4-\pi)/N}\approx0.0052\) și \(\sqrt{(32/3-\pi^2)/N}\approx0.0028\); intervalul pentru \(\hat\pi_2\) este de aproximativ \(\sqrt{3.38}\approx1.8\) ori mai scurt. Figura 1 arată evoluția celor doi estimatori când \(N\) crește.

Arată codul R
set.seed(7); Nmax <- 20000; nn <- 10:Nmax
m1 <- cumsum(4 * (runif(Nmax)^2 + runif(Nmax)^2 < 1)) / seq_len(Nmax)
m2 <- cumsum(4 * sqrt(1 - runif(Nmax)^2)) / seq_len(Nmax)   # medii cumulate
d <- rbind(data.frame(N = nn, est = m1[nn], s = sqrt(pi * (4 - pi)),
                      g = "hat(pi)[1]"),
           data.frame(N = nn, est = m2[nn], s = sqrt(32 / 3 - pi^2),
                      g = "hat(pi)[2]"))
ggplot(d, aes(N, est)) +
  geom_ribbon(aes(ymin = pi - 1.96 * s / sqrt(N),
                  ymax = pi + 1.96 * s / sqrt(N)),
              fill = culori[["gri"]], alpha = 0.25) +
  geom_line(aes(colour = g), linewidth = 0.5, show.legend = FALSE) +
  geom_hline(yintercept = pi, linetype = 2, colour = culori[["rosu"]]) +
  facet_wrap(~g, labeller = label_parsed) +
  scale_colour_manual(values = unname(culori[c("albastru", "verde")])) +
  scale_x_log10() + coord_cartesian(ylim = c(2.8, 3.5)) +
  labs(x = "N (scară logaritmică)", y = "estimația lui π")
Figura 1: Estimațiile Monte Carlo \(\hat\pi_1\) și \(\hat\pi_2\) în funcție de numărul de simulări \(N\) (scară logaritmică). Benzile marchează \(\pi\pm1.96\,\sigma/\sqrt N\): traiectoriile intră în bandă și rămân, în mare, în interiorul ei (LNM și TLC).

În statistică, principiul Monte Carlo se aplică de regulă unei statistici \(T_n=T(X_1,\dots,X_n)\): simulăm \(B\) eșantioane independente de volum \(n\), calculăm statistica pe fiecare și aproximăm orice mărime legată de repartiția ei de eșantionare (\(\E[T_n]\), \(\Var(T_n)\), \(\PP(T_n\in A)\)) prin mărimea empirică corespunzătoare; Propoziția 1, aplicată celor \(B\) valori independente obținute, garantează consistența și dă eroarea standard. Acesta va fi instrumentul nostru de control în toate cursurile următoare.

Principiul Monte Carlo presupune că știm să simulăm \(X_1,\dots,X_N\) cu repartiția dorită. Calculatorul ne dă însă doar uniforme. Trecem acum la problema centrală a cursului: cum transformăm uniforme independente în variabile cu o repartiție dată?

3 Metoda inversă

Teorema de universalitate (Teorema 12 din Cursul 3) spune că, pentru orice funcție de repartiție \(F\), variabila \(F^{-1}(U)\), cu \(U\sim\Unif(0,1)\), are funcția de repartiție \(F\). Aceasta este deja o metodă de simulare, numită metoda inversă (sau metoda transformării inverse):

  1. determinăm funcția cuantilă \(F^{-1}\) (explicit sau printr-un algoritm);
  2. generăm \(U_1,\dots,U_n\) \(\iid\) \(\Unif(0,1)\);
  3. întoarcem \(X_i=F^{-1}(U_i)\), \(i=1,\dots,n\).

Variabilele \(X_1,\dots,X_n\) sunt independente, ca funcții (boreliene, deoarece \(F^{-1}\) este crescătoare) de variabile independente (Propoziția 39 din Cursul 1), și au toate funcția de repartiție \(F\): formează un eșantion din \(F\). Metoda este exactă (nu aproximativă) și folosește o singură uniformă pentru fiecare observație; este practică atunci când \(F^{-1}\) are o expresie explicită sau se calculează eficient. Vom folosi des și observația că \(1-U\sim\Unif(0,1)\) (pentru \(t\in[0,1]\), \(\PP(1-U\le t)=\PP(U\ge1-t)=1-(1-t)=t\)), deci \(F^{-1}(1-U)\) are și ea funcția de repartiție \(F\).

3.1 Cazul variabilelor aleatoare discrete

Fie \(X\) o variabilă aleatoare discretă cu valorile \(x_1<x_2<\cdots\) (în număr finit sau numărabil) și \[ X\sim\begin{pmatrix} x_1 & x_2 & x_3 & \cdots\\ p_1 & p_2 & p_3 & \cdots\end{pmatrix},\qquad s_0=0,\quad s_k=p_1+\cdots+p_k . \] Funcția de repartiție este constantă pe porțiuni: \(F(x)=0\) pentru \(x<x_1\) și \(F(x)=\sum_{j:\,x_j\le x}p_j=s_k\) pentru \(x_k\le x<x_{k+1}\). Fie \(u\in(0,1)\) și \(k\) cel mai mic indice cu \(s_k\ge u\) (există, deoarece \(s_k\nearrow1>u\)); atunci \(s_{k-1}<u\le s_k\). Mulțimea \(\{x:F(x)\ge u\}\) este \([x_k,\infty)\): pentru \(x\ge x_k\) avem \(F(x)\ge F(x_k)=s_k\ge u\), iar pentru \(x<x_k\) avem \(F(x)\le s_{k-1}<u\). Infimumul ei este \(x_k\), deci \[ F^{-1}(u)=x_k\quad\text{dacă } s_{k-1}<u\le s_k,\qquad\text{adică}\qquad F^{-1}(u)=\sum_{k\ge1}x_k\,\Ind_{(s_{k-1},\,s_k]}(u). \]

Propoziția 2 (Metoda inversă pentru variabile discrete)

Dacă \(U\sim\Unif(0,1)\), atunci variabila aleatoare \[ Y=\sum_{k\ge1}x_k\,\Ind_{\{s_{k-1}<U\le s_k\}} \] are aceeași repartiție ca \(X\).

Demonstrație. Este un caz particular al Teoremei 12 din Cursul 3, deoarece, din formula de mai sus, \(Y=F^{-1}(U)\) pe \(\{0<U<1\}\), eveniment de probabilitate \(1\). Dăm și un argument direct, care nu folosește ordinea valorilor. Intervalele \((s_{k-1},s_k]\), \(k\ge1\), sunt disjuncte două câte două, iar reuniunea lor este \((0,1]\) (deoarece \(s_0=0\) și \(s_k\nearrow1\)). Prin urmare, pentru \(U\in(0,1)\), exact un indicator din suma care definește \(Y\) este egal cu \(1\), deci \(Y\) ia valoarea \(x_k\) exact pe evenimentul \(\{s_{k-1}<U\le s_k\}\). Rezultă, pentru orice \(k\ge1\), \[ \PP(Y=x_k)=\PP(s_{k-1}<U\le s_k)=F_U(s_k)-F_U(s_{k-1})=s_k-s_{k-1}=p_k . \] Cum \(\sum_kp_k=1\), \(Y\) ia (a.s.) doar valorile \(x_k\), cu probabilitățile \(p_k\), adică are repartiția lui \(X\).■

Algoritmul corespunzător este o căutare secvențială: generăm \(U\) și îl comparăm succesiv cu \(s_1,s_2,\dots\) până la primul \(k\) cu \(U\le s_k\). Numărul de comparații este \(k\) cu probabilitatea \(p_k\), deci numărul mediu de comparații este \(\sum_k k\,p_k\). Cum demonstrația directă nu folosește ordinea valorilor, putem parcurge valorile în orice ordine; pentru a micșora costul este util să le ordonăm descrescător după probabilități. Pentru o variabilă cu valori în \(\N=\{0,1,2,\dots\}\) avem formula compactă \[ F^{-1}(u)=\#\{i\ge0:\ F(i)<u\}, \tag{4}\] utilă pentru implementări vectorizate. Într-adevăr, dacă \(F^{-1}(u)=k\), atunci \(F(k-1)<u\le F(k)\) (cu \(F(-1)=0\)); cum \(F\) este crescătoare, \(F(i)\le F(k-1)<u\) pentru \(i=0,\dots,k-1\) și \(F(i)\ge F(k)\ge u\) pentru \(i\ge k\), deci exact \(k\) indici \(i\ge0\) verifică \(F(i)<u\).

Exemplul 3 (O repartiție discretă finită)

Fie \(X\sim\begin{pmatrix}1&2&3&4\\0.2&0.5&0.1&0.2\end{pmatrix}\).

Funcția de repartiție și funcția cuantilă. Sumele parțiale sunt \(s_1=0.2\), \(s_2=0.7\), \(s_3=0.8\), \(s_4=1\), deci \[ F(x)=\begin{cases}0, & x<1,\\ 0.2, & 1\le x<2,\\ 0.7, & 2\le x<3,\\ 0.8, & 3\le x<4,\\ 1, & x\ge4,\end{cases} \qquad F^{-1}(u)=\begin{cases}1, & 0<u\le0.2,\\ 2, & 0.2<u\le0.7,\\ 3, & 0.7<u\le0.8,\\ 4, & 0.8<u<1.\end{cases} \] Observăm că \(F^{-1}(u)=1+\Ind_{\{u>0.2\}}+\Ind_{\{u>0.7\}}+\Ind_{\{u>0.8\}}\) (fiecare prag depășit adaugă o unitate), în acord cu (4) aplicată lui \(X-1\). Deci \(X=1+\Ind_{\{U>0.2\}}+\Ind_{\{U>0.7\}}+\Ind_{\{U>0.8\}}\); de exemplu, pentru \(U=0.75\) obținem \(X=1+1+1+0=3\).

Algoritmul, pas cu pas. Să presupunem că generatorul întoarce \(u=0.37\). Căutarea secvențială compară \(u\) cu sumele parțiale, în ordine:

  1. este \(u\le s_1\)? Nu, deoarece \(0.37>0.2\); trecem mai departe;
  2. este \(u\le s_2\)? Da, deoarece \(0.37\le0.7\); ne oprim la \(k=2\).

Valoarea întoarsă este \(X=x_2=2\), după două comparații. Motivul: \(u\) a căzut în intervalul \((s_1,s_2]=(0.2,\,0.7]\), a cărui lungime este tocmai \(p_2=0.5\); cum probabilitatea ca o uniformă să cadă într-un interval din \((0,1)\) este lungimea acestuia, valoarea \(2\) apare cu probabilitatea \(0.5\). Cu alte cuvinte, împărțim \((0,1]\) în bucăți de lungimi \(0.2\), \(0.5\), \(0.1\), \(0.2\) și întoarcem numărul bucății în care cade \(u\). Pentru cinci uniforme succesive obținem: \[ \begin{array}{l|ccccc} u & 0.37 & 0.92 & 0.15 & 0.75 & 0.70\\ \hline \text{intervalul care îl conține} & (0.2,\,0.7] & (0.8,\,1] & (0,\,0.2] & (0.7,\,0.8] & (0.2,\,0.7]\rule{0pt}{2.6ex}\\ \text{valoarea întoarsă } F^{-1}(u) & 2 & 4 & 1 & 3 & 2\\ \text{numărul de comparații} & 2 & 4 & 1 & 3 & 2 \end{array} \] Ultima coloană arată rolul inegalității nestricte din \(s_{k-1}<u\le s_k\): numărul \(u=0.70=s_2\) aparține intervalului \((0.2,\,0.7]\), deci valoarea întoarsă este \(2\), nu \(3\). Convenția este impusă de definiția \(F^{-1}(u)=\inf\{x:\ F(x)\ge u\}\) (aici \(F(2)=0.7\ge u\)), dar nu are importanță practică, deoarece \(\PP(U=s_k)=0\).

Costul căutării secvențiale. Parcurgând valorile în ordinea \(1,2,3,4\), numărul de comparații \(C\) este \(k\) atunci când \(X=k\), deci \[ \E[C]=1\cdot0.2+2\cdot0.5+3\cdot0.1+4\cdot0.2=2.3 . \] În ordinea descrescătoare a probabilităților (\(2,1,4,3\), cu probabilitățile \(0.5,0.2,0.2,0.1\)), \[ \E[C']=1\cdot0.5+2\cdot0.2+3\cdot0.2+4\cdot0.1=1.9 , \] o economie de \((2.3-1.9)/2.3\approx17\%\). Ordinea descrescătoare este optimă. Într-adevăr, o ordine de parcurgere atribuie fiecărei valori \(i\) o poziție \(r_i\in\{1,2,3,4\}\), iar costul ei mediu este \(\sum_ir_ip_i\). Dacă \(p_i<p_j\), dar valoarea \(i\) este testată înaintea lui \(j\) (\(r_i<r_j\)), atunci schimbând între ele pozițiile celor două valori (restul termenilor sumei rămân neschimbați) costul mediu se modifică cu \[ (r_jp_i+r_ip_j)-(r_ip_i+r_jp_j)=p_i(r_j-r_i)-p_j(r_j-r_i)=-(r_j-r_i)(p_j-p_i)<0 , \] adică scade strict. Există doar un număr finit de ordini (\(4!=24\)), deci una dintre ele are costul minim; în ea nu poate exista nicio pereche cu \(p_i<p_j\) și \(r_i<r_j\) (altfel schimbarea de mai sus ar micșora costul), deci probabilitățile sunt descrescătoare de-a lungul pozițiilor. Toate ordinile descrescătoare au același cost (diferă doar prin permutarea unor valori cu probabilități egale), deci fiecare dintre ele este optimă. Același raționament funcționează pentru orice repartiție cu un număr finit de valori.

Funcția de mai jos implementează metoda pentru o repartiție discretă arbitrară; findInterval(u, s, left.open = TRUE) numără sumele parțiale strict mai mici decât \(u\), adică întoarce \(k-1\) pentru \(s_{k-1}<u\le s_k\). Ea este echivalentă cu sample(x, n, replace = TRUE, prob = p).

gen_discret <- function(n, x, p) {
  s <- cumsum(p)                                  # sumele parțiale s_k
  u <- runif(n)
  x[findInterval(u, s, left.open = TRUE) + 1]   # k: s_{k-1} < u <= s_k
}
set.seed(3)
x <- gen_discret(1e5, 1:4, c(0.2, 0.5, 0.1, 0.2))
round(table(x) / 1e5, 3)            # frecvențe relative vs 0.2 0.5 0.1 0.2
#> x
#>     1     2     3     4 
#> 0.201 0.501 0.098 0.200
c(media = mean(x), teoretic = sum(1:4 * c(0.2, 0.5, 0.1, 0.2)))
#>    media teoretic 
#>    2.297    2.300

Frecvențele relative diferă de probabilitățile teoretice cu cel mult câteva unități a treia zecimală, în acord cu eroarea standard \(\sqrt{p_k(1-p_k)/n}\le\sqrt{0.25/10^5}\approx0.0016\), iar media empirică este apropiată de \(\E[X]=2.3\).

Exemplul 4 (Uniforma discretă, Bernoulli și geometrica)

Fie \(U\sim\Unif(0,1)\).

Bernoulli \(\Bern(p)\), \(p\in(0,1)\). Valorile sunt \(x_1=0\), \(x_2=1\), cu \(p_1=1-p\), \(p_2=p\), deci \(s_1=1-p\), \(s_2=1\) și \(F^{-1}(u)=\Ind_{\{u>1-p\}}\): \(X=\Ind_{\{U>1-p\}}\), cu \(\PP(X=1)=1-(1-p)=p\). Înlocuind \(U\) cu \(1-U\) obținem varianta mai des folosită \(X=\Ind_{\{U<p\}}\).

Uniforma discretă pe \(\{1,\dots,N\}\). Aici \(s_k=\frac kN\), iar pentru \(u\in(0,1)\) \[ F^{-1}(u)=k\iff\frac{k-1}{N}<u\le\frac kN\iff k-1<Nu\le k\iff k=\lceil Nu\rceil , \] deci \(X=\lceil NU\rceil\). Cum \(NU\) este întreg doar pe un eveniment de probabilitate \(0\), avem a.s. \(\lceil NU\rceil=\lfloor NU\rfloor+1\) (în R: floor(N * runif(n)) + 1, echivalent cu sample(1:N, n, replace = TRUE)). De exemplu, un zar (\(N=6\)) se simulează prin \(\lceil6U\rceil\): pentru \(u=0.37\) obținem \(\lceil2.22\rceil=3\), în acord cu \(\frac26<0.37\le\frac36\).

Geometrica \(\Geom(p)\) (numărul de încercări până la primul succes, \(\PP(X=k)=(1-p)^{k-1}p\), \(k\ge1\)). Suma geometrică dă, pentru \(k\in\N^*\), \[ F(k)=\sum_{j=1}^k(1-p)^{j-1}p=p\,\frac{1-(1-p)^k}{1-(1-p)}=1-(1-p)^k , \] iar \(F\) este constantă pe fiecare interval \([k,k+1)\). Pentru \(u\in(0,1)\), \(F^{-1}(u)\) este cel mai mic întreg \(k\ge1\) cu \(F(k)\ge u\), iar \[ F(k)\ge u\iff(1-p)^k\le1-u\iff k\ln(1-p)\le\ln(1-u)\iff k\ge\frac{\ln(1-u)}{\ln(1-p)} , \] unde la ultimul pas am împărțit la \(\ln(1-p)<0\), ceea ce schimbă sensul inegalității. Cel mai mic întreg cu această proprietate este partea întreagă superioară, deci \(F^{-1}(u)=\big\lceil\ln(1-u)/\ln(1-p)\big\rceil\) (raportul este strict pozitiv, deci rezultatul este \(\ge1\)). Înlocuind \(1-U\) cu \(U\), \(X=\big\lceil\ln U/\ln(1-p)\big\rceil\sim\Geom(p)\). Cum \(E=-\ln U\sim\Exp(1)\) (Exemplul 7), avem \(X=\lceil E/\mu\rceil\) cu \(\mu=-\ln(1-p)\): repartiția geometrică este „partea întreagă superioară” a unei exponențiale (Delmas 2010, Ex. VII.1).

Un calcul numeric. Pentru \(p=0.3\) și \(u=0.37\): \(\ln(1-u)=\ln0.63\approx-0.4620\) și \(\ln(1-p)=\ln0.7\approx-0.3567\), deci \(F^{-1}(0.37)=\lceil0.4620/0.3567\rceil=\lceil1.295\rceil=2\). Verificare pe funcția de repartiție: \(F(1)=0.3<0.37\le F(2)=1-0.7^2=0.51\), deci într-adevăr \(F^{-1}(0.37)=2\). Formula cu \(U\) în loc de \(1-U\) dă, pentru același \(u\), \(\lceil\ln0.37/\ln0.7\rceil=\lceil2.788\rceil=3\): valorile produse de cele două formule diferă, dar repartiția lor este aceeași, și numai ea contează într-o simulare.

În R, rgeom(n, p) simulează numărul de eșecuri dinaintea primului succes, cu valori în \(\{0,1,2,\dots\}\); pentru convenția noastră (numărul de încercări) folosim rgeom(n, p) + 1.

Repartiția geometrică are o infinitate de valori și totuși funcția ei cuantilă are o formulă explicită. Exemplul următor arată că o astfel de formulă poate fi nu doar comodă, ci indispensabilă.

Exemplul 5 (O repartiție discretă cu funcția cuantilă explicită)

Fie \(X\) cu valori în \(\N^*\) și \(\PP(X=k)=\frac{1}{k(k+1)}\), \(k\ge1\); de exemplu \(p_1=\frac12\), \(p_2=\frac16\), \(p_3=\frac1{12}\).

Funcția de repartiție. Cum \(\frac{1}{j(j+1)}=\frac1j-\frac{1}{j+1}\), suma este telescopică: \[ F(k)=\sum_{j=1}^k\Big(\frac1j-\frac{1}{j+1}\Big)=1-\frac{1}{k+1}=\frac{k}{k+1},\qquad k\ge1 ; \] în particular \(F(k)\to1\) când \(k\to\infty\), deci numerele \(p_k\) formează într-adevăr o repartiție.

Inversarea. Pentru \(u\in(0,1)\), \(F^{-1}(u)\) este cel mai mic întreg \(k\ge1\) cu \(F(k)\ge u\), iar \[ \frac{k}{k+1}\ge u\iff k\ge u(k+1)\iff k(1-u)\ge u\iff k\ge\frac{u}{1-u} , \] deci \(F^{-1}(u)=\big\lceil\frac{u}{1-u}\big\rceil\) (raportul este strict pozitiv, deci rezultatul este cel puțin \(1\)). Dacă raportul este chiar un întreg \(k\), adică \(u=\frac{k}{k+1}=F(k)\), formula întoarce \(k\), nu \(k+1\), în acord cu convenția \(s_{k-1}<u\le s_k\).

Algoritmul și un calcul numeric. Generăm \(U\) și întoarcem \(X=\lceil U/(1-U)\rceil\). Pentru \(u=0.37\): \(\lceil0.37/0.63\rceil=\lceil0.587\rceil=1\), în acord cu \(u\le F(1)=0.5\). Pentru \(u=0.92\): \(\lceil0.92/0.08\rceil=\lceil11.5\rceil=12\), în acord cu \(F(11)=\frac{11}{12}\approx0.9167<0.92\le F(12)=\frac{12}{13}\approx0.9231\).

De ce contează formula explicită. Căutarea secvențială ar face \(X\) comparații, deci în medie \(\sum_{k\ge1}k\,p_k=\sum_{k\ge1}\frac{1}{k+1}=+\infty\) (seria armonică): fiecare căutare se termină, dar costul mediu este infinit, la fel ca media \(\E[X]\). Formula explicită costă o împărțire și o rotunjire, oricare ar fi \(u\).

Când funcția de repartiție nu se inversează explicit, folosim o recurență pentru probabilități.

Exemplul 6 (Repartiția Poisson prin metoda inversă)

Pentru \(X\sim\Pois(\lambda)\), cu \(p_k=e^{-\lambda}\lambda^k/k!\), \(k\in\N\), funcția de repartiție \(F(k)=e^{-\lambda}\sum_{j=0}^k\lambda^j/j!\) nu se inversează explicit. Probabilitățile verifică însă o recurență simplă: împărțind două probabilități consecutive, \[ \frac{p_{k+1}}{p_k}=\frac{e^{-\lambda}\lambda^{k+1}/(k+1)!}{e^{-\lambda}\lambda^k/k!}=\frac{\lambda}{k+1},\qquad\text{deci}\qquad p_0=e^{-\lambda},\quad p_{k+1}=\frac{\lambda}{k+1}\,p_k . \] Recurența evită calculul separat al puterilor \(\lambda^k\) și al factorialelor (care depășesc capacitatea de reprezentare pentru \(k\) mare).

Algoritmul (cu \(F(-1)=0\)): generăm \(U\); pornim cu \(i=0\), \(p=p_0\), \(F=p_0\); cât timp \(U>F\), trecem la \(i+1\), actualizăm \(p\leftarrow p\,\lambda/(i+1)\) și \(F\leftarrow F+p\); la oprire întoarcem \(X=i\). Algoritmul se oprește exact la primul \(i\) cu \(U\le F(i)\), adică la \(i\) cu \(F(i-1)<U\le F(i)\), deci \(X=F^{-1}(U)\sim\Pois(\lambda)\) (Propoziția 2). Numărul de comparații este \(X+1\), deci în medie \(\lambda+1\).

Algoritmul, pas cu pas, pentru \(\lambda=2\). Pornim cu \(p_0=e^{-2}\approx0.1353\); recurența dă \(p_1=\frac21p_0\approx0.2707\), \(p_2=\frac22p_1\approx0.2707\), \(p_3=\frac23p_2\approx0.1804\), \(p_4=\frac24p_3\approx0.0902\), \(p_5=\frac25p_4\approx0.0361\), iar sumele lor succesive sunt valorile \(F(i)\): \[ \begin{array}{l|cccccc} i & 0 & 1 & 2 & 3 & 4 & 5\\ \hline p_i & 0.1353 & 0.2707 & 0.2707 & 0.1804 & 0.0902 & 0.0361\rule{0pt}{2.6ex}\\ F(i) & 0.1353 & 0.4060 & 0.6767 & 0.8571 & 0.9473 & 0.9834 \end{array} \] Pentru \(u=0.37\): la \(i=0\) avem \(u>F(0)=0.1353\), deci continuăm; la \(i=1\) avem \(u\le F(1)=0.4060\) și ne oprim, cu \(X=1\) (două comparații, o singură actualizare a lui \(p\) și a lui \(F\)). Pentru \(u=0.95\): \(u\) depășește pe rând \(F(0),\dots,F(4)\) (ultima fiind \(0.9473\)) și abia \(F(5)=0.9834\ge0.95\), deci \(X=5\), după șase comparații. Valorile mari ale lui \(u\) cer mai multe iterații, dar sunt rare: \(\PP(X\ge5)=1-F(4)\approx0.053\).

Binomiala \(\Bin(m,p)\) se simulează cu același algoritm, în care se schimbă doar valoarea de pornire \(p_0\) și factorul recurenței. Din \(p_k=\binom mk p^k(1-p)^{m-k}\), folosind \(\frac{k!}{(k+1)!}=\frac{1}{k+1}\) și \(\frac{(m-k)!}{(m-k-1)!}=m-k\), \[ \frac{p_{k+1}}{p_k}=\frac{m!\,k!\,(m-k)!}{(k+1)!\,(m-k-1)!\,m!}\cdot\frac{p^{k+1}(1-p)^{m-k-1}}{p^k(1-p)^{m-k}}=\frac{m-k}{k+1}\cdot\frac{p}{1-p}, \] deci \(p_0=(1-p)^m\) și \(p_{k+1}=\frac{m-k}{k+1}\cdot\frac{p}{1-p}\,p_k\), \(k=0,\dots,m-1\). Algoritmul: generăm \(U\); pornim cu \(i=0\), probabilitatea curentă \(q=(1-p)^m\) și \(F=q\); cât timp \(U>F\), actualizăm \(q\leftarrow q\cdot\frac{m-i}{i+1}\cdot\frac{p}{1-p}\), trecem la \(i+1\) și \(F\leftarrow F+q\). Cum \(F(m)=1\ge U\), algoritmul se oprește după cel mult \(m\) pași și întoarce \(X=F^{-1}(U)\sim\Bin(m,p)\), cu \(X+1\) comparații, deci în medie \(1+mp\). De exemplu, pentru \(\Bin(3,\frac12)\) factorul recurenței este \(\frac{3-k}{k+1}\), deci \(p_0=\frac18=0.125\), \(p_1=3p_0=0.375\), \(p_2=\frac22p_1=0.375\) și \(p_3=\frac13p_2=0.125\); pentru \(u=0.37\) avem \(F(0)=0.125<u\le F(1)=0.5\), deci \(X=1\).

3.2 Cazul variabilelor aleatoare continue

Pentru o repartiție continuă cu funcția de repartiție strict crescătoare pe suport, \(F^{-1}\) este inversa obișnuită (Propoziția 9 din Cursul 3), iar metoda inversă se reduce la rezolvarea ecuației \(F(x)=u\).

Exemplul 7 (Repartiția exponențială)

Fie \(X\sim\Exp(\lambda)\), \(\lambda>0\), cu \(f(x)=\lambda e^{-\lambda x}\Ind_{[0,\infty)}(x)\).

Funcția de repartiție. Pentru \(x<0\), \(F(x)=0\), iar pentru \(x\ge0\) \[ F(x)=\int_0^x\lambda e^{-\lambda t}\dd t=\Big[-e^{-\lambda t}\Big]_0^x=1-e^{-\lambda x}. \] Pe \((0,\infty)\), \(F\) este continuă și strict crescătoare (\(F'(x)=\lambda e^{-\lambda x}>0\)), cu \(F(0+)=0\) și \(F(\infty)=1\): o bijecție de la \((0,\infty)\) la \((0,1)\).

Inversarea. Pentru \(u\in(0,1)\), \[ F(x)=u\iff e^{-\lambda x}=1-u\iff -\lambda x=\ln(1-u)\iff x=-\frac{\ln(1-u)}{\lambda}, \] deci \(F^{-1}(u)=-\frac1\lambda\ln(1-u)\). Din Teorema 12 din Cursul 3, \(-\frac1\lambda\ln(1-U)\sim\Exp(\lambda)\), iar cum \(1-U\sim\Unif(0,1)\), obținem regula de simulare \[ X=-\frac1\lambda\ln U\sim\Exp(\lambda). \] Verificare directă: pentru \(x\ge0\), \(\PP(-\frac1\lambda\ln U\le x)=\PP(\ln U\ge-\lambda x)=\PP(U\ge e^{-\lambda x})=1-e^{-\lambda x}\) (am aplicat funcția strict crescătoare \(\exp\)). Reamintim \(\E[X]=\frac1\lambda\), \(\Var(X)=\frac1{\lambda^2}\) și cuantila de ordin \(u\), \(-\frac1\lambda\ln(1-u)\).

Algoritmul și un calcul numeric. (1) Generăm \(U\sim\Unif(0,1)\); (2) întoarcem \(X=-\frac1\lambda\ln U\). Pentru \(\lambda=2\) și \(u=0.37\), funcția cuantilă dă \(F^{-1}(0.37)=-\frac12\ln0.63\approx0.2310\) (într-adevăr, \(F(0.2310)=1-e^{-0.4620}=1-0.63=0.37\)), iar regula cu \(U\) în locul lui \(1-U\) întoarce \(-\frac12\ln0.37\approx0.4971\). Ca la repartiția geometrică, cele două numere diferă, dar ambele reguli produc variabile \(\Exp(2)\): prima este crescătoare în \(u\) (valorile mici ale lui \(u\) dau valori mici ale lui \(X\)), a doua este descrescătoare.

Exemplul 8 (Repartiția Cauchy)

Fie \(X\sim\Cauchy(0,1)\), cu densitatea \(f(x)=\frac{1}{\pi(1+x^2)}\), \(x\in\R\).

Funcția de repartiție. Cum \((\arctan t)'=\frac{1}{1+t^2}\) și \(\lim_{t\to-\infty}\arctan t=-\frac\pi2\), \[ F(x)=\int_{-\infty}^x\frac{\dd t}{\pi(1+t^2)}=\frac1\pi\Big(\arctan x+\frac\pi2\Big)=\frac12+\frac1\pi\arctan x , \] continuă și strict crescătoare de la \(\R\) pe \((0,1)\).

Inversarea. Pentru \(u\in(0,1)\), \(F(x)=u\iff\arctan x=\pi\big(u-\frac12\big)\iff x=\tan\big(\pi(u-\frac12)\big)\), deoarece \(\pi(u-\frac12)\in(-\frac\pi2,\frac\pi2)\), intervalul pe care \(\tan\) este inversa lui \(\arctan\). Deci \(X=\tan\big(\pi(U-\tfrac12)\big)\sim\Cauchy(0,1)\).

Algoritmul și un calcul numeric. (1) Generăm \(U\sim\Unif(0,1)\); (2) întoarcem \(X=\tan\big(\pi(U-\frac12)\big)\). Pentru \(u=0.37\): \(\pi(u-\frac12)=-0.13\pi\approx-0.4084\) și \(x=\tan(-0.4084)\approx-0.433\); valorile \(u<\frac12\) dau \(x<0\), iar \(u=\frac12\) dă mediana \(0\). Pentru \(u=0.99\): \(x=\tan(0.49\pi)\approx31.8\). Așadar, în medie, o observație Cauchy din o sută depășește \(31.8\), pe când cuantila de ordin \(0.99\) a repartiției \(\Norm(0,1)\) este doar \(z_{0.99}\approx2.33\): aceasta înseamnă, concret, „cozi grele”.

Locație și scală. Pentru \(\alpha\in\R\), \(\beta>0\), funcția \(x\mapsto\alpha+\beta x\) este strict crescătoare, deci variabila \(Y=\alpha+\beta X\) are densitatea \(\frac1\beta f\big(\frac{y-\alpha}{\beta}\big)=\frac{1}{\pi\beta}\big[1+\big(\frac{y-\alpha}{\beta}\big)^2\big]^{-1}\) (Teorema 17 din Cursul 1), adică \(Y\sim\Cauchy(\alpha,\beta)\); deci \(\alpha+\beta\tan\big(\pi(U-\tfrac12)\big)\sim\Cauchy(\alpha,\beta)\). Cuantilele sunt \(q_u=\alpha+\beta\tan\big(\pi(u-\frac12)\big)\): mediana este \(q_{0.5}=\alpha\), iar cuartila superioară \(q_{0.75}=\alpha+\beta\tan\frac\pi4=\alpha+\beta\).

Comportamentul mediei empirice. Media repartiției Cauchy nu există (Exemplul 14 din Cursul 1), deci LNM nu se aplică: mediile empirice ale unui eșantion Cauchy nu se stabilizează când volumul crește, deoarece câteva observații foarte mari în modul (cozile grele) domină suma; mai precis, media \(\bar X_n\) a unui eșantion de volum \(n\) din \(\Cauchy(\alpha,\beta)\) are tot repartiția \(\Cauchy(\alpha,\beta)\), pentru orice \(n\) (Casella and Berger 2002, cap. 5). În schimb, mediana empirică se apropie de mediana teoretică \(\alpha\) (Cursul 6).

În ambele exemple am parcurs aceiași patru pași: (1) calculăm \(F\) prin integrarea densității; (2) rezolvăm ecuația \(F(x)=u\); (3) scriem algoritmul; (4) verificăm, direct sau numeric. Îi reluăm pentru două densități cu suportul \((0,1)\), la care vom reveni când vom discuta metoda respingerii.

Exemplul 9 (Două densități pe intervalul unitate)

Fie \(U\sim\Unif(0,1)\).

Densitatea \(f(x)=3x^2\,\Ind_{(0,1)}(x)\). (1) Pentru \(x\in[0,1]\), \(F(x)=\int_0^x3t^2\dd t=x^3\), iar \(F(x)=0\) pentru \(x<0\) și \(F(x)=1\) pentru \(x>1\); \(F\) este continuă și strict crescătoare pe \((0,1)\). (2) Pentru \(u\in(0,1)\), \(F(x)=u\iff x^3=u\iff x=u^{1/3}\), deci \(F^{-1}(u)=u^{1/3}\). (3) Algoritmul: generăm \(U\) și întoarcem \(X=U^{1/3}\); de exemplu, \(u=0.37\) dă \(x=0.37^{1/3}\approx0.718\). (4) Verificare directă: pentru \(x\in[0,1]\), \(\PP(U^{1/3}\le x)=\PP(U\le x^3)=x^3=F(x)\). Mediana este \(F^{-1}(\frac12)=2^{-1/3}\approx0.794\): densitatea crește spre \(1\), deci valorile mari sunt mai probabile decât cele mici.

Repartiția arcsinus. Fie \(f(x)=\frac{1}{\pi\sqrt{x(1-x)}}\), \(0<x<1\), densitatea repartiției \(\BetaD(\frac12,\frac12)\) (constanta de normare este \(B(\frac12,\frac12)=\Gamma(\frac12)^2/\Gamma(1)=\pi\)). (1) Calculăm \(F\) cu schimbarea de variabilă \(t=\sin^2s\), \(s\in[0,\frac\pi2]\): \(\dd t=2\sin s\cos s\dd s\), \(\sqrt{t(1-t)}=\sin s\cos s\), iar limitele \(t=0\), \(t=x\) devin \(s=0\), \(s=\arcsin\sqrt x\), deci \[ F(x)=\int_0^x\frac{\dd t}{\pi\sqrt{t(1-t)}}=\frac1\pi\int_0^{\arcsin\sqrt x}\frac{2\sin s\cos s}{\sin s\cos s}\dd s=\frac2\pi\arcsin\sqrt x,\qquad x\in[0,1]. \] (2) \(F\) este continuă și strict crescătoare pe \((0,1)\), iar pentru \(u\in(0,1)\), cum \(\frac{\pi u}{2}\in(0,\frac\pi2)\) (interval pe care \(\sin\) este inversa lui \(\arcsin\)), \[ F(x)=u\iff\arcsin\sqrt x=\frac{\pi u}{2}\iff\sqrt x=\sin\frac{\pi u}{2}\iff x=\sin^2\frac{\pi u}{2}. \] (3) Algoritmul: generăm \(U\) și întoarcem \(X=\sin^2(\pi U/2)\); pentru \(u=0.37\), \(x=\sin^2(0.5812)\approx0.3014\). (4) Verificare numerică: \(F(0.3014)=\frac2\pi\arcsin\sqrt{0.3014}=\frac2\pi\arcsin(0.5490)\approx\frac2\pi\cdot0.5812=0.37\).

Densitatea arcsinus este nemărginită lângă \(0\) și lângă \(1\), dar aceasta nu creează nicio dificultate metodei inverse, care lucrează cu \(F\), nu cu \(f\). Vom vedea în Exemplul 13 că, pentru metoda respingerii, lucrurile stau altfel.

Aceeași rețetă se aplică tuturor repartițiilor pentru care \(F\) se inversează explicit; câteva exemple sunt adunate în Tabelul 1, iar Figura 2 compară histogramele unor eșantioane simulate cu densitățile teoretice.

Tabelul 1: Metoda inversă pentru câteva repartiții continue uzuale. În ultima coloană am folosit, acolo unde a fost util, faptul că \(1-U\sim\mathcal{U}(0,1)\).
Repartiția Densitatea \(f(x)\) \(F(x)\) Simulare (\(U\sim\Unif(0,1)\))
\(\Exp(\lambda)\) \(\lambda e^{-\lambda x}\), \(x>0\) \(1-e^{-\lambda x}\) \(-\frac1\lambda\ln U\)
Weibull \((k,s)\) \(\frac ks\big(\frac xs\big)^{k-1}e^{-(x/s)^k}\), \(x>0\) \(1-e^{-(x/s)^k}\) \(s\,(-\ln U)^{1/k}\)
Rayleigh \((\theta)\) \(\frac x\theta e^{-x^2/(2\theta)}\), \(x>0\) \(1-e^{-x^2/(2\theta)}\) \(\sqrt{-2\theta\ln U}\)
Pareto \((\alpha,\beta)\) \(\beta\alpha^\beta x^{-\beta-1}\), \(x>\alpha\) \(1-(\alpha/x)^\beta\) \(\alpha\,U^{-1/\beta}\)
\(\Cauchy(\alpha,\beta)\) \(\frac{1}{\pi\beta}\big[1+(\frac{x-\alpha}{\beta})^2\big]^{-1}\) \(\frac12+\frac1\pi\arctan\frac{x-\alpha}{\beta}\) \(\alpha+\beta\tan\big(\pi(U-\frac12)\big)\)
Logistică \((\alpha,\beta)\) \(\frac{e^{-(x-\alpha)/\beta}}{\beta(1+e^{-(x-\alpha)/\beta})^2}\) \(\frac{1}{1+e^{-(x-\alpha)/\beta}}\) \(\alpha+\beta\ln\frac{U}{1-U}\)
Laplace \((\alpha,\beta)\) \(\frac{1}{2\beta}e^{-\lvert x-\alpha\rvert/\beta}\) Exemplul 10 \(\alpha-\beta\sgn(U-\frac12)\ln(1-2\lvert U-\frac12\rvert)\)
\(\Unif(a,b)\) \(\frac{1}{b-a}\), \(a<x<b\) \(\frac{x-a}{b-a}\) \(a+(b-a)U\)
Exemplul 10 (Deducerea formulelor din tabel)

În fiecare caz calculăm \(F\) prin integrarea densității, rezolvăm ecuația \(F(x)=u\) pentru \(u\in(0,1)\) și, unde este util, înlocuim \(1-U\) cu \(U\). În toate cazurile, densitatea este strict pozitivă pe intervalul deschis \(I\) pe care \(0<F<1\), deci \(F\) este continuă și strict crescătoare pe \(I\), iar \(F^{-1}(u)\) este unica soluție din \(I\) a ecuației \(F(x)=u\) (Propoziția 9 din Cursul 3); în afara lui \(I\), \(F\) este \(0\) sau \(1\).

Pareto \((\alpha,\beta)\), \(\alpha,\beta>0\). Pentru \(x>\alpha\), \[ F(x)=\int_\alpha^x\beta\alpha^\beta t^{-\beta-1}\dd t=\beta\alpha^\beta\Big[\frac{t^{-\beta}}{-\beta}\Big]_\alpha^x=\alpha^\beta\big(\alpha^{-\beta}-x^{-\beta}\big)=1-\Big(\frac\alpha x\Big)^\beta, \] (pentru \(x\le\alpha\), \(F(x)=0\)), iar, ridicând la puterea \(-1/\beta\), \(F(x)=u\iff(\alpha/x)^\beta=1-u\iff x/\alpha=(1-u)^{-1/\beta}\iff x=\alpha(1-u)^{-1/\beta}\). Deci \(F^{-1}(u)=\alpha(1-u)^{-1/\beta}\) și, înlocuind \(1-U\) cu \(U\), \(X=\alpha U^{-1/\beta}\).

Weibull \((k,s)\), \(k,s>0\). Cu schimbarea \(v=(t/s)^k\), \(\dd v=\frac ks\big(\frac ts\big)^{k-1}\dd t\) (limitele \(t=0\), \(t=x\) devin \(v=0\), \(v=(x/s)^k\)), pentru \(x>0\), \[ F(x)=\int_0^x\frac ks\Big(\frac ts\Big)^{k-1}e^{-(t/s)^k}\dd t=\int_0^{(x/s)^k}e^{-v}\dd v=\Big[-e^{-v}\Big]_0^{(x/s)^k}=1-e^{-(x/s)^k}, \] iar \(F(x)=u\iff e^{-(x/s)^k}=1-u\iff(x/s)^k=-\ln(1-u)\iff x=s\,(-\ln(1-u))^{1/k}\) (aici \(-\ln(1-u)>0\)). Deci, înlocuind \(1-U\) cu \(U\), \(X=s(-\ln U)^{1/k}=sE^{1/k}\), cu \(E=-\ln U\sim\Exp(1)\). Repartiția Rayleigh \((\theta)\) este cazul \(k=2\), \(s=\sqrt{2\theta}\): densitatea Weibull devine \(\frac{2}{s}\cdot\frac xs\,e^{-x^2/s^2}=\frac{2x}{2\theta}e^{-x^2/(2\theta)}=\frac x\theta e^{-x^2/(2\theta)}\), iar \(X=\sqrt{2\theta}\,(-\ln U)^{1/2}=\sqrt{-2\theta\ln U}\).

Logistică \((\alpha,\beta)\), \(\beta>0\). Aici pornim de la funcția de repartiție din tabel și verificăm că derivata ei este densitatea. Cu \(w=w(x)=e^{-(x-\alpha)/\beta}\), \(w'=-w/\beta\), derivata lui \(F(x)=(1+w)^{-1}\) este \(F'(x)=-\frac{w'}{(1+w)^2}=\frac{w}{\beta(1+w)^2}\), densitatea din tabel; în plus, când \(x\to-\infty\), \(w\to\infty\) și \(F(x)\to0\), iar când \(x\to\infty\), \(w\to0\) și \(F(x)\to1\), deci \(F(x)=\int_{-\infty}^xF'(t)\dd t\) este funcția de repartiție a acestei densități. Inversarea: \(F(x)=u\iff1+w=\frac1u\iff e^{-(x-\alpha)/\beta}=\frac{1-u}{u}\iff-\frac{x-\alpha}{\beta}=\ln\frac{1-u}{u}\iff x=\alpha+\beta\ln\frac{u}{1-u}\) (funcția logit).

Laplace \((\alpha,\beta)\). Pentru \(x\le\alpha\), \(|t-\alpha|=\alpha-t\) pe \((-\infty,x]\) și \[ F(x)=\int_{-\infty}^x\frac{1}{2\beta}e^{(t-\alpha)/\beta}\dd t=\frac12\Big[e^{(t-\alpha)/\beta}\Big]_{-\infty}^x=\frac12e^{(x-\alpha)/\beta}\le\frac12 ; \] pentru \(x>\alpha\), \(F(x)=F(\alpha)+\int_\alpha^x\frac{1}{2\beta}e^{-(t-\alpha)/\beta}\dd t=\frac12+\frac12\big(1-e^{-(x-\alpha)/\beta}\big)=1-\frac12e^{-(x-\alpha)/\beta}>\frac12\). Ecuația \(F(x)=u\) se rezolvă deci pe ramura stângă pentru \(u\le\frac12\) și pe cea dreaptă pentru \(u>\frac12\): \[ F^{-1}(u)=\begin{cases}\alpha+\beta\ln(2u), & 0<u\le\frac12,\\ \alpha-\beta\ln\big(2(1-u)\big), & \frac12<u<1,\end{cases} \] Într-adevăr, pentru \(u\le\frac12\): \(\frac12e^{(x-\alpha)/\beta}=u\iff x=\alpha+\beta\ln(2u)\) (și \(x\le\alpha\), deoarece \(\ln(2u)\le0\)); pentru \(u>\frac12\): \(1-\frac12e^{-(x-\alpha)/\beta}=u\iff e^{-(x-\alpha)/\beta}=2(1-u)\iff x=\alpha-\beta\ln\big(2(1-u)\big)\) (și \(x>\alpha\)). Compact, \(F^{-1}(u)=\alpha-\beta\,\sgn\big(u-\frac12\big)\ln\big(1-2|u-\frac12|\big)\): pentru \(u<\frac12\), \(\sgn(u-\frac12)=-1\) și \(1-2|u-\frac12|=1-2(\frac12-u)=2u\); pentru \(u>\frac12\), \(\sgn(u-\frac12)=1\) și \(1-2|u-\frac12|=1-2(u-\frac12)=2(1-u)\); pentru \(u=\frac12\) ambele formule dau \(\alpha\).

Mediane, medii și varianțe. Pentru Pareto \((2,3)\) mediana este \(F^{-1}(\frac12)=2\cdot\big(\frac12\big)^{-1/3}=2\cdot2^{1/3}\approx2.52\), iar media (finită pentru \(\beta>1\)) este \[ \int_\alpha^\infty x\,\beta\alpha^\beta x^{-\beta-1}\dd x=\beta\alpha^\beta\Big[\frac{x^{1-\beta}}{1-\beta}\Big]_\alpha^\infty=\beta\alpha^\beta\cdot\frac{\alpha^{1-\beta}}{\beta-1}=\frac{\beta\alpha}{\beta-1}=\frac{3\cdot2}{2}=3 . \] Pentru Laplace \((\alpha,\beta)\) mediana este \(F^{-1}(\frac12)=\alpha\). Cu schimbarea \(t=x-\alpha\), \(\E[X-\alpha]=\int_{\R}t\,\frac{1}{2\beta}e^{-|t|/\beta}\dd t=0\) (integrand impar și integrabil), deci media este \(\alpha\), iar, din paritate și cu \(s=t/\beta\), \[ \Var(X)=\int_{\R}t^2\,\frac{1}{2\beta}e^{-|t|/\beta}\dd t=\frac1\beta\int_0^\infty t^2e^{-t/\beta}\dd t=\beta^2\int_0^\infty s^2e^{-s}\dd s=\beta^2\,\Gamma(3)=2\beta^2 . \] Histogramele din Figura 2 confirmă formulele.

Arată codul R
set.seed(8)
n <- 1e4; u <- runif(n)
sims <- list(   # simularea (metoda inversă), densitatea, domeniul afișat
  list(x = -log(u) / 2, f = function(t) dexp(t, 2), lim = c(0, 3),
       t = "Exp(2)"),
  list(x = 3 * (-log(u))^(1 / 2), f = function(t) dweibull(t, 2, 3),
       lim = c(0, 9), t = "Weibull(k = 2, s = 3)"),
  list(x = 2 + 3 * log(u / (1 - u)), f = function(t) dlogis(t, 2, 3),
       lim = c(-15, 19), t = "logistică(2, 3)"),
  list(x = 2 * u^(-1 / 3), f = function(t) 3 * 2^3 / t^4, lim = c(2, 8),
       t = "Pareto(2, 3)"))
pl <- lapply(sims, function(s) {
  xs <- s$x[s$x >= s$lim[1] & s$x <= s$lim[2]]
  tt <- seq(s$lim[1], s$lim[2], length.out = 300)
  ggplot(data.frame(x = xs), aes(x)) +
    geom_histogram(aes(y = after_stat(count) / (n * after_stat(width))),
                   bins = 45, boundary = s$lim[1], fill = culori[["albastru"]],
                   alpha = 0.45, colour = "white", linewidth = 0.1) +
    geom_line(data = data.frame(x = tt, y = s$f(tt)), aes(x, y),
              colour = culori[["rosu"]]) +
    labs(title = s$t, x = NULL, y = "densitate")
})
(pl[[1]] + pl[[2]]) / (pl[[3]] + pl[[4]])
Figura 2: Histogramele a câte \(10^4\) observații simulate prin metoda inversă și densitățile teoretice: \(\mathrm{Exp}(2)\), Weibull cu \(k=2\), \(s=3\), logistică \((2,3)\) și Pareto \((2,3)\) (restrânsă la \([2,8]\)).

Metoda inversă nu cere ca repartiția să fie „pur” discretă sau „pur” continuă: Teorema 12 din Cursul 3 este valabilă pentru orice funcție de repartiție. De exemplu, dacă timpul de așteptare la un ghișeu este \(0\) cu probabilitatea \(0.3\) și, în rest, \(\Exp(1)\), atunci, din formula probabilității totale, \(F(x)=0.3+0.7(1-e^{-x})=1-0.7e^{-x}\) pentru \(x\ge0\) și \(F(x)=0\) pentru \(x<0\) (un salt de \(0.3\) în \(0\)). Calculăm \(F^{-1}(u)=\inf\{x:F(x)\ge u\}\). Dacă \(u\le0.3\), atunci \(F(0)=0.3\ge u\), iar \(F(x)=0<u\) pentru \(x<0\), deci \(F^{-1}(u)=0\). Dacă \(u>0.3\), atunci \(F(x)<u\) pentru orice \(x\le0\), iar pentru \(x>0\) \[ 1-0.7e^{-x}\ge u\iff e^{-x}\le\frac{1-u}{0.7}\iff x\ge\ln\frac{0.7}{1-u}\quad(>0,\ \text{deoarece }1-u<0.7), \] deci \(F^{-1}(u)=\ln\frac{0.7}{1-u}\); în R, ifelse(u <= 0.3, 0, log(0.7 / (1 - u))).

Observație

Pentru repartiția normală, \(\Phi^{-1}\) nu are o expresie elementară, dar se calculează numeric cu precizie foarte mare (prin aproximări raționale; algoritmul lui Wichura, 1988, implementat în qnorm). Metoda inversă rămâne deci aplicabilă: \(\Phi^{-1}(U)\sim\Norm(0,1)\); de altfel, generatorul implicit al funcției rnorm din R este chiar metoda inversă (normal.kind = "Inversion" în RNGkind()). Vom vedea și metode exacte fără \(\Phi^{-1}\): prin respingere (Exemplul 15) și prin transformări (Box–Muller, Secțiunea 5.2).

4 Metoda respingerii

Metoda inversă cere cunoașterea funcției cuantilă, rareori disponibilă explicit (normala, Gamma, Beta, repartițiile multidimensionale). Metoda respingerii (acceptare–respingere) ocolește această dificultate: generăm observații dintr-o repartiție „ușoară” și le păstrăm doar pe cele care îndeplinesc o anumită condiție. Tratăm întâi repartiția uniformă pe o mulțime și rezultatul general despre primul punct al unui șir care cade într-o mulțime dată, apoi cazul repartițiilor cu densitate.

4.1 Repartiția uniformă pe o mulțime. Repartiții condiționate

În cele ce urmează, \(\B(\R^d)\) este \(\sigma\)-algebra boreliană a lui \(\R^d\), iar \(\lambda_d\) măsura Lebesgue (lungime, arie, volum).

Definiția 3 (Repartiția uniformă pe o mulțime)

Fie \(B\in\B(\R^d)\) cu \(0<\lambda_d(B)<\infty\). Vectorul aleator \(M\) cu valori în \(\R^d\) este repartizat uniform pe \(B\), și notăm \(M\sim\Unif(B)\), dacă \[ \PP(M\in A)=\frac{\lambda_d(A\cap B)}{\lambda_d(B)},\qquad\forall A\in\B(\R^d). \]

Echivalent, \(M\sim\Unif(B)\) dacă și numai dacă \(M\) are densitatea \(f_M=\frac{1}{\lambda_d(B)}\Ind_B\): pentru orice \(A\in\B(\R^d)\), \[ \int_Af_M(x)\dd x=\frac{1}{\lambda_d(B)}\int_{\R^d}\Ind_A(x)\Ind_B(x)\dd x=\frac{1}{\lambda_d(B)}\int_{\R^d}\Ind_{A\cap B}(x)\dd x=\frac{\lambda_d(A\cap B)}{\lambda_d(B)} , \] iar o repartiție este determinată de valorile ei pe \(\B(\R^d)\). Intuitiv, probabilitatea ca \(M\) să cadă într-o regiune este proporțională cu volumul părții acelei regiuni conținute în \(B\). Pentru \(d=1\) și \(B=[a,b]\) regăsim repartiția \(\Unif(a,b)\).

Propoziția 4 (Uniforma pe un dreptunghi)

Fie \(C=[a_1,b_1]\times\cdots\times[a_d,b_d]\), cu \(a_k<b_k\), și \(U_1,\dots,U_d\) variabile independente \(\Unif(0,1)\). Atunci vectorul \(M=(V_1,\dots,V_d)\), cu \(V_k=a_k+(b_k-a_k)U_k\), este repartizat uniform pe \(C\).

Demonstrație. Ideea demonstrației. Fiecare coordonată \(V_k\) este uniformă pe \([a_k,b_k]\), coordonatele sunt independente, iar produsul densităților marginale este constant pe \(C\) și nul în rest — adică densitatea repartiției uniforme pe \(C\).

Marginalele. Pentru \(t\in[a_k,b_k]\), \[ \PP(V_k\le t)=\PP\Big(U_k\le\frac{t-a_k}{b_k-a_k}\Big)=\frac{t-a_k}{b_k-a_k}, \] deoarece \(\frac{t-a_k}{b_k-a_k}\in[0,1]\); pentru \(t<a_k\) probabilitatea este \(0\), iar pentru \(t>b_k\) este \(1\). Deci \(V_k\sim\Unif(a_k,b_k)\), cu densitatea \(\frac{1}{b_k-a_k}\Ind_{[a_k,b_k]}\) (metoda inversă din Tabelul 1).

Independența. Fiecare \(V_k\) este o funcție (afină) doar de \(U_k\), iar \(U_1,\dots,U_d\) sunt independente, deci \(V_1,\dots,V_d\) sunt independente (Propoziția 39 din Cursul 1).

Densitatea comună. Din criteriul de factorizare (Propoziția 38 din Cursul 1), vectorul are densitatea \[ f_M(x_1,\dots,x_d)=\prod_{k=1}^d\frac{\Ind_{[a_k,b_k]}(x_k)}{b_k-a_k}=\frac{\Ind_{C}(x_1,\dots,x_d)}{\prod_{k=1}^d(b_k-a_k)}=\frac{1}{\lambda_d(C)}\Ind_C(x_1,\dots,x_d), \] deoarece produsul indicatorilor este indicatorul produsului cartezian, iar volumul dreptunghiului este produsul lungimilor laturilor. Deci \(M\sim\Unif(C)\).■

Cum simulăm însă un punct uniform pe o mulțime \(B\) oarecare (disc, bilă, triunghi)? Dacă \(B\subseteq C\), cu \(C\) un dreptunghi, generăm puncte uniforme în \(C\) până când unul dintre ele cade în \(B\) (Figura 3).

Figura 3: Simularea repartiției uniforme pe o mulțime \(B\) inclusă în dreptunghiul \(C\): punctele \(M_1,M_2,\dots\) sunt generate uniform în \(C\); cele care cad în afara lui \(B\) sunt respinse (aici \(M_1,\dots,M_4\)), iar primul punct care cade în \(B\) este păstrat (aici \(T=5\) și \(M_T=M_5\)).

În desen, primele patru puncte au căzut în \(C\setminus B\) și au fost respinse, iar al cincilea a căzut în \(B\) și a fost păstrat: numărul de încercări, \(T=5\), este aleator, iar punctul păstrat este \(M_T\), punctul cu indicele aleator \(T\). Trebuie lămurite două lucruri: cum este repartizat \(T\) (cât costă metoda) și de ce \(M_T\) este repartizat uniform pe \(B\) — nu este evident că alegerea unui punct „după ce am văzut unde a căzut” păstrează uniformitatea. Răspunsul este dat de rezultatul următor, formulat pentru o repartiție oarecare \(\mu\) a punctelor \(M_n\) (nu neapărat uniformă pe un dreptunghi): \(T\) este momentul primului succes într-un șir de încercări independente, deci este repartizat geometric, iar \(M_T\) are repartiția unui punct \(M_1\) condiționat de faptul că a căzut în \(B\).

Teorema 5 (Simularea repartiției condiționate prin respingere)

Fie \((M_n)_{n\ge1}\) vectori aleatori în \(\R^d\), independenți și cu aceeași repartiție \(\mu\), și \(B\in\B(\R^d)\) cu \(\mu(B)>0\). Definim \[ T=\inf\{n\ge1:\ M_n\in B\}\quad(\inf\emptyset=+\infty),\qquad M_T(\omega)=\begin{cases}M_{T(\omega)}(\omega), & T(\omega)<\infty,\\ 0, & T(\omega)=\infty.\end{cases} \] Atunci:

  1. \(\PP(T<\infty)=1\), iar \(T\sim\Geom(\mu(B))\): \(\PP(T=k)=(1-\mu(B))^{k-1}\mu(B)\), \(k\ge1\); în particular \(\E[T]=1/\mu(B)\);
  2. \(M_T\) este un vector aleator cu repartiția \[ \nu(A)=\PP(M_T\in A)=\frac{\mu(A\cap B)}{\mu(B)}=\mu(A\mid B),\qquad A\in\B(\R^d), \] adică repartiția lui \(M_1\) condiționată de evenimentul \(\{M_1\in B\}\); notăm \(\nu=\mathcal{L}(M_1\mid M_1\in B)\).

Demonstrație. Ideea demonstrației. Indicele aleator \(T\) este momentul primului „succes” într-un șir de probe Bernoulli independente \(\Ind_{\{M_n\in B\}}\), cu probabilitatea de succes \(p=\mu(B)\in(0,1]\). Pentru repartiția lui \(M_T\) descompunem după valorile lui \(T\): pe \(\{T=k\}\), \(M_T=M_k\), iar independența separă „trecutul” \(\{M_1\notin B,\dots,M_{k-1}\notin B\}\) de „prezent”.

Pasul 1: măsurabilitatea lui \(T\). \(T\) ia valori în mulțimea numărabilă \(\N^*\cup\{+\infty\}\), deci este suficient ca \(\{T=k\}\in\F\) pentru orice \(k\). Pentru \(k\in\N^*\), \[ \{T=k\}=\{M_1\notin B,\dots,M_{k-1}\notin B,\ M_k\in B\}=\bigcap_{i<k}M_i^{-1}(B^c)\cap M_k^{-1}(B)\in\F, \] iar \(\{T=\infty\}=\bigcap_{n\ge1}M_n^{-1}(B^c)\in\F\), ca intersecție numărabilă de evenimente.

Pasul 2: repartiția lui \(T\). Evenimentele \(\{M_1\notin B\},\dots,\{M_{k-1}\notin B\},\{M_k\in B\}\) sunt independente (sunt determinate de vectori independenți) și \(\PP(M_i\in B)=\mu(B)=p\) pentru orice \(i\), deci \[ \PP(T=k)=\prod_{i=1}^{k-1}\PP(M_i\notin B)\cdot\PP(M_k\in B)=(1-p)^{k-1}p,\qquad k\in\N^* . \] Pentru orice \(m\ge1\), \(\{T=\infty\}\subseteq\bigcap_{i=1}^m\{M_i\notin B\}\), deci \(\PP(T=\infty)\le(1-p)^m\xrightarrow[m\to\infty]{}0\); aici folosim ipoteza \(\mu(B)>0\), care asigură \(1-p<1\). Așadar \(T<\infty\) a.s. și \(T\sim\Geom(p)\), cu media \[ \E[T]=\sum_{k\ge1}k(1-p)^{k-1}p=p\cdot\frac{1}{\big(1-(1-p)\big)^2}=\frac1p , \] unde am folosit \(\sum_{k\ge1}kq^{k-1}=\frac{1}{(1-q)^2}\) pentru \(q\in[0,1)\). Această formulă se obține scriind \(k=\sum_{j=1}^k1\) și schimbând ordinea de sumare (serie dublă cu termeni nenegativi), apoi însumând de două ori seria geometrică: \[ \sum_{k\ge1}kq^{k-1}=\sum_{k\ge1}\sum_{j=1}^kq^{k-1}=\sum_{j\ge1}\sum_{k\ge j}q^{k-1}=\sum_{j\ge1}\frac{q^{j-1}}{1-q}=\frac{1}{(1-q)^2} . \]

Pasul 3: măsurabilitatea lui \(M_T\). Fie \(A\in\B(\R^d)\). Evenimentele \(\{T=k\}\), \(k\in\N^*\cup\{\infty\}\), formează o partiție a lui \(\Omega\), iar pe \(\{T=k\}\), \(k<\infty\), avem \(M_T=M_k\), deci \[ \{M_T\in A\}\cap\{T=k\}=\{M_1\notin B,\dots,M_{k-1}\notin B,\ M_k\in A\cap B\}=\bigcap_{i<k}M_i^{-1}(B^c)\cap M_k^{-1}(A\cap B)\in\F ; \] pe \(\{T=\infty\}\), \(M_T=0\), iar \(\{M_T\in A\}\cap\{T=\infty\}\) este \(\{T=\infty\}\) sau \(\emptyset\), după cum \(0\in A\) sau nu. Deci \(\{M_T\in A\}\) este o reuniune numărabilă de evenimente, iar \(M_T\) este vector aleator.

Pasul 4: repartiția lui \(M_T\). Cum \(\PP(T=\infty)=0\), din aditivitatea numărabilă, Pasul 3 și independență, \[ \begin{aligned} \nu(A)=\PP(M_T\in A)&=\sum_{k\ge1}\PP\big(M_T\in A,\,T=k\big)=\sum_{k\ge1}\PP\big(M_1\notin B,\dots,M_{k-1}\notin B,\ M_k\in A\cap B\big)\\ &=\sum_{k\ge1}(1-p)^{k-1}\,\mu(A\cap B)=\mu(A\cap B)\cdot\frac{1}{1-(1-p)}=\frac{\mu(A\cap B)}{\mu(B)} , \end{aligned} \] unde, la trecerea la al doilea rând, am folosit independența vectorilor \(M_1,\dots,M_k\) (\(\PP(M_i\notin B)=1-p\) pentru \(i<k\) și \(\PP(M_k\in A\cap B)=\mu(A\cap B)\)), iar apoi am însumat seria geometrică de rație \(1-p\in[0,1)\) și am folosit \(p=\mu(B)\). Am obținut \(\nu(A)=\mu(A\cap B)/\mu(B)=\mu(A\mid B)\) pentru orice \(A\in\B(\R^d)\), adică afirmația 2.■

Observație

Calculul de la Pasul 4 arată mai mult: pentru orice \(k\ge1\) și \(A\in\B(\R^d)\), \[ \PP(M_T\in A,\ T=k)=(1-p)^{k-1}\mu(A\cap B)=\underbrace{(1-p)^{k-1}p}_{\PP(T=k)}\cdot\underbrace{\frac{\mu(A\cap B)}{\mu(B)}}_{\nu(A)} , \] deci \(M_T\) și \(T\) sunt independente (Delmas 2010, Ex. VII.4): valoarea acceptată nu depinde de numărul de încercări necesare pentru a o obține. Consecință practică: repetând procedura (fiecare nouă observație folosește vectori \(M_n\) încă neexaminați) obținem variabile independente cu repartiția \(\nu\), adică un eșantion din \(\nu\). Costul mediu pentru o observație acceptată este \(1/\mu(B)\): metoda devine lentă când \(\mu(B)\) este mic.

Demonstrația independenței observațiilor succesive. Fie \(T_0=0\), \(T_j=\inf\{n>T_{j-1}:\ M_n\in B\}\) momentul celei de-a \(j\)-a acceptări și \(Z_j=M_{T_j}\) a \(j\)-a valoare acceptată, \(j\ge1\). Fixăm \(m\ge1\), indicii \(1\le k_1<k_2<\dots<k_m\) și \(A_1,\dots,A_m\in\B(\R^d)\). Evenimentul \(\{T_1=k_1,\dots,T_m=k_m,\ Z_1\in A_1,\dots,Z_m\in A_m\}\) înseamnă că \(M_{k_j}\in A_j\cap B\) pentru \(j=1,\dots,m\) și că \(M_n\notin B\) pentru ceilalți \(k_m-m\) indici \(n\le k_m\). Vectorii \(M_1,\dots,M_{k_m}\) fiind independenți, cu repartiția \(\mu\), \[ \PP\big(T_1=k_1,\dots,T_m=k_m,\ Z_1\in A_1,\dots,Z_m\in A_m\big)=(1-p)^{k_m-m}\prod_{j=1}^m\mu(A_j\cap B). \] Notăm \(d_j=k_j-k_{j-1}\ge1\) (cu \(k_0=0\)) numărul de încercări dintre două acceptări consecutive; atunci \(k_m-m=\sum_{j=1}^m(d_j-1)\), iar alegerea indicilor \(k_1<\dots<k_m\) revine la alegerea întregilor \(d_1,\dots,d_m\ge1\). Însumând după toate aceste valori (serie multiplă cu termeni nenegativi, care se scrie ca produs de serii geometrice), \[ \PP\big(Z_1\in A_1,\dots,Z_m\in A_m\big)=\prod_{j=1}^m\Big(\mu(A_j\cap B)\sum_{d_j\ge1}(1-p)^{d_j-1}\Big)=\prod_{j=1}^m\frac{\mu(A_j\cap B)}{p}=\prod_{j=1}^m\nu(A_j). \] Pentru \(A_1=\dots=A_m=\R^d\) suma este \(1\), deci \(T_1,\dots,T_m\) sunt finiți a.s.; luând \(A_i=\R^d\) pentru \(i\ne j\) obținem \(\PP(Z_j\in A_j)=\nu(A_j)\). Prin urmare \(\PP(Z_1\in A_1,\dots,Z_m\in A_m)=\prod_j\PP(Z_j\in A_j)\) pentru orice boreliene \(A_1,\dots,A_m\): vectorii \(Z_1,\dots,Z_m\) sunt independenți (Definiția 37 din Cursul 1) și au toți repartiția \(\nu\).

Exemplul 11 (Zarul aruncat până la primul rezultat mai mare decât patru)

Verificăm teorema pe cel mai simplu caz. Aruncăm în mod repetat un zar echilibrat: \(M_1,M_2,\dots\) sunt independente, cu repartiția \(\mu\) uniformă pe \(\{1,\dots,6\}\) (aici \(d=1\)), și luăm \(B=\{5,6\}\), cu \(\mu(B)=\frac26=\frac13\). Dacă, de exemplu, aruncările sunt \(3,1,4,6,2,\dots\), atunci \(T=4\) și \(M_T=6\).

Numărul de aruncări. Din punctul 1 al Teoremei 5, \(T\sim\Geom(\frac13)\): \(\PP(T=k)=\big(\frac23\big)^{k-1}\frac13\), cu \(\E[T]=3\) aruncări în medie.

Valoarea păstrată. Din punctul 2, \(\nu(\{5\})=\frac{\mu(\{5\}\cap B)}{\mu(B)}=\frac{1/6}{1/3}=\frac12\), la fel \(\nu(\{6\})=\frac12\), iar \(\nu(\{j\})=0\) pentru \(j\le4\): \(M_T\) este uniformă pe \(\{5,6\}\), adică are repartiția unei aruncări despre care știm că a dat un rezultat mai mare decât \(4\). Verificare directă, cu seria de la Pasul 4: \[ \PP(M_T=5)=\sum_{k\ge1}\PP\big(M_1\le4,\dots,M_{k-1}\le4,\ M_k=5\big)=\sum_{k\ge1}\Big(\frac23\Big)^{k-1}\frac16=\frac16\cdot\frac{1}{1-\frac23}=\frac12 . \]

Ce reținem. Respingerea nu deformează repartiția în interiorul lui \(B\): probabilitățile relative ale valorilor din \(B\) rămân cele inițiale și se schimbă doar normarea (împărțirea la \(\mu(B)\)). Pentru un zar măsluit, cu \(\mu(\{5\})=0.1\) și \(\mu(\{6\})=0.3\), am obține \(M_T=5\) cu probabilitatea \(\frac{0.1}{0.4}=0.25\) și \(M_T=6\) cu probabilitatea \(0.75\), iar \(T\sim\Geom(0.4)\).

Corolarul 6 (Uniforma pe o mulțime prin respingere)

Fie \(B\subseteq C\), cu \(C\) un dreptunghi și \(\lambda_d(B)>0\). Dacă \(M_1,M_2,\dots\) sunt independenți, repartizați uniform pe \(C\), atunci primul \(M_n\) care cade în \(B\) este repartizat uniform pe \(B\), iar numărul de încercări necesare este \(\Geom\big(\lambda_d(B)/\lambda_d(C)\big)\), cu media \(\lambda_d(C)/\lambda_d(B)\).

Demonstrație. Aplicăm Teorema 5 cu \(\mu=\Unif(C)\), adică \(\mu(A)=\lambda_d(A\cap C)/\lambda_d(C)\). Cum \(B\subseteq C\), \(\mu(B)=\lambda_d(B)/\lambda_d(C)>0\) și, pentru orice \(A\in\B(\R^d)\), folosind \(A\cap B\cap C=A\cap B\), \[ \nu(A)=\frac{\mu(A\cap B)}{\mu(B)}=\frac{\lambda_d(A\cap B)/\lambda_d(C)}{\lambda_d(B)/\lambda_d(C)}=\frac{\lambda_d(A\cap B)}{\lambda_d(B)} , \] adică \(\nu=\Unif(B)\) (Definiția 3). Numărul de încercări este \(T\sim\Geom(\mu(B))\), cu media \(1/\mu(B)=\lambda_d(C)/\lambda_d(B)\).■

Exemplul 12 (Uniforma pe disc)

Fie \(C=[-1,1]^2\) și \(D=\{(x,y):x^2+y^2\le1\}\) discul unitate.

Algoritmul prin respingere. Generăm \((V_1,V_2)=(2U_1-1,2U_2-1)\), uniform pe \(C\) (Propoziția 4), până când \(V_1^2+V_2^2\le1\). Conform Corolarului 6, punctul acceptat este uniform pe \(D\). Cum \(\lambda_2(D)=\pi\) și \(\lambda_2(C)=4\), probabilitatea de acceptare este \(\pi/4\approx0.785\), iar numărul de încercări este \(\Geom(\pi/4)\), cu media \(4/\pi\approx1.273\). Totodată, proporția de puncte acceptate este un estimator Monte Carlo consistent al lui \(\pi/4\) (estimatorul \(\hat\pi_1/4\) din Exemplul 2, pe întreg discul).

Un calcul numeric. Dacă generatorul produce \((u_1,u_2)=(0.91,\,0.83)\), punctul propus este \((v_1,v_2)=(2\cdot0.91-1,\ 2\cdot0.83-1)=(0.82,\,0.66)\), cu \(v_1^2+v_2^2=0.6724+0.4356=1.108>1\): punctul se află într-un colț al pătratului, în afara discului, și este respins. Perechea următoare, \((u_1,u_2)=(0.37,\,0.58)\), dă \((v_1,v_2)=(-0.26,\,0.16)\), cu \(v_1^2+v_2^2=0.0676+0.0256=0.0932\le1\): punctul este acceptat, deci \(T=2\) și \(M_T=(-0.26,\,0.16)\).

Citirea probabilității de acceptare. Numărul \(\pi/4\approx0.785\) este fracțiunea din aria pătratului ocupată de disc: din \(1500\) de puncte propuse ne așteptăm la aproximativ \(1500\cdot0.785\approx1178\) de puncte acceptate (în simularea din Figura 4 au fost acceptate \(77.0\%\), adică \(1155\)). Fiecare încercare consumă două uniforme, deci un punct al discului costă în medie \(2\cdot\frac4\pi\approx2.55\) uniforme. În dimensiune \(3\), același algoritm (bila unitate, de volum \(\frac{4\pi}{3}\), în cubul \([-1,1]^3\), de volum \(8\)) are probabilitatea de acceptare \(\frac{4\pi/3}{8}=\frac\pi6\approx0.524\); ea scade rapid când dimensiunea crește, deoarece colțurile cubului ocupă tot mai mult din volum.

O idee greșită. Am putea fi tentați să generăm coordonatele polare \(R\sim\Unif(0,1)\) și \(\Theta\sim\Unif(0,2\pi)\) independente și să luăm \((R\cos\Theta,R\sin\Theta)\). Punctele obținute se aglomerează însă spre centru (Figura 4): pentru \(r\in[0,1]\), un punct \((X,Y)\) uniform pe \(D\) cade în discul de rază \(r\) cu probabilitatea \[ \PP\big(X^2+Y^2\le r^2\big)=\frac{\lambda_2(\{x^2+y^2\le r^2\})}{\lambda_2(D)}=\frac{\pi r^2}{\pi}=r^2 , \] nu \(r\); de exemplu, discul de rază \(\frac12\) trebuie să primească doar un sfert din puncte, nu jumătate. Distanța la origine a unui punct uniform pe \(D\) are deci funcția de repartiție \(r^2\) pe \([0,1]\) și, prin metoda inversă, se simulează ca \(\sqrt{U}\), nu ca \(U\).

Arată codul R
set.seed(10)
n <- 1500
v <- matrix(runif(2 * n, -1, 1), ncol = 2)          # uniforme în pătrat
acc <- rowSums(v^2) <= 1                            # punctele acceptate
cerc <- data.frame(x = cos(seq(0, 2 * pi, length.out = 200)),
                   y = sin(seq(0, 2 * pi, length.out = 200)))
t1 <- 2 * pi * runif(n); r1 <- runif(n)             # unghi și rază uniforme
et <- sprintf("respingere: %.1f%% acceptate", 100 * mean(acc))
d <- rbind(data.frame(x = v[, 1], y = v[, 2], acc = acc, g = et),
           data.frame(x = r1 * cos(t1), y = r1 * sin(t1), acc = TRUE,
                      g = "polar greșit"))
d$g <- factor(d$g, levels = c(et, "polar greșit"))
ggplot(d, aes(x, y)) +
  geom_point(aes(colour = acc), size = 0.35, show.legend = FALSE) +
  geom_path(data = cerc, colour = culori[["bleumarin"]], linewidth = 0.6) +
  scale_colour_manual(values = c(`FALSE` = "grey70",
                                 `TRUE` = culori[["rosu"]])) +
  facet_wrap(~g) + coord_equal() + labs(x = NULL, y = NULL)
Figura 4: Stânga: metoda respingerii pentru uniforma pe discul unitate (punctele uniforme în pătrat: respinse cu gri, acceptate cu roșu). Dreapta: metoda greșită \(R\sim\mathcal{U}(0,1)\), \(\Theta\sim\mathcal{U}(0,2\pi)\), cu punctele aglomerate spre centru. Câte 1500 de puncte generate.

4.2 Metoda respingerii pentru repartiții cu densitate

Vrem să simulăm o variabilă (sau un vector) \(Z\) cu densitatea \(f\) pe \(\R^d\), numită densitatea țintă. Presupunem că știm să simulăm din densitatea \(g\), numită propunere, și că există o constantă \(c>0\) astfel încât \[ f(x)\le c\,g(x),\qquad\forall x\in\R^d . \tag{5}\] Ideea este geometrică. Notăm cu \[ G=\{(x,y)\in\R^d\times\R:\ 0\le y\le f(x)\},\qquad H=\{(x,y)\in\R^d\times\R:\ 0\le y\le c\,g(x)\} \] subgraficele lui \(f\) și \(cg\); din (5), \(G\subseteq H\). Vom arăta că: (i) abscisa unui punct uniform sub graficul lui \(f\) are densitatea \(f\); (ii) punctul \((X,cg(X)U)\), cu \(X\sim g\) și \(U\sim\Unif(0,1)\) independente, este uniform sub graficul lui \(cg\). Combinând cu Teorema 5: generăm puncte uniforme în \(H\) până când unul cade în \(G\); acesta este uniform în \(G\), iar abscisa lui are densitatea \(f\) (Figura 5; o ilustrare cu puncte simulate este Figura 8).

Cum citim desenul. În Figura 5, regiunea \(H\) este tot ce se află sub curba \(cg\), iar \(G\) (verde) este partea ei de sub curba \(f\). O propunere înseamnă două numere: abscisa \(X\), generată cu densitatea \(g\), și o înălțime \(cg(X)U\), aleasă uniform între \(0\) și \(cg(X)\) pe verticala lui \(X\). Punctul \(M_1\) a nimerit deasupra graficului lui \(f\), adică \(cg(X_1)U_1>f(X_1)\), și este respins; punctul \(M_2\) a nimerit sub grafic, adică \(cg(X_2)U_2\le f(X_2)\), și este acceptat: valoarea simulată este abscisa lui, \(Z=X_2\). Acolo unde cele două curbe sunt apropiate, aproape toate propunerile sunt acceptate; acolo unde \(cg\) este mult deasupra lui \(f\), cele mai multe sunt respinse. În acest fel abscisele acceptate ajung să fie repartizate după \(f\), deși au fost generate după \(g\). Fracțiunea de propuneri acceptate este raportul celor două arii, \(\lambda_2(G)/\lambda_2(H)\), pe care îl calculăm mai jos.

Figura 5: Metoda respingerii: densitatea țintă \(f\) se află sub graficul lui \(cg\), deci subgraficul \(G\) al lui \(f\) (verde) este inclus în subgraficul \(H\) al lui \(cg\) (zona verde împreună cu zona roșie, \(H\setminus G\)). Punctul \(M_1=(X_1,\,cg(X_1)U_1)\), situat deasupra graficului lui \(f\), este respins; punctul \(M_2=(X_2,\,cg(X_2)U_2)\), situat sub graficul lui \(f\), este acceptat, iar algoritmul întoarce abscisa lui, \(X_2\).

Mulțimile \(G\) și \(H\) sunt boreliene, fiind definite prin inegalități între funcții boreliene de \((x,y)\): de exemplu \(G=\{(x,y):\ y\ge0\}\cap\{(x,y):\ f(x)-y\ge0\}\). Din teorema lui Fubini, volumul unei mulțimi \(E\in\B(\R^{d+1})\) este integrala lungimilor secțiunilor ei verticale: \(\lambda_{d+1}(E)=\int_{\R^d}\lambda_1(E_x)\dd x\), cu \(E_x=\{y:(x,y)\in E\}\). (Este teorema lui Fubini–Tonelli pentru funcția nenegativă \(\Ind_E\), adică însăși construcția măsurii produs; ca peste tot în acest curs, o admitem din teoria măsurii (Billingsley 1995, sec. 18).) Cum \(G_x=[0,f(x)]\) și \(H_x=[0,cg(x)]\), de lungimi \(f(x)\), respectiv \(cg(x)\), \[ \lambda_{d+1}(G)=\int_{\R^d}f(x)\dd x=1,\qquad \lambda_{d+1}(H)=c\int_{\R^d}g(x)\dd x=c . \] În particular, \(f\le cg\) implică \(1=\lambda_{d+1}(G)\le\lambda_{d+1}(H)=c\), deci în mod necesar \(c\ge1\).

Proprietatea (i) este o reformulare geometrică a definiției densității (Figura 6). Pentru \(d=1\): probabilitatea ca abscisa \(Z\) a unui punct uniform din \(G\) să cadă în \([a,b]\) este aria porțiunii \(G_{a,b}\) a subgraficului de deasupra lui \([a,b]\) (aria totală a lui \(G\) fiind \(1\)), adică \(\int_a^bf(x)\dd x\).

Figura 6: Subgraficul \(G\) al densității \(f\) și porțiunea \(G_{a,b}=G\cap([a,b]\times\mathbb{R})\) de deasupra intervalului \([a,b]\). Dacă \((Z,Y)\) este repartizat uniform pe \(G\), atunci \(\mathbb{P}(Z\in[a,b])\) este aria lui \(G_{a,b}\), adică \(\int_a^bf(x)\,\mathrm{d}x\).
Propoziția 7 (Uniforma sub graficul unei densități)

Fie \(f\) o densitate de probabilitate pe \(\R^d\), \(G\) subgraficul ei și \(M=(Z,Y)\sim\Unif(G)\). Atunci \(Z\) are densitatea \(f\).

Demonstrație. Ideea demonstrației. Probabilitatea ca abscisa \(Z\) să cadă în \(A\) este volumul porțiunii de subgrafic situate deasupra lui \(A\); calculat prin secțiuni verticale (de lungime \(f(x)\)), acest volum este \(\int_Af\).

Fie \(A\in\B(\R^d)\) și \(G_A=G\cap(A\times\R)=\{(x,y):x\in A,\ 0\le y\le f(x)\}\) porțiunea de subgrafic situată deasupra lui \(A\). Evenimentul \(\{Z\in A\}\) coincide cu \(\{M\in A\times\R\}\), iar din definiția repartiției uniforme (Definiția 3, cu \(B=G\)) și din \(\lambda_{d+1}(G)=1\), \[ \PP(Z\in A)=\frac{\lambda_{d+1}\big((A\times\R)\cap G\big)}{\lambda_{d+1}(G)}=\lambda_{d+1}(G_A). \] Secțiunea verticală a lui \(G_A\) prin \(x\) este \([0,f(x)]\) dacă \(x\in A\) și \(\emptyset\) altfel, deci are lungimea \(f(x)\Ind_A(x)\), iar din teorema lui Fubini \[ \PP(Z\in A)=\int_{\R^d}f(x)\Ind_A(x)\dd x=\int_Af(x)\dd x ,\qquad\forall A\in\B(\R^d), \] adică \(Z\) are densitatea \(f\). (Pentru \(d=1\) și \(A=[a,b]\): probabilitatea este aria de sub graficul lui \(f\) între \(a\) și \(b\), adică aria porțiunii \(G_{a,b}\) din Figura 6.)■

Proprietatea (ii) spune cum construim un punct uniform sub graficul lui \(cg\) din două variabile pe care știm să le simulăm (Figura 7): alegem întâi abscisa \(X\), cu densitatea \(g\); apoi, pe segmentul vertical de deasupra lui \(X\), de lungime \(cg(X)\), alegem ordonata uniform, \(Y=cg(X)U\). Abscisele în care \(g\) este mare sunt alese mai des, dar deasupra lor segmentul vertical este proporțional mai lung, deci punctele se „împrăștie” pe verticală exact cât trebuie pentru ca densitatea pe \(H\) să fie constantă.

Figura 7: Construcția unui punct uniform sub graficul lui \(cg\): abscisa \(X\) are densitatea \(g\), iar ordonata \(cg(X)U\) este aleasă uniform pe segmentul vertical \([0,\,cg(X)]\) de deasupra lui \(X\). Punctul \(M=(X,\,cg(X)U)\) este repartizat uniform pe subgraficul \(H\) al lui \(cg\).
Propoziția 8 (Un punct uniform sub graficul lui cg)

Fie \(X\) un vector aleator pe \(\R^d\) cu densitatea \(g\), \(U\sim\Unif(0,1)\) independentă de \(X\), \(c>0\) și \(H\) subgraficul lui \(cg\). Atunci punctul \(M=(X,\,c\,g(X)\,U)\) este repartizat uniform pe \(H\).

Demonstrație. Ideea demonstrației. Pe verticala \(X=x\), ordonata \(cg(x)U\) este uniformă pe \([0,cg(x)]\), iar abscisa are densitatea \(g(x)\); produsul „densitatea abscisei × densitatea ordonatei” este \(g(x)\cdot\frac{1}{cg(x)}=\frac1c\), constant pe \(H\). Formalizăm acest calcul pe dreptunghiuri \(A\times B\), unde arătăm că repartiția lui \(M\) și \(\Unif(H)\) dau aceeași valoare; două probabilități care coincid pe dreptunghiuri coincid pe toate mulțimile boreliene.

Pasul 1: calculul pe dreptunghiuri. Fie \(A\in\B(\R^d)\) și \(B\in\B(\R)\). Din independență, \((X,U)\) are densitatea \(g(x)\Ind_{[0,1]}(u)\) pe \(\R^d\times\R\) (criteriul de factorizare, Propoziția 38 din Cursul 1, aici pentru un vector și o variabilă: pe dreptunghiuri, \(\PP(X\in A',U\in B')=\int_{A'}g(x)\dd x\cdot\int_{B'}\Ind_{[0,1]}(u)\dd u\) este integrala lui \(g(x)\Ind_{[0,1]}(u)\) pe \(A'\times B'\), iar extinderea la toate mulțimile boreliene se face exact ca la Pasul 3 de mai jos). Evenimentul \(\{M\in A\times B\}\) este \(\{X\in A,\ cg(X)U\in B\}\), deci probabilitatea lui este integrala densității lui \((X,U)\) pe mulțimea \(\{(x,u):\ x\in A,\ cg(x)u\in B\}\): \[ \PP(M\in A\times B)=\int_{\R^d}\int_{\R}\Ind_A(x)\,\Ind_B\big(cg(x)u\big)\,g(x)\,\Ind_{[0,1]}(u)\dd u\dd x . \] Integrandul este nenegativ, deci, din teorema lui Fubini (Billingsley 1995, sec. 18), putem integra întâi în \(u\), pentru \(x\) fixat: \[ \PP(M\in A\times B)=\int_{\R^d}\Ind_A(x)\,I(x)\dd x,\qquad I(x)=\int_0^1\Ind_B\big(cg(x)u\big)\,g(x)\dd u . \] Dacă \(g(x)=0\), atunci \(I(x)=0\). Dacă \(g(x)>0\), schimbarea de variabilă \(t=cg(x)u\) (\(\dd u=\frac{\dd t}{cg(x)}\), iar \(u\in[0,1]\iff t\in[0,cg(x)]\)) dă \[ I(x)=\int_0^{cg(x)}\Ind_B(t)\,g(x)\,\frac{\dd t}{cg(x)}=\frac1c\,\lambda_1\big(B\cap[0,cg(x)]\big), \] formulă valabilă și pentru \(g(x)=0\) (atunci \(B\cap\{0\}\) are lungimea nulă). Deci \[ \PP(M\in A\times B)=\frac1c\int_{\R^d}\Ind_A(x)\,\lambda_1\big(B\cap[0,cg(x)]\big)\dd x . \]

Pasul 2: aceeași valoare pentru uniforma pe \(H\). Secțiunea mulțimii \((A\times B)\cap H\) prin \(x\) este \(B\cap[0,cg(x)]\) dacă \(x\in A\) și \(\emptyset\) altfel, deci, din teorema lui Fubini și \(\lambda_{d+1}(H)=c\), \[ \Unif(H)(A\times B)=\frac{\lambda_{d+1}\big((A\times B)\cap H\big)}{c}=\frac1c\int_{\R^d}\Ind_A(x)\,\lambda_1\big(B\cap[0,cg(x)]\big)\dd x=\PP(M\in A\times B). \]

Pasul 3: toate mulțimile boreliene. Notăm \(P_1(E)=\PP(M\in E)\) și \(P_2(E)=\Unif(H)(E)\), două probabilități pe \(\B(\R^{d+1})\), și fie \(\mathcal{C}\) clasa dreptunghiurilor \(A\times B\), cu \(A\in\B(\R^d)\), \(B\in\B(\R)\). Din Pașii 1–2, \(P_1=P_2\) pe \(\mathcal{C}\). Clasa \(\mathcal{C}\) este închisă la intersecții finite (este un \(\pi\)-sistem), deoarece \((A_1\times B_1)\cap(A_2\times B_2)=(A_1\cap A_2)\times(B_1\cap B_2)\), și generează \(\B(\R^{d+1})\): fiecare \(A\times B=(A\times\R)\cap(\R^d\times B)\) este o mulțime boreliană, iar \(\mathcal{C}\) conține produsele de intervale deschise, din care se obține orice mulțime deschisă din \(\R^{d+1}\) ca reuniune numărabilă. Din teorema de unicitate a măsurilor de probabilitate — două probabilități care coincid pe o clasă închisă la intersecții finite coincid pe \(\sigma\)-algebra generată de ea (Billingsley 1995, sec. 3) — rezultă \(P_1=P_2\) pe \(\B(\R^{d+1})\), adică \(\PP(M\in E)=\Unif(H)(E)\) pentru orice \(E\in\B(\R^{d+1})\): \(M\sim\Unif(H)\).■

Cele două propoziții, împreună cu Teorema 5, dau rezultatul central al secțiunii. Îl citim astfel: perechile \((X_n,U_n)\) sunt propunerile succesive, \(T\) este numărul de ordine al primei propuneri acceptate, iar \(Z=X_T\) este valoarea întoarsă de algoritm. Teorema spune două lucruri: cât costă o observație (\(T\) este repartizată geometric, cu media \(c\)) și că observația obținută are exact densitatea țintă.

Teorema 9 (Metoda respingerii)

Fie \(f\) și \(g\) densități pe \(\R^d\) și \(c\ge1\) astfel încât \(f\le cg\). Fie \((X_n)_{n\ge1}\) vectori aleatori \(\iid\) cu densitatea \(g\) și \((U_n)_{n\ge1}\) variabile \(\iid\) \(\Unif(0,1)\), independente de \((X_n)\). Definim \[ T=\inf\{n\ge1:\ c\,g(X_n)\,U_n\le f(X_n)\}. \] Atunci \(T\sim\Geom(1/c)\) (în particular \(T<\infty\) a.s. și \(\E[T]=c\)), iar \(Z=X_T\) are densitatea \(f\).

Demonstrație. Ideea demonstrației. Punctele \(M_n=(X_n,cg(X_n)U_n)\) sunt independente și uniforme sub graficul lui \(cg\), iar condiția de acceptare spune exact că \(M_n\) cade sub graficul lui \(f\). Primul punct care cade în \(G\) este uniform pe \(G\) (simularea repartiției condiționate prin respingere), iar abscisa unui punct uniform sub graficul lui \(f\) are densitatea \(f\). Numărul de încercări este geometric, cu probabilitatea de succes egală cu raportul volumelor, \(\lambda_{d+1}(G)/\lambda_{d+1}(H)=1/c\).

Pasul 1: punctele propuse. Fie \(M_n=(X_n,\,cg(X_n)U_n)\). Șirurile \((X_n)\) și \((U_n)\) fiind independente între ele și fiecare format din variabile i.i.d., perechile \((X_n,U_n)\), \(n\ge1\), sunt independente și identic repartizate; vectorii \(M_n\), funcții boreliene de câte o pereche, sunt atunci independenți și identic repartizați (Propoziția 39 din Cursul 1). Pentru fiecare \(n\), \(X_n\) are densitatea \(g\) și este independent de \(U_n\sim\Unif(0,1)\), deci, din Propoziția 8, repartiția comună a vectorilor \(M_n\) este \(\mu=\Unif(H)\).

Pasul 2: condiția de acceptare. Ordonata \(cg(X_n)U_n\) este nenegativă, deci \(cg(X_n)U_n\le f(X_n)\iff0\le cg(X_n)U_n\le f(X_n)\iff M_n\in G\), iar \(T=\inf\{n\ge1: M_n\in G\}\) este indicele din Teorema 5, cu \(\R^{d+1}\) în locul lui \(\R^d\) și \(G\) în rolul lui \(B\).

Pasul 3: probabilitatea de acceptare. Cum \(G\subseteq H\) (din \(f\le cg\)), \(\mu(G)=\lambda_{d+1}(G\cap H)/\lambda_{d+1}(H)=\lambda_{d+1}(G)/\lambda_{d+1}(H)=\frac1c>0\). Din Teorema 5, \(T\sim\Geom(1/c)\), deci \(T<\infty\) a.s. și \(\E[T]=1/\mu(G)=c\).

Pasul 4: punctul acceptat. Tot din Teorema 5, \(M_T\) are repartiția \(\mu(\cdot\mid G)\); pentru \(A\in\B(\R^{d+1})\), \[ \mu(A\mid G)=\frac{\mu(A\cap G)}{\mu(G)}=\frac{\lambda_{d+1}(A\cap G)/c}{1/c}=\lambda_{d+1}(A\cap G)=\frac{\lambda_{d+1}(A\cap G)}{\lambda_{d+1}(G)} , \] deci \(M_T\sim\Unif(G)\) (raționamentul Corolarului 6, cu \(H\) în locul dreptunghiului).

Pasul 5: proiecția. Pe \(\{T<\infty\}\), eveniment de probabilitate \(1\), \(M_T=(X_T,cg(X_T)U_T)\), deci abscisa lui \(M_T\) este \(Z=X_T\). Din Propoziția 7, aplicată punctului \(M_T\sim\Unif(G)\), abscisa \(Z=X_T\) are densitatea \(f\). Am arătat astfel că \(T\sim\Geom(1/c)\) și că valoarea acceptată are densitatea țintă.■

Algoritmul corespunzător:

  1. generăm \(X\sim g\) și, independent, \(U\sim\Unif(0,1)\);
  2. dacă \(U\le\dfrac{f(X)}{c\,g(X)}\), acceptăm și întoarcem \(Z=X\); altfel respingem și revenim la pasul 1.

Rezultatul admite și o demonstrație directă, fără geometrie (Casella and Berger 2002, Ex. 5.59). Notăm \(E_n=\{c\,g(X_n)U_n\le f(X_n)\}\) evenimentul de acceptare la pasul \(n\) și \(a(x)=\frac{f(x)}{cg(x)}\in[0,1]\) pentru \(g(x)>0\). În punctele cu \(g(x)=0\) avem și \(f(x)=0\) (din \(0\le f\le cg\)), condiția de acceptare \(0\le0\) este îndeplinită și punem \(a(x)=1\); aceste puncte nu contează, deoarece \(\PP(g(X_n)=0)=\int_{\{g=0\}}g(x)\dd x=0\). Cu această convenție, \(E_n=\{U_n\le a(X_n)\}\).

Pasul 1: o singură propunere. Din independența lui \(X_1\) și \(U_1\), perechea \((X_1,U_1)\) are densitatea \(g(x)\Ind_{[0,1]}(u)\), iar din teorema lui Fubini (integrand nenegativ; integrăm întâi în \(u\)), pentru \(A\in\B(\R^d)\), \[ \begin{aligned} \PP\big(X_1\in A,\ E_1\big)&=\int_{\R^d}\Ind_A(x)\Big(\int_0^1\Ind_{\{u\le a(x)\}}\dd u\Big)g(x)\dd x=\int_{\R^d}\Ind_A(x)\,\PP\big(U_1\le a(x)\big)\,g(x)\dd x\\ &=\int_{A\cap\{g>0\}}\frac{f(x)}{cg(x)}\,g(x)\dd x=\frac1c\int_Af(x)\dd x , \end{aligned} \tag{6}\] deoarece \(\PP(U_1\le a)=\int_0^1\Ind_{\{u\le a\}}\dd u=a\) pentru \(a\in[0,1]\), iar la ultima egalitate am folosit \(f=0\) pe \(\{g=0\}\).

Pasul 2: numărul de încercări. Pentru \(A=\R^d\), probabilitatea de acceptare este \(\PP(E_1)=\frac1c\int_{\R^d}f(x)\dd x=\frac1c\). Evenimentul \(E_n\) depinde doar de perechea \((X_n,U_n)\), iar perechile sunt independente și identic repartizate, deci evenimentele \(E_1,E_2,\dots\) sunt independente și au toate probabilitatea \(\frac1c\). Cum \(\{T=k\}=E_1^c\cap\dots\cap E_{k-1}^c\cap E_k\), \[ \PP(T=k)=\Big(1-\frac1c\Big)^{k-1}\frac1c,\qquad k\ge1, \] adică \(T\sim\Geom(1/c)\); în particular \(T<\infty\) a.s. (suma acestor probabilități este \(1\)).

Pasul 3: valoarea acceptată. Pentru \(k\ge1\), \(\{T=k,\ X_T\in A\}=E_1^c\cap\dots\cap E_{k-1}^c\cap\big(\{X_k\in A\}\cap E_k\big)\). Primele \(k-1\) evenimente depind de primele \(k-1\) perechi, iar ultimul doar de perechea \((X_k,U_k)\), care are aceeași repartiție ca \((X_1,U_1)\); din independență și din (6), \[ \PP(T=k,\ X_T\in A)=\Big(1-\frac1c\Big)^{k-1}\cdot\frac1c\int_Af(x)\dd x . \] Însumând după \(k\) (evenimentele \(\{T=k\}\) sunt disjuncte, cu reuniunea de probabilitate \(1\)) și folosind \(\sum_{k\ge1}\big(1-\frac1c\big)^{k-1}=\frac{1}{1-(1-1/c)}=c\), \[ \PP(X_T\in A)=\sum_{k\ge1}\Big(1-\frac1c\Big)^{k-1}\frac1c\int_Af(x)\dd x=c\cdot\frac1c\int_Af(x)\dd x=\int_Af(x)\dd x ,\qquad A\in\B(\R^d), \] deci \(X_T\) are densitatea \(f\).

Observație

Câteva remarci practice.

  • Eficiența. Probabilitatea de acceptare este \(1/c\), iar numărul mediu de propuneri pentru o observație este \(c\). Condiția \(f\le cg\) înseamnă \(c\ge f(x)/g(x)\) în orice punct cu \(g(x)>0\) (și \(f(x)=0\) acolo unde \(g(x)=0\)), deci cea mai mică constantă admisibilă pentru o propunere dată — cea care maximizează probabilitatea de acceptare — este \(c^*=\sup_{x:\,g(x)>0}f(x)/g(x)\); căutăm o propunere \(g\) ușor de simulat, cu cozi cel puțin la fel de grele ca ale lui \(f\) (altfel \(f/g\) este nemărginită) și cu \(c^*\) cât mai aproape de \(1\).
  • Densități nenormalizate. Dacă \(f=\tilde f/K\) cu \(K=\int\tilde f\) necunoscut și \(\tilde f\le Mg\), atunci \(f\le\frac MKg\), deci putem lua \(c=\frac MK\), iar condiția de acceptare \[ U\le\frac{f(X)}{c\,g(X)}=\frac{\tilde f(X)/K}{(M/K)\,g(X)}=\frac{\tilde f(X)}{M\,g(X)} \] nu depinde de \(K\) (Knight 2000, Pb. 2.10). Metoda funcționează deci și când densitatea țintă este cunoscută doar până la o constantă multiplicativă (situație tipică în statistica bayesiană); probabilitatea de acceptare este \(\frac1c=\frac KM\). Indicatorii de acceptare \(\Ind_{E_n}\) sunt i.i.d. \(\Bern(K/M)\), deci, din LNM tare (Teorema 61 din Cursul 1), proporția de propuneri acceptate dintre primele \(N\) converge a.s. la \(K/M\): înmulțită cu \(M\), ea estimează consistent constanta \(K\).

Aplicarea metodei cere mereu aceiași pași: alegem propunerea \(g\); calculăm constanta \(c=\sup f/g\); scriem condiția de acceptare \(U\le f(X)/(cg(X))\) în forma cea mai simplă; citim probabilitatea de acceptare \(1/c\). Îi parcurgem întâi pe un caz în care toate calculele se fac de mână.

Exemplul 13 (Un prim exemplu: densitatea \(3x^2\) cu propunere uniformă)

Reluăm densitatea țintă \(f(x)=3x^2\,\Ind_{(0,1)}(x)\) din Exemplul 9, cu propunerea \(g=\Ind_{(0,1)}\) (densitatea uniformă standard).

Constanta \(c\). Pe \((0,1)\), raportul \(f(x)/g(x)=3x^2\) este crescător, deci \(\sup_{0<x<1}f(x)/g(x)=\lim_{x\nearrow1}3x^2=3\): cea mai mică constantă cu \(f\le cg\) este \(c=3\). Geometric, \(H\) este dreptunghiul \([0,1]\times[0,3]\), de arie \(3\), iar \(G\) este regiunea de sub parabola \(y=3x^2\), de arie \(1\).

Algoritmul. Generăm \(X\) și \(U\) independente, repartizate \(\Unif(0,1)\); acceptăm și întoarcem \(Z=X\) dacă \[ U\le\frac{f(X)}{c\,g(X)}=\frac{3X^2}{3}=X^2 \] (echivalent: punctul \((X,3U)\), uniform în dreptunghiul \(H\), se află sub parabolă, \(3U\le3X^2\)); altfel generăm o nouă pereche.

O rulare, pas cu pas. Să presupunem că generatorul produce, pe rând, perechile \((x_n,u_n)\) de mai jos. \[ \begin{array}{l|cccccc} n & 1 & 2 & 3 & 4 & 5 & 6\\ \hline x_n & 0.42 & 0.75 & 0.88 & 0.21 & 0.64 & 0.97\rule{0pt}{2.6ex}\\ u_n & 0.61 & 0.83 & 0.37 & 0.09 & 0.30 & 0.92\\[2pt] x_n^2 & 0.1764 & 0.5625 & 0.7744 & 0.0441 & 0.4096 & 0.9409\\[2pt] u_n\le x_n^2\,? & \text{nu} & \text{nu} & \text{da} & \text{nu} & \text{da} & \text{da} \end{array} \] La prima pereche, \(u_1=0.61>x_1^2=0.1764\): respingem (punctul \((x_1,3u_1)=(0.42,\,1.83)\) este deasupra parabolei, care în \(x=0.42\) are înălțimea \(f(0.42)\approx0.53\)). La a doua, \(0.83>0.5625\): respingem. La a treia, \(0.37\le0.7744\): acceptăm; prima observație este \(Z_1=0.88\), obținută după \(T=3\) propuneri. Continuând cu perechi noi, obținem \(Z_2=0.64\) (după încă două propuneri) și \(Z_3=0.97\) (după încă una). O propunere \(x\) este acceptată cu probabilitatea \(\PP(U\le x^2)=x^2\): cele apropiate de \(1\) sunt acceptate aproape sigur, cele apropiate de \(0\) aproape niciodată — de aceea valorile acceptate sunt mai degrabă mari, cum cere densitatea \(3x^2\).

Probabilitatea de acceptare. Din Teorema 9, ea este \(\frac1c=\frac13\), iar numărul de propuneri pentru o observație este \(T\sim\Geom(\frac13)\), cu \(\E[T]=3\). O verificăm direct: perechea \((X,U)\) are densitatea \(1\) pe \([0,1]^2\), deci \[ \PP(U\le X^2)=\int_0^1\Big(\int_0^{x^2}\dd u\Big)\dd x=\int_0^1x^2\dd x=\frac13 , \] raportul dintre aria de sub parabolă și aria dreptunghiului \(H\). Interpretare: în medie, două propuneri din trei sunt irosite (rularea de mai sus, cu trei acceptări din șase, a fost mai norocoasă decât media); pentru un eșantion de volum \(1000\) trebuie generate în medie \(3000\) de perechi, adică \(6000\) de uniforme.

Repartiția valorii acceptate. Pentru \(t\in[0,1]\), același calcul restrâns la \(x\le t\) (relația (6) cu \(A=[0,t]\)) dă \(\PP(X\le t,\ U\le X^2)=\int_0^tx^2\dd x=\frac{t^3}{3}\). Împărțind la probabilitatea de acceptare, \[ \PP\big(X\le t\mid U\le X^2\big)=\frac{t^3/3}{1/3}=t^3 , \] funcția de repartiție a densității \(3x^2\): o propunere acceptată are într-adevăr repartiția țintă.

Comparație cu metoda inversă. Metoda inversă, \(X=U^{1/3}\), folosește o singură uniformă pe observație; respingerea folosește două uniforme la fiecare încercare, deci în medie \(2\cdot3=6\). Când \(F^{-1}\) este disponibilă explicit, metoda inversă este preferabilă; respingerea devine utilă atunci când nu este, ca în exemplul următor. Propunerea trebuie însă aleasă cu grijă: pentru densitatea arcsinus \(\frac{1}{\pi\sqrt{x(1-x)}}\) din Exemplul 9, raportul \(f(x)/g(x)=f(x)\) tinde la \(+\infty\) când \(x\to0\) sau \(x\to1\), deci nu există nicio constantă \(c\) cu \(f\le cg\): propunerea uniformă nu poate fi folosită.

Atenție!

După o respingere se generează o pereche complet nouă \((X,U)\), iar testul de acceptare se face cu o uniformă independentă de propunere. Două greșeli frecvente schimbă repartiția rezultatului:

  • păstrarea propunerii respinse: dacă, după o respingere, am păstra \(X\) și am genera doar un nou \(U\), până la acceptare, atunci orice propunere cu \(f(X)>0\) ar fi acceptată în cele din urmă (pentru \(X=x\) fixat, fiecare nou test reușește cu aceeași probabilitate \(\frac{f(x)}{cg(x)}>0\)), deci algoritmul ar întoarce chiar prima propunere, repartizată după \(g\), nu după \(f\) (în Exemplul 13: uniformă, nu cu densitatea \(3x^2\));
  • aceeași uniformă pentru propunere și pentru test: Teorema 9 cere ca \(U_n\) să fie independentă de \(X_n\). În Exemplul 13, dacă am lua \(X=U\), testul \(U\le X^2\) ar deveni \(U\le U^2\), care nu este îndeplinit pentru niciun \(U\in(0,1)\).
Exemplul 14 (Repartiția Beta cu propunere uniformă)

Fie \(f\) densitatea \(\BetaD(a,b)\) cu \(a=2.7\), \(b=6.3\), \(f(x)=\frac{x^{a-1}(1-x)^{b-1}}{B(a,b)}\), \(0<x<1\), și \(g=\Ind_{(0,1)}\) (Casella and Berger 2002, Ex. 5.6.7). Funcția de repartiție Beta (beta incompletă) nu se inversează explicit.

Constanta \(c\). Cum \(g=1\) pe \((0,1)\), cea mai mică constantă cu \(f\le cg\) este \(c=\sup_{0<x<1}f(x)\), valoarea densității în modul ei. Derivăm logaritmul densității (\(\ln\) este strict crescătoare, deci \(f\) și \(\ln f\) au același punct de maxim): \[ \frac{\dd}{\dd x}\ln f(x)=\frac{a-1}{x}-\frac{b-1}{1-x}=\frac{(a-1)(1-x)-(b-1)x}{x(1-x)}=\frac{(a-1)-(a+b-2)x}{x(1-x)} . \] Cum \(a,b>1\), numărătorul este pozitiv pentru \(x<x^*\) și negativ pentru \(x>x^*\), unde \(x^*=\frac{a-1}{a+b-2}=\frac{1.7}{7}\approx0.243\); deci \(f\) crește pe \((0,x^*]\) și descrește pe \([x^*,1)\), iar \(x^*\) este punctul de maxim global. (Pentru \(a<1\) densitatea ar fi nemărginită în \(0\) și nicio constantă nu ar funcționa cu propunerea uniformă.) Prin urmare \[ c=f(x^*)=\frac{(x^*)^{a-1}(1-x^*)^{b-1}}{B(a,b)}=\frac{(1.7/7)^{1.7}\,(5.3/7)^{5.3}}{B(2.7,6.3)}\approx2.670, \] unde \(B(2.7,6.3)=\frac{\Gamma(2.7)\Gamma(6.3)}{\Gamma(9)}\approx0.00773\) (în R: dbeta(1.7 / 7, 2.7, 6.3)). Pas cu pas: \((x^*)^{1.7}=0.2429^{1.7}\approx0.0902\) și \((1-x^*)^{5.3}=0.7571^{5.3}\approx0.2289\), cu produsul \(\approx0.02064\), iar \(0.02064/0.00773\approx2.670\).

Eficiența. Din Teorema 9, probabilitatea de acceptare este \(1/c\approx0.375\), iar numărul de perechi \((X,U)\) necesare pentru o observație este \(T\sim\Geom(p)\) cu \(p=1/c\), deci \(\E[T]=\frac1p=c\approx2.67\) și, din formula varianței repartiției geometrice (tabelul repartițiilor discrete din Cursul 1), \(\Var(T)=\frac{1-p}{p^2}=c^2\big(1-\frac1c\big)=c(c-1)\approx4.46\). Cum \(g=1\) pe \((0,1)\), condiția de acceptare \(U\le\frac{f(X)}{cg(X)}\) devine \(U\le f(X)/c\). Media repartiției este \(\frac{a}{a+b}=\frac{2.7}{9}=0.3\).

Citirea probabilității de acceptare. Numărul \(1/c\approx0.375\) este raportul dintre aria de sub graficul lui \(f\) (egală cu \(1\)) și aria dreptunghiului \([0,1]\times[0,c]\) de sub graficul lui \(cg\) (egală cu \(c\)): în medie, din opt propuneri sunt acceptate trei, iar un eșantion de volum \(1000\) cere în medie \(2670\) de perechi \((X,U)\), adică \(5340\) de uniforme. Acceptarea depinde de punctul propus: propunerea \(x\) este acceptată cu probabilitatea \(f(x)/c\), egală cu \(1\) în modul \(x^*\approx0.243\), cu \(f(0.1)/c\approx0.55\), cu \(f(0.5)/c\approx0.38\) și cu numai \(f(0.8)/c\approx0.007\) — propunerile din zona în care densitatea Beta este aproape nulă sunt aproape toate respinse (Figura 8, stânga).

a <- 2.7; b <- 6.3
cst <- dbeta((a - 1) / (a + b - 2), a, b)        # c = max f, atins în modul
set.seed(11)
m <- 3e4
x <- runif(m); u <- runif(m)                     # m perechi (X, U)
z <- x[u <= dbeta(x, a, b) / cst]               # valorile acceptate
c(c = cst, acceptare = length(z) / m, teoretic = 1 / cst)
#>         c acceptare  teoretic 
#>    2.6697    0.3726    0.3746
c(media = mean(z), teoretic = a / (a + b))
#>    media teoretic 
#>   0.2991   0.3000

Citim rezultatul: constanta este \(c=2.6697\); din cele \(m=30000\) de perechi au fost acceptate \(11178\), adică o proporție de \(0.3726\), foarte apropiată de \(1/c\approx0.3746\) (în medie ne așteptam la \(30000/c\approx11237\) de acceptări); media valorilor acceptate, \(0.2991\), este apropiată de media teoretică \(0.3\). Codul este vectorizat: generăm dinainte \(m\) perechi și păstrăm doar valorile acceptate, deci volumul final este aleator (\(\approx0.375\,m\)); pentru un volum fix generăm cu o marjă și trunchiem (Exemplul 15).

Arată codul R
k <- 600                                          # primele 600 de propuneri
dp <- data.frame(x = x[1:k], y = cst * u[1:k],
                 acc = u[1:k] <= dbeta(x[1:k], a, b) / cst)
tt <- seq(0, 1, length.out = 300)
p1 <- ggplot(dp, aes(x, y)) +
  geom_point(aes(colour = acc), size = 0.6, show.legend = FALSE) +
  geom_line(data = data.frame(x = tt, y = dbeta(tt, a, b)),
            colour = culori[["bleumarin"]]) +
  geom_hline(yintercept = cst, linetype = 2, colour = culori[["gri"]]) +
  scale_colour_manual(values = c(`FALSE` = "grey70",
                                 `TRUE` = culori[["rosu"]])) +
  labs(x = "x", y = "c g(x) U")
p2 <- ggplot(data.frame(z = z), aes(z)) +
  geom_histogram(aes(y = after_stat(density)), bins = 40,
                 fill = culori[["albastru"]], alpha = 0.45, colour = "white",
                 linewidth = 0.1) +
  geom_line(data = data.frame(z = tt, y = dbeta(tt, a, b)), aes(z, y),
            colour = culori[["rosu"]]) +
  labs(x = "x", y = "densitate")
p1 + p2
Figura 8: Metoda respingerii pentru \(\mathrm{Beta}(2.7,6.3)\) cu propunere uniformă. Stânga: punctele \((X_i,\,cU_i)\) sunt uniforme sub graficul lui \(cg\) (linia întreruptă); cele de sub graficul lui \(f\) (roșu) sunt acceptate. Dreapta: histograma abscisei punctelor acceptate și densitatea \(f\).
Exemplul 15 (Repartiția normală din repartiția exponențială)

Simulăm întâi \(|Z|\), \(Z\sim\Norm(0,1)\), apoi îi atribuim un semn aleator.

Densitatea țintă. Pentru \(x\ge0\), \(\PP(|Z|\le x)=2\Phi(x)-1\), iar derivând, \(|Z|\) are densitatea \(f(x)=2\phi(x)=\frac{2}{\sqrt{2\pi}}e^{-x^2/2}\), \(x\ge0\). Ca propunere folosim \(h(x)=\lambda e^{-\lambda x}\), \(x\ge0\) (Exemplul 7), cu o coadă mai grea decât cea gaussiană.

Pasul 1: constanta. Pentru \(x\ge0\), \(\frac{f(x)}{h(x)}=\frac{2}{\lambda\sqrt{2\pi}}e^{\psi(x)}\), cu \(\psi(x)=-\frac{x^2}{2}+\lambda x\). Cum \(\psi'(x)=\lambda-x\) este pozitivă pe \([0,\lambda)\) și negativă pe \((\lambda,\infty)\), \(\psi\) crește pe \([0,\lambda]\) și descrește pe \([\lambda,\infty)\), deci are pe \([0,\infty)\) maximul \(\psi(\lambda)=-\frac{\lambda^2}{2}+\lambda^2=\frac{\lambda^2}{2}\), atins în \(x=\lambda>0\); exponențiala fiind crescătoare, \[ c(\lambda)=\sup_{x\ge0}\frac{f(x)}{h(x)}=\frac{2}{\lambda\sqrt{2\pi}}\,e^{\lambda^2/2},\qquad \frac{f(x)}{c(\lambda)h(x)}=e^{-\frac{x^2}{2}+\lambda x-\frac{\lambda^2}{2}}=e^{-\frac12(x-\lambda)^2}. \]

Pasul 2: alegerea optimă a lui \(\lambda\). Cum \(\ln c(\lambda)=\ln\frac{2}{\sqrt{2\pi}}-\ln\lambda+\frac{\lambda^2}{2}\), avem \(\frac{\dd}{\dd\lambda}\ln c(\lambda)=\lambda-\frac1\lambda=\frac{\lambda^2-1}{\lambda}\), negativă pe \((0,1)\) și pozitivă pe \((1,\infty)\); minimul este în \(\lambda=1\): \[ c(1)=\frac{2}{\sqrt{2\pi}}e^{1/2}=\sqrt{\frac{2e}{\pi}}\approx1.3155 , \] cu probabilitatea de acceptare \(\sqrt{\pi/(2e)}\approx0.760\). Pentru comparație, \(c(0.5)=\frac{2}{0.5\sqrt{2\pi}}e^{0.125}\approx1.596\cdot1.133\approx1.81\) și \(c(2)=\frac{2}{2\sqrt{2\pi}}e^{2}\approx0.399\cdot7.389\approx2.95\): o alegere nepotrivită a parametrului propunerii poate dubla costul.

Citirea geometrică (Figura 9, aflată imediat după exemplu). Pentru \(\lambda=1\), anvelopa \(c\,h(x)=\sqrt{2e/\pi}\,e^{-x}\) atinge ținta în \(x=\lambda=1\), unde \(f(1)=c\,h(1)=\frac{2}{\sqrt{2\pi}}e^{-1/2}\approx0.484\), și este strict deasupra ei în rest; o constantă mai mică ar coborî anvelopa sub \(f\) lângă \(x=1\). Propunerea \(x\) este acceptată cu probabilitatea \(\frac{f(x)}{c\,h(x)}=e^{-(x-1)^2/2}\): egală cu \(1\) în punctul de tangență, cu \(e^{-1/2}\approx0.61\) în \(x=0\) și cu \(e^{-2}\approx0.14\) în \(x=3\). De exemplu, perechea \((x,u)=(0.3,\,0.90)\) este respinsă, deoarece \(e^{-(0.3-1)^2/2}=e^{-0.245}\approx0.783<0.90\), iar perechea \((x,u)=(1.4,\,0.50)\) este acceptată, deoarece \(e^{-(1.4-1)^2/2}=e^{-0.08}\approx0.923\ge0.50\).

Pasul 3: simetrizarea. Fie \(X\sim f\) și \(S\) independentă de \(X\), cu \(\PP(S=1)=\PP(S=-1)=\frac12\). Din formula probabilității totale și independență, \(\PP(SX\le t)=\frac12\PP(X\le t)+\frac12\PP(-X\le t)\). Pentru \(t\ge0\): \(\PP(X\le t)=2\Phi(t)-1\) și \(\PP(-X\le t)=1\), deci \(\PP(SX\le t)=\Phi(t)\). Pentru \(t<0\): \(\PP(X\le t)=0\) și \(\PP(X\ge-t)=1-(2\Phi(-t)-1)=2\Phi(t)\) (din \(\Phi(-t)=1-\Phi(t)\)), deci \(\PP(SX\le t)=\Phi(t)\). Așadar \(SX\sim\Norm(0,1)\).

Algoritmul: generăm \(X\sim\Exp(1)\) și \(U\sim\Unif(0,1)\) până când \(U\le e^{-(X-1)^2/2}\) (Teorema 9, cu ținta \(f\), propunerea \(h\) pentru \(\lambda=1\) și \(c=c(1)\): valoarea acceptată are densitatea \(f\)); întoarcem \(X\) sau \(-X\), cu probabilitatea \(\frac12\) fiecare (Pasul 3). Costul: o observație normală cere în medie \(c\approx1.32\) perechi \((X,U)\) — fiecare cu o uniformă pentru exponențiala \(X=-\ln U'\) (Exemplul 7) și una pentru \(U\) — plus o uniformă pentru semn, adică aproximativ \(2\cdot1.32+1\approx3.6\) uniforme.

Legătura cu propunerea Laplace. Echivalent, este metoda respingerii cu propunerea Laplace \(g(x)=\frac12e^{-|x|}\), \(x\in\R\), pentru ținta \(\phi\) (Casella and Berger 2002, Ex. 5.63). Într-adevăr, dacă \(E\sim\Exp(1)\) și \(S\) este un semn aleator independent, atunci, ca la Pasul 3, \(\PP(SE\le t)=\frac12\PP(E\le t)+\frac12\PP(E\ge-t)\), care este \(\frac12e^{t}\) pentru \(t<0\) și \(\frac12(1-e^{-t})+\frac12=1-\frac12e^{-t}\) pentru \(t\ge0\): funcția de repartiție Laplace \((0,1)\) din Exemplul 10, deci \(SE\sim g\). Raportul \[ \frac{\phi(x)}{g(x)}=\frac{2}{\sqrt{2\pi}}\,e^{-x^2/2+|x|}=\frac{2}{\sqrt{2\pi}}\,e^{\psi(|x|)}\qquad(\psi\text{ de la Pasul 1, cu }\lambda=1) \] este funcția \(f/h\) de mai sus evaluată în \(|x|\), deci are același supremum \(c=\sqrt{2e/\pi}\), iar condiția de acceptare \(U\le\frac{\phi(x)}{cg(x)}=e^{-(|x|-1)^2/2}\) depinde doar de \(|x|=E\). Cele două variante diferă doar prin momentul în care se alege semnul (înainte sau după acceptare), iar semnul este independent de \((E,U)\).

rnorm_resp <- function(n) {
  out <- numeric(0)
  while (length(out) < n) {
    m <- ceiling(1.35 * (n - length(out))) + 20      # marjă peste c = 1.3155
    x <- rexp(m); u <- runif(m)
    x <- x[u <= exp(-(x - 1)^2 / 2)]                  # jumătăți de normală
    out <- c(out, ifelse(runif(length(x)) <= 0.5, x, -x))  # semn aleator
  }
  out[1:n]
}
set.seed(13)
z <- rnorm_resp(1e4)
c(media = mean(z), var = var(z), q975 = quantile(z, 0.975, names = FALSE),
  c = sqrt(2 * exp(1) / pi), acceptare = sqrt(pi / (2 * exp(1))))
#>     media       var      q975         c acceptare 
#>  -0.01185   0.99558   1.96158   1.31549   0.76017

Media, varianța și cuantila de ordin \(0.975\) ale eșantionului simulat (\(-0.012\), \(0.996\) și \(1.962\)) sunt apropiate de \(0\), \(1\) și \(z_{0.975}\approx1.96\); ultimele două numere afișate sunt constanta \(c\) și probabilitatea de acceptare teoretică.

Figura 9: Metoda respingerii pentru jumătatea de normală: ținta \(f(x)=2\phi(x)\), \(x\ge0\), propunerea \(h(x)=e^{-x}\) (linie întreruptă) și anvelopa \(c\,h(x)\), cu \(c=\sqrt{2e/\pi}\), tangentă la \(f\) în \(x=1\). Un punct uniform de sub anvelopă este acceptat dacă nimerește în zona verde, de sub \(f\). Curba punctată este densitatea normală standard \(\phi(x)=\frac12f(|x|)\) a rezultatului: un semn aleator mută valoarea acceptată în stânga cu probabilitatea \(\frac12\).

În Figura 9, zona roșie dintre anvelopă și țintă corespunde propunerilor respinse: aria ei este \(c-1\approx0.32\), față de aria \(1\) a zonei verzi, deci fracțiunea acceptată este \(\frac{1}{1+0.32}=\frac1c\approx0.76\). Propunerea \(h\) însăși (linia întreruptă) nu domină ținta — lângă \(x=1\) ea se află sub \(f\) — și de aceea trebuie înmulțită cu \(c\).

Atenție!

Propunerea trebuie să aibă cozi cel puțin la fel de grele ca ținta. Nu putem simula repartiția Cauchy prin respingere cu propunere normală: \[ \frac{1/(\pi(1+x^2))}{\phi(x)}=\sqrt{\frac2\pi}\,\frac{e^{x^2/2}}{1+x^2}\xrightarrow[|x|\to\infty]{}+\infty , \] deoarece \(e^{x^2/2}\ge1+\frac{x^2}{2}+\frac{x^4}{8}\) (primii termeni ai seriei exponențialei), deci raportul este cel puțin \(\sqrt{\frac2\pi}\cdot\frac{x^4}{8(1+x^2)}\to\infty\). Prin urmare, pentru ținta \(f(x)=\frac{1}{\pi(1+x^2)}\) și propunerea \(g=\phi\), nu există nicio constantă \(c\) cu \(f\le cg\). Dacă am folosi totuși o constantă finită \(c\), condiția de acceptare \(U_1\le\frac{f(X_1)}{cg(X_1)}\) ar avea, pentru \(X_1=x\), probabilitatea \(\PP\big(U_1\le\frac{f(x)}{cg(x)}\big)=\min\big(\frac{f(x)}{cg(x)},1\big)\), iar relația (6) ar deveni \[ \PP(X_1\in A,\,E_1)=\int_A\min\Big(\frac{f(x)}{cg(x)},1\Big)g(x)\dd x=\frac1c\int_A\min\big(f(x),cg(x)\big)\dd x . \] Cu \(\kappa=\int_{\R}\min(f,cg)<1\), probabilitatea de acceptare ar fi \(\kappa/c\), iar calculul de la Pasul 3 al demonstrației directe ar da \(\PP(X_T\in A)=\frac1\kappa\int_A\min(f,cg)\): algoritmul ar produce densitatea \(\frac1\kappa\min(f,cg)\), nu \(f\), care subestimează sistematic cozile (acolo unde \(f>cg\)).

Metoda respingerii rezolvă cazurile în care cunoaștem densitatea (chiar și doar până la o constantă), dar nu și funcția cuantilă. Pentru multe repartiții importante există însă o a treia cale, adesea mai rapidă: repartiția dorită este repartiția unei funcții de variabile pe care știm deja să le simulăm.

5 Simulare prin transformări

Dacă \(X\) este un vector aleator pe care știm să îl simulăm și \(h\) este o funcție, atunci simulăm \(Y=h(X)\) aplicând \(h\) valorilor simulate; rămâne de identificat repartiția lui \(Y\). Instrumentul este Teorema schimbării de variabilă din Cursul 1 (Teorema 52 din Cursul 1), pe care o reamintim: dacă vectorul \(d\)-dimensional \(X\) are densitatea \(f_X\), \(S\subseteq\R^d\) este o mulțime deschisă cu \(\PP(X\in S)=1\), iar \(h:S\to\R^d\) este injectivă, de clasă \(C^1\), cu iacobianul \(J_h(x)\ne0\) pentru orice \(x\in S\), atunci \(h(S)\) este deschisă, \(h^{-1}:h(S)\to S\) este de clasă \(C^1\), cu \(J_{h^{-1}}(y)=1/J_h\big(h^{-1}(y)\big)\), iar \(Y=h(X)\) are densitatea \[ f_Y(y)=f_X\big(h^{-1}(y)\big)\,\big|J_{h^{-1}}(y)\big|\,\Ind_{h(S)}(y),\qquad y\in\R^d . \tag{7}\] În aplicații, densitatea obținută este adesea un produs de funcții care depind de grupe diferite de coordonate; atunci grupele de coordonate sunt independente, iar densitățile lor se citesc din factori. Acesta este conținutul criteriului de mai jos, pe care îl vom folosi din nou în Cursul 5.

5.1 Criteriul de factorizare

În Cursul 1 am văzut că variabilele aleatoare cu densități sunt independente exact atunci când densitatea comună este produsul densităților marginale (Propoziția 38 din Cursul 1). Pentru a citi independența din forma densității comune este mai comodă următoarea variantă, în care factorii nu trebuie să fie densități.

Lema 10 (Factorizarea densității comune)

Fie \(U\) și \(V\) vectori aleatori (de dimensiuni \(p\), respectiv \(q\)) astfel încât \((U,V)\) are densitatea \(f(u,v)=a(u)\,b(v)\) pentru orice \((u,v)\), cu \(a,b\ge0\) boreliene. Atunci \(U\) și \(V\) sunt independenți, iar densitățile lor sunt \(f_U=c_b\,a\) și \(f_V=c_a\,b\), unde \(c_a=\int a\) și \(c_b=\int b\) (cu \(c_ac_b=1\)).

Demonstrație. Ideea demonstrației. Integrând densitatea comună în câte una dintre variabile obținem densitățile marginale, proporționale cu \(a\), respectiv \(b\); produsul lor este chiar densitatea comună, iar probabilitatea unui dreptunghi \(C\times D\) se desface atunci în produsul probabilităților.

Pasul 1: constantele. Integrandul \(a(u)b(v)\) este nenegativ, deci, din teorema lui Fubini–Tonelli (Billingsley 1995, sec. 18), integrala dublă se calculează iterat: \[ 1=\iint a(u)b(v)\dd u\dd v=\int\Big(\int a(u)\dd u\Big)b(v)\dd v=\int a(u)\dd u\cdot\int b(v)\dd v=c_ac_b . \] Produsul \(c_ac_b\) fiind \(1\), niciuna dintre constante nu este \(0\) sau \(+\infty\) (altfel produsul ar fi \(0\) sau \(+\infty\)), deci \(c_a,c_b\in(0,\infty)\).

Pasul 2: marginalele. Din Propoziția 36 din Cursul 1, \[ \begin{aligned} f_U(u)&=\int f(u,v)\dd v=a(u)\int b(v)\dd v=c_b\,a(u),\\ f_V(v)&=\int f(u,v)\dd u=b(v)\int a(u)\dd u=c_a\,b(v). \end{aligned} \]

Pasul 3: independența. Din Pașii 1–2, \(f_U(u)f_V(v)=c_ac_b\,a(u)b(v)=a(u)b(v)=f(u,v)\) pentru orice \((u,v)\). Pentru boreliene \(C\subseteq\R^p\), \(D\subseteq\R^q\), din nou din Fubini–Tonelli, \[ \begin{aligned} \PP(U\in C,\,V\in D)&=\int_C\int_Df_U(u)f_V(v)\dd v\dd u=\int_Cf_U(u)\dd u\cdot\int_Df_V(v)\dd v\\ &=\PP(U\in C)\,\PP(V\in D), \end{aligned} \] adică \(U\) și \(V\) sunt independenți (Definiția 37 din Cursul 1, în forma cu mulțimi boreliene).■

Exemplul 16 (Citirea independenței din forma densității)

Fie \((U,V)\) cu densitatea \(f(u,v)=6e^{-2u-3v}\) pentru \(u>0\), \(v>0\) și \(f(u,v)=0\) în rest. Indicatorul cadranului \(\{u>0,\ v>0\}\) este produsul indicatorilor celor două semiaxe, deci, pentru orice \((u,v)\in\R^2\), \[ f(u,v)=a(u)\,b(v),\qquad a(u)=e^{-2u}\,\Ind_{(0,\infty)}(u),\quad b(v)=6e^{-3v}\,\Ind_{(0,\infty)}(v). \] Constantele din Lema 10 sunt \(c_a=\int_0^\infty e^{-2u}\dd u=\frac12\) și \(c_b=\int_0^\infty6e^{-3v}\dd v=2\) (într-adevăr, \(c_ac_b=1\)). Prin urmare \(U\) și \(V\) sunt independente, cu densitățile \(f_U(u)=c_b\,a(u)=2e^{-2u}\), \(u>0\), și \(f_V(v)=c_a\,b(v)=3e^{-3v}\), \(v>0\): \(U\sim\Exp(2)\) și \(V\sim\Exp(3)\). Felul în care împărțim constanta \(6\) între cei doi factori nu contează (puteam lua \(a(u)=6e^{-2u}\) și \(b(v)=e^{-3v}\) pe semiaxele pozitive): constantele \(c_a\) și \(c_b\) refac normarea. Independența a fost citită direct din forma de produs a densității, iar densitățile marginale au rezultat din factori, până la o constantă — acesta este avantajul lemei.

Factorizarea trebuie să aibă loc pentru orice \((u,v)\), inclusiv în afara suportului: dacă suportul densității comune nu este un produs cartezian, componentele nu sunt independente. De exemplu, pentru densitatea \(f(u,v)=2\,\Ind_{\{0<u<v<1\}}\), marginalele sunt \(f_U(u)=\int_u^12\dd v=2(1-u)\) și \(f_V(v)=\int_0^v2\dd u=2v\) pe \((0,1)\), iar \(f_U(u)f_V(v)=4(1-u)v\ne f(u,v)\); direct: \(\PP(U>\frac12,\ V<\frac12)=0\), în timp ce \(\PP(U>\frac12)\,\PP(V<\frac12)=\frac14\cdot\frac14>0\).

5.2 Repartiția normală: metoda Box–Muller

Funcția cuantilă \(\Phi^{-1}\) a repartiției normale nu are o expresie elementară. Metoda următoare produce, fără \(\Phi^{-1}\), două variabile normale standard independente din două uniforme independente, printr-o trecere la coordonate polare.

Teorema 11 (Metoda Box–Muller)

Fie \(U_1,U_2\) independente, repartizate \(\Unif(0,1)\), și \[ X_1=\sqrt{-2\ln U_2}\,\cos(2\pi U_1),\qquad X_2=\sqrt{-2\ln U_2}\,\sin(2\pi U_1). \] Atunci \(X_1\) și \(X_2\) sunt independente și repartizate \(\Norm(0,1)\).

Demonstrație. Ideea demonstrației. Perechea \((X_1,X_2)\) este scrisă în coordonate polare, cu raza \(R=\sqrt{-2\ln U_2}\) și unghiul \(\Theta=2\pi U_1\), independente. Calculăm densitatea lui \((R,\Theta)\) și trecem la coordonate carteziene cu Teorema schimbării de variabilă: iacobianul \(1/r\) simplifică factorul \(r\) din densitatea razei și rămâne \(\frac{1}{2\pi}e^{-(x_1^2+x_2^2)/2}=\phi(x_1)\phi(x_2)\), un produs de funcții de câte o coordonată; criteriul de factorizare dă independența și repartițiile.

Pasul 1: raza și unghiul. Fie \(R=\sqrt{-2\ln U_2}\) și \(\Theta=2\pi U_1\) (cum \(\PP(0<U_2<1)=1\), avem \(-2\ln U_2>0\) a.s., deci \(R\) este bine definită și strict pozitivă a.s.). Ele sunt independente, fiind funcții de \(U_2\), respectiv \(U_1\) (Propoziția 39 din Cursul 1). Unghiul \(\Theta\sim\Unif(0,2\pi)\) (Propoziția 4 cu \(d=1\)), cu densitatea \(\frac{1}{2\pi}\Ind_{(0,2\pi)}\). Pentru \(r>0\), aplicând funcția strict crescătoare \(\exp\) inegalității \(\ln U_2\ge-\frac{r^2}{2}\), \[ \PP(R\le r)=\PP\big(-2\ln U_2\le r^2\big)=\PP\big(U_2\ge e^{-r^2/2}\big)=1-e^{-r^2/2}, \] iar \(\PP(R\le r)=0\) pentru \(r\le0\). Derivând, \(R\) are densitatea \(f_R(r)=re^{-r^2/2}\), \(r>0\) (repartiția Rayleigh cu \(\theta=1\) din Tabelul 1). Din independență și Propoziția 38 din Cursul 1, \((R,\Theta)\) are densitatea \[ f_{(R,\Theta)}(r,\theta)=\frac{1}{2\pi}\,re^{-r^2/2}\qquad\text{pe }\Delta=(0,\infty)\times(0,2\pi), \] și \(0\) în rest; în particular \(\PP\big((R,\Theta)\in\Delta\big)=1\).

Pasul 2: trecerea la coordonate carteziene. Funcția \(g(r,\theta)=(r\cos\theta,r\sin\theta)\) este de clasă \(C^1\) pe mulțimea deschisă \(\Delta\) și este injectivă, cu imaginea \(g(\Delta)=\R^2\setminus\{(x,0):\ x\ge0\}\): orice punct din afara semiaxei \(\{(x,0):\ x\ge0\}\) se scrie în mod unic sub forma \((r\cos\theta,r\sin\theta)\) cu \(r>0\) și \(\theta\in(0,2\pi)\) (unghiul \(\theta=0\) corespunde tocmai semiaxei eliminate). Iacobianul ei este \[ J_{g}(r,\theta)=\det\begin{pmatrix}\cos\theta&-r\sin\theta\\ \sin\theta&r\cos\theta\end{pmatrix}=r\cos^2\theta+r\sin^2\theta=r>0 . \] Ipotezele Teoremei 52 din Cursul 1 sunt deci îndeplinite pentru vectorul \((R,\Theta)\), cu \(S=\Delta\) și \(h=g\). Inversa \(g^{-1}\) asociază punctului \((x_1,x_2)\in g(\Delta)\) raza \(r=\sqrt{x_1^2+x_2^2}\) și unghiul corespunzător, iar \(|J_{g^{-1}}(x_1,x_2)|=\frac{1}{J_g(g^{-1}(x_1,x_2))}=\frac1r\). Din (7), vectorul \((X_1,X_2)=g(R,\Theta)\) are densitatea \[ \begin{aligned} f_{X_1,X_2}(x_1,x_2)&=f_{(R,\Theta)}\big(g^{-1}(x_1,x_2)\big)\,\big|J_{g^{-1}}(x_1,x_2)\big|=\frac{1}{2\pi}\,r\,e^{-r^2/2}\cdot\frac1r\Big|_{r^2=x_1^2+x_2^2}\\ &=\frac{1}{2\pi}e^{-(x_1^2+x_2^2)/2}=\frac{1}{\sqrt{2\pi}}e^{-x_1^2/2}\cdot\frac{1}{\sqrt{2\pi}}e^{-x_2^2/2}=\phi(x_1)\,\phi(x_2) \end{aligned} \] pentru \((x_1,x_2)\in g(\Delta)\) și \(0\) pe semiaxa \(\{(x,0):\ x\ge0\}\). Semiaxa are aria nulă, deci modificarea densității pe ea nu schimbă nicio probabilitate: \((X_1,X_2)\) are și densitatea \(\phi(x_1)\phi(x_2)\), \((x_1,x_2)\in\R^2\).

Pasul 3: concluzia. Densitatea comună este de forma \(a(x_1)\,b(x_2)\) pentru orice \((x_1,x_2)\in\R^2\), cu \(a=b=\phi\). Din Lema 10, \(X_1\) și \(X_2\) sunt independente, cu densitățile \(c_b\,a\) și \(c_a\,b\); cum \(c_a=c_b=\int_{\R}\phi(x)\dd x=1\), ambele au densitatea \(\phi\), adică sunt repartizate \(\Norm(0,1)\).■

Independența lui \(X_1\) și \(X_2\) este remarcabilă: ele sunt construite din aceleași două uniforme și sunt legate prin \(X_1^2+X_2^2=R^2\). Explicația este invarianța la rotații a densității \(\phi(x_1)\phi(x_2)\), care depinde doar de distanța la origine. Metoda produce două normale din două uniforme, fără a evalua \(\Phi^{-1}\), dar cu funcții trigonometrice, relativ costisitoare. Metoda polară a lui Marsaglia le evită, combinând Box–Muller cu metoda respingerii: pornește de la un punct \((V_1,V_2)\) uniform pe discul unitate (Exemplul 12) și întoarce \(V_1\sqrt{-2\ln(S)/S}\) și \(V_2\sqrt{-2\ln(S)/S}\), cu \(S=V_1^2+V_2^2\), care sunt tot două normale standard independente (Devroye 1986, cap. V). Odată simulată \(Z\sim\Norm(0,1)\), variabila \(\mu+\sigma Z\) este repartizată \(\Norm(\mu,\sigma^2)\) (Propoziția 18 din Cursul 1).

Exemplul 17 (Metoda Box–Muller, calculată de mână)

Fie \(u_1=0.37\) și \(u_2=0.82\) două valori produse de generator.

Raza. \(-2\ln u_2=-2\ln0.82\approx0.3969\), deci \(r=\sqrt{0.3969}\approx0.6300\).

Unghiul. \(\theta=2\pi u_1\approx2.3248\) radiani, adică \(0.37\cdot360^\circ=133.2^\circ\) (în cadranul al doilea), cu \(\cos\theta\approx-0.6845\) și \(\sin\theta\approx0.7290\).

Cele două valori. \(x_1=r\cos\theta\approx0.6300\cdot(-0.6845)\approx-0.431\) și \(x_2=r\sin\theta\approx0.6300\cdot0.7290\approx0.459\). Verificare: \(x_1^2+x_2^2\approx0.186+0.211=0.397=r^2\).

Din două uniforme am obținut două observații independente din \(\Norm(0,1)\). Pentru o observație din \(\Norm(10,4)\), cu \(\mu=10\) și \(\sigma=2\), luăm \(10+2x_1\approx9.137\).

Cum citim construcția. Numărul \(u_1\) hotărăște doar direcția punctului \((x_1,x_2)\), iar \(u_2\) doar distanța lui la origine: valorile lui \(u_2\) apropiate de \(1\) dau puncte apropiate de origine, iar cele apropiate de \(0\) dau puncte îndepărtate (de exemplu, \(r=3\) corespunde lui \(u_2=e^{-4.5}\approx0.011\)). Pătratul razei, \(R^2=-2\ln U_2\), este repartizat \(\Exp(\frac12)\) (Exemplul 7 cu \(\lambda=\frac12\)), în acord cu un rezultat pe care îl demonstrăm mai jos (Propoziția 12(b), cu \(k=2\)): suma pătratelor a două variabile normale standard independente, aici \(X_1^2+X_2^2\), este repartizată \(\GammaD(1,\frac12)=\Exp(\frac12)\).

box_muller <- function(n) {
  m <- ceiling(n / 2)
  r <- sqrt(-2 * log(runif(m))); t <- 2 * pi * runif(m)   # raza și unghiul
  c(r * cos(t), r * sin(t))[1:n]            # primele m: X1, ultimele m: X2
}
set.seed(16)
x <- box_muller(1e5)
rbind(BoxMuller = c(media = mean(x), var = var(x),
                    quantile(x, c(0.025, 0.975))),
      teoretic  = c(0, 1, qnorm(c(0.025, 0.975))))
#>                media    var   2.5% 97.5%
#> BoxMuller -0.0008978 0.9958 -1.958 1.955
#> teoretic   0.0000000 1.0000 -1.960 1.960
cor(x[1:50000], x[50001:1e5])   # perechile (X1, X2): corelație ≈ 0
#> [1] -0.001982

Eșantionul simulat reproduce media \(0\), varianța \(1\) și cuantilele \(\pm1.96\) ale repartiției \(\Norm(0,1)\), iar corelația empirică a perechilor \((X_1,X_2)\) este practic nulă.

5.3 Repartițiile Gamma, \(\chi^2\) și binomială

Alte repartiții uzuale se obțin ca sume de variabile independente pe care știm deja să le simulăm; repartiția sumei se identifică prin funcția generatoare de momente.

Propoziția 12 (Gamma cu parametru întreg, chi-pătrat, binomială)

Fie \(U_1,U_2,\dots\) independente \(\Unif(0,1)\) și \(Z_1,Z_2,\dots\) independente \(\Norm(0,1)\).

  1. Pentru \(n\in\N^*\) și \(\lambda>0\), \(-\frac1\lambda\ln(U_1U_2\cdots U_n)\sim\GammaD(n,\lambda)\).

  2. Pentru \(k\in\N^*\), \(Z_1^2+\dots+Z_k^2\sim\GammaD\big(\frac k2,\frac12\big)\), repartiția numită \(\chi^2\) cu \(k\) grade de libertate (Cursul 5); în particular \(-2\ln(U_1\cdots U_\nu)\sim\GammaD(\nu,\frac12)=\chi^2_{2\nu}\).

  3. Pentru \(m\in\N^*\) și \(p\in(0,1)\), \(\sum_{i=1}^m\Ind_{\{U_i<p\}}\sim\Bin(m,p)\).

Demonstrație. În fiecare caz variabila construită este o sumă de variabile independente (funcții de variabile independente, Propoziția 39 din Cursul 1); f.g.m. a sumei este produsul f.g.m. ale termenilor (Propoziția 46 din Cursul 1), iar o f.g.m. finită pe o vecinătate a lui \(0\) determină repartiția (Teorema 33 din Cursul 1).

  1. Logaritmul produsului este suma logaritmilor, deci \(-\frac1\lambda\ln(U_1\cdots U_n)=\sum_{i=1}^nE_i\), cu \(E_i=-\frac1\lambda\ln U_i\sim\Exp(\lambda)\) (Exemplul 7), iar suma a \(n\) variabile \(\Exp(\lambda)\) independente are repartiția \(\GammaD(n,\lambda)\) (Exemplul 31 din Cursul 1).

  2. Din Exemplul 9 din Cursul 1, \(Z_i^2\sim\GammaD(\frac12,\frac12)\), cu f.g.m. \(\big(\frac{1/2}{1/2-t}\big)^{1/2}=(1-2t)^{-1/2}\), \(t<\frac12\) (Exemplul 21 din Cursul 1). Deci \[ M_{Z_1^2+\dots+Z_k^2}(t)=\prod_{i=1}^k(1-2t)^{-1/2}=(1-2t)^{-k/2}=\Big(\frac{1/2}{1/2-t}\Big)^{k/2},\qquad t<\frac12 , \] f.g.m. a repartiției \(\GammaD(\frac k2,\frac12)\). Afirmația despre \(-2\ln(U_1\cdots U_\nu)\) este punctul (a) cu \(n=\nu\) și \(\lambda=\frac12\).

  3. Variabilele \(B_i=\Ind_{\{U_i<p\}}\) sunt independente și repartizate \(\Bern(p)\), deoarece \(\PP(B_i=1)=\PP(U_i<p)=p\), cu f.g.m. \(M_{B_i}(t)=1-p+pe^t\), \(t\in\R\). Din binomul lui Newton, \[ M_{B_1+\dots+B_m}(t)=(1-p+pe^t)^m=\sum_{k=0}^me^{tk}\binom mkp^k(1-p)^{m-k},\qquad t\in\R , \] iar ultima sumă este \(\E[e^{tY}]\) pentru \(Y\sim\Bin(m,p)\).

■

Exemplul 18 (Gamma, chi-pătrat și binomială din uniforme: calcule numerice)

Folosim cinci valori produse de generator: \(u_1=0.37\), \(u_2=0.82\), \(u_3=0.55\), \(u_4=0.12\), \(u_5=0.25\).

O observație din \(\GammaD(3,2)\) (punctul (a), cu \(n=3\), \(\lambda=2\)). Produsul primelor trei valori este \(u_1u_2u_3=0.37\cdot0.82\cdot0.55\approx0.1669\), deci \(x=-\frac12\ln0.1669\approx0.895\). Același număr se obține adunând trei observații \(\Exp(2)\) simulate prin metoda inversă: \(-\frac12\ln0.37\approx0.497\), \(-\frac12\ln0.82\approx0.099\) și \(-\frac12\ln0.55\approx0.299\), cu suma \(0.895\); forma cu produsul evaluează un singur logaritm în loc de trei. Pentru orientare, \(\E[X]=\frac n\lambda=1.5\) și \(\Var(X)=\frac{n}{\lambda^2}=0.75\).

O observație din \(\chi^2_4\) (punctul (b)). Cu \(\nu=2\): \(-2\ln(u_1u_2)=-2\ln0.3034\approx2.385\). Alternativ, din patru valori normale standard, de exemplu \(z=(-0.43,\,0.46,\,1.20,\,-0.70)\), obținem \(z_1^2+\dots+z_4^2=0.1849+0.2116+1.44+0.49\approx2.327\): alt număr, dar din aceeași repartiție \(\chi^2_4\), de medie \(4\). Prima variantă costă două uniforme, a doua patru normale. Pentru un număr impar de grade de libertate este nevoie de un pătrat de normală: de exemplu, dacă \(Z\sim\Norm(0,1)\) este independentă de \(U_1,U_2\), atunci \(-2\ln(U_1U_2)+Z^2\sim\chi^2_5\), deoarece f.g.m. a sumei este \((1-2t)^{-2}(1-2t)^{-1/2}=(1-2t)^{-5/2}\), \(t<\frac12\).

O observație din \(\Bin(5,0.3)\) (punctul (c)). Indicatorii \(\Ind_{\{u_i<0.3\}}\) sunt, în ordine, \(0,0,0,1,1\) (doar \(u_4=0.12\) și \(u_5=0.25\) sunt sub \(0.3\)), deci \(x=2\). Costul este de \(m=5\) uniforme pe observație; metoda inversă din Exemplul 6 folosește o singură uniformă și, în medie, \(1+mp=2.5\) comparații, deci devine mai economică atunci când \(m\) este mare.

Metoda (a) costă \(n\) uniforme pe observație; pentru parametru de formă neîntreg se folosesc metode de respingere (Devroye 1986; Robert and Casella 2004) (în R, rgamma). Repartițiile Student și Fisher–Snedecor, definite prin normale și \(\chi^2\) independente, se simulează tot prin transformări și sunt studiate în Cursul 5.

Tabelul 2 rezumă cele trei familii de metode din acest curs.

Tabelul 2: Metode de simulare: condiții de aplicare și exemple.
Metoda Ce trebuie să cunoaștem Cost pe observație Exemple
inversă (continuu) \(F^{-1}\) explicit o uniformă exponențială, Weibull, Cauchy, Pareto
inversă (discret) \(p_k\) (eventual recurent) o uniformă + căutare Bernoulli, geometrică, Poisson
respingere \(f\le cg\) (\(f\) până la o constantă), simulare din \(g\) în medie \(c\) propuneri Beta, normală, uniforma pe o mulțime
transformări o caracterizare a repartiției fix Box–Muller, Gamma, \(\chi^2\), binomială

6 Exerciții rezolvate

Exercițiul 1 (Integrare Monte Carlo și volumul simulării)

Fie \(I=\int_0^1\sin(\sqrt x)\dd x\). (a) Propuneți un estimator Monte Carlo \(I_n\) al lui \(I\) și calculați valoarea exactă a integralei. (b) Calculați varianța \(\sigma^2\) a lui \(\sin\sqrt U\). (c) Determinați volumul \(n\) pentru care \(\PP(|I_n-I|\ge0.01)\le0.01\) (aproximativ, prin TLC) și comparați-l cu volumul dat de inegalitatea lui Cebîșev.

Soluție

Ce se cere și ce folosim. La (a) scriem integrala ca medie a unei funcții de o variabilă uniformă și aplicăm Propoziția 1; valoarea exactă se obține printr-o schimbare de variabilă și o integrare prin părți. La (b) calculăm \(\E[\sin^2\sqrt U]\) în același fel și folosim \(\Var(Y)=\E[Y^2]-(\E[Y])^2\). La (c) traducem cerința în limbajul TLC (relația (3)), respectiv al inegalității lui Cebîșev.

  1. Densitatea lui \(U\sim\Unif(0,1)\) este \(\Ind_{[0,1]}\), deci, din formula de transport (Teorema 22 din Cursul 1), \(I=\int_0^1\sin(\sqrt x)\dd x=\E[\sin\sqrt U]\). Pentru \(U_1,U_2,\dots\) i.i.d. \(\Unif(0,1)\), estimatorul \(I_n=\frac1n\sum_{i=1}^n\sin\sqrt{U_i}\) este nedeplasat și consistent tare (Propoziția 1; ipotezele sunt îndeplinite, deoarece \(0\le\sin\sqrt U\le1\), deci toate momentele sunt finite). Pentru valoarea exactă schimbăm variabila \(x=t^2\), \(\dd x=2t\dd t\) (limitele \(x=0\), \(x=1\) devin \(t=0\), \(t=1\)) și integrăm prin părți, cu \(u=t\), \(v'=\sin t\), deci \(u'=1\), \(v=-\cos t\): \[ \begin{aligned} I&=\int_0^1\sin(t)\,2t\dd t=2\Big(\big[-t\cos t\big]_0^1+\int_0^1\cos t\dd t\Big)=2\big(-\cos1+\sin1\big)\\ &=2(\sin1-\cos1)\approx0.6023 . \end{aligned} \] Numeric (argumentele sunt în radiani): \(\sin1\approx0.8415\) și \(\cos1\approx0.5403\), deci \(I=2(\sin1-\cos1)\approx0.6023\).

  2. Avem nevoie de momentul de ordinul doi al variabilei \(Y=\sin\sqrt U\). Cu aceeași schimbare de variabilă și cu \(\sin^2t=\frac{1-\cos2t}{2}\), \[ \begin{aligned} \E\big[\sin^2\sqrt U\big]&=\int_0^1\sin^2(\sqrt x)\dd x=\int_0^12t\sin^2t\dd t\\ &=\int_0^1t(1-\cos2t)\dd t=\frac12-\int_0^1t\cos2t\dd t . \end{aligned} \] Ultima integrală se calculează prin părți, cu \(u=t\), \(v'=\cos2t\), deci \(u'=1\), \(v=\frac{\sin2t}{2}\): \[ \int_0^1t\cos2t\dd t=\Big[\frac{t\sin2t}{2}\Big]_0^1-\int_0^1\frac{\sin2t}{2}\dd t=\frac{\sin2}{2}+\Big[\frac{\cos2t}{4}\Big]_0^1=\frac{\sin2}{2}+\frac{\cos2}{4}-\frac14 . \] Prin urmare \[ \E\big[\sin^2\sqrt U\big]=\frac12-\Big(\frac{\sin2}{2}+\frac{\cos2}{4}-\frac14\Big)=\frac34-\frac{\sin2}{2}-\frac{\cos2}{4}\approx0.39939 , \] unde am folosit \(\sin2\approx0.9093\) și \(\cos2\approx-0.4161\), adică \(0.75-0.4546+0.1040\). Prin urmare \(\sigma^2=\E[\sin^2\sqrt U]-I^2\approx0.39939-0.60234^2\approx0.03658\) și \(\sigma\approx0.1913\). Abaterea standard a unui singur termen este deci aproximativ o treime din valoarea integralei; eroarea estimatorului \(I_n\) va fi \(\sigma/\sqrt n\).

  3. Căutăm cel mai mic \(n\) pentru care abaterea \(|I_n-I|\) depășește \(0.01\) cu probabilitate cel mult \(0.01\). Fie \(Z\sim\Norm(0,1)\). Din TLC (Propoziția 1), \(\sqrt n(I_n-I)/\sigma\) este aproximativ \(\Norm(0,1)\), deci, împărțind inegalitatea \(|I_n-I|\ge0.01\) la \(\sigma/\sqrt n\), \[ \begin{aligned} \PP(|I_n-I|\ge0.01)&=\PP\Big(\frac{\sqrt n\,|I_n-I|}{\sigma}\ge\frac{0.01\sqrt n}{\sigma}\Big)\approx\PP\Big(|Z|\ge\frac{0.01\sqrt n}{\sigma}\Big)\\ &=2\Big(1-\Phi\Big(\frac{0.01\sqrt n}{\sigma}\Big)\Big), \end{aligned} \] iar aceasta este \(\le0.01\) dacă și numai dacă \(\Phi(0.01\sqrt n/\sigma)\ge0.995\), adică \(0.01\sqrt n/\sigma\ge z_{0.995}=2.5758\) (\(\Phi\) este strict crescătoare): \[ n\ge\Big(\frac{2.5758\,\sigma}{0.01}\Big)^2=(257.58\cdot0.19125)^2\approx2426.9,\qquad\text{deci } n=2427 . \] Aproximarea normală cere deci \(n=2427\); este relația (3) cu \(\alpha=0.01\) și \(\varepsilon=0.01\). Verificare: pentru \(n=2427\) eroarea standard este \(\sigma/\sqrt n\approx0.19125/49.26\approx0.00388\), iar \(2.5758\cdot0.00388\approx0.0100\), exact pragul cerut.

    Inegalitatea lui Cebîșev (Propoziția 26 din Cursul 1), aplicată lui \(I_n\), cu \(\E[I_n]=I\) și \(\Var(I_n)=\sigma^2/n\), dă, fără aproximații, \[ \PP(|I_n-I|\ge0.01)\le\frac{\Var(I_n)}{0.01^2}=\frac{\sigma^2}{10^{-4}\,n}, \] iar \(\frac{\sigma^2}{10^{-4}\,n}\le0.01\iff n\ge10^6\sigma^2\approx36578\): inegalitatea lui Cebîșev cere \(n\ge36578\), o margine garantată, dar de aproximativ \(36578/2427\approx15\) ori mai pesimistă decât cea obținută din aproximarea normală. Factorul nu depinde de integrală: în general, cele două volume sunt \(n_{\mathrm{Ceb}}=\frac{\sigma^2}{\alpha\varepsilon^2}\) și \(n_{\mathrm{TLC}}=\frac{z_{1-\alpha/2}^2\sigma^2}{\varepsilon^2}\), cu raportul \(\frac{1}{\alpha z_{1-\alpha/2}^2}=\frac{1}{0.01\cdot2.5758^2}\approx15.1\) pentru \(\alpha=0.01\). Inegalitatea lui Cebîșev este valabilă pentru orice repartiție cu varianța dată, de aceea este prudentă; aproximarea normală folosește forma repartiției lui \(I_n\), cunoscută (asimptotic) din TLC. În practică, \(\sigma\) fiind necunoscut, l-am estima dintr-o simulare-pilot și am folosi volumul dat de aproximarea normală.

Exercițiul 2 (Simularea repartiției din coadă)

Fie \(X\) cu funcția de repartiție \(F\) continuă și strict crescătoare și \(a\in\R\) cu \(F(a)<1\). Vrem să simulăm repartiția condiționată \(\mathcal{L}(X\mid X>a)\). (a) Descrieți metoda respingerii și numărul mediu de încercări; ce se întâmplă pentru \(X\sim\Exp(1)\), \(a=4\), respectiv \(X\sim\Norm(0,1)\), \(a=5\)? (b) Fie \(U\sim\Unif(0,1)\) și \(T=F^{-1}\big(F(a)+(1-F(a))U\big)\). Determinați repartiția lui \(T\). Care metodă este de preferat? (c) Aplicați (b) pentru \(X\sim\Exp(\lambda)\).

Soluție

Ce se cere și ce folosim. Ținta este repartiția lui \(X\) condiționată de evenimentul \(\{X>a\}\). La (a) aplicăm direct teorema despre simularea repartiției condiționate prin respingere; la (b) calculăm funcția de repartiție a lui \(T\) cu lema fundamentală a funcției cuantilă și o comparăm cu cea a repartiției condiționate; (c) este un caz particular în care totul se calculează explicit.

  1. Generăm \(X_1,X_2,\dots\) independente, cu repartiția \(\mu\) a lui \(X\), până la primul \(T\) cu \(X_T>a\). Teorema 5 cu \(B=(a,\infty)\), \(\mu(B)=1-F(a)>0\), dă \(X_T\sim\mu(\cdot\mid B)=\mathcal{L}(X\mid X>a)\) și \(T\sim\Geom(1-F(a))\), cu \(\E[T]=\frac{1}{1-F(a)}\). Pentru \(\Exp(1)\) și \(a=4\): \(1-F(4)=e^{-4}\approx0.0183\), deci \(\E[T]=e^4\approx54.6\) încercări pentru o singură observație. Pentru \(\Norm(0,1)\) și \(a=5\): \(1-F(5)=\Phi(-5)\approx2.87\cdot10^{-7}\), deci \(\E[T]=1/\Phi(-5)\approx3.5\cdot10^6\); un eșantion de \(1000\) de observații din coadă ar cere în medie \(3.5\cdot10^9\) variabile normale. Metoda este corectă, dar devine impracticabilă departe în coadă: aproape toate observațiile generate sunt aruncate.

  2. Ideea: în loc să generăm ordinul cuantilei uniform pe \((0,1)\) și să aruncăm valorile care dau \(X\le a\), îl generăm direct uniform pe \((F(a),1)\), adică în zona care corespunde valorilor mai mari decât \(a\). Variabila \(V=F(a)+(1-F(a))U\) este o funcție afină strict crescătoare de \(U\), deci este uniformă pe \((F(a),1)\) (Propoziția 4 cu \(d=1\)); în particular \(V\in(0,1)\) a.s., iar \(T=F^{-1}(V)\) este bine definită. Din Lema 8 din Cursul 3, \(\{T\le t\}=\{F^{-1}(V)\le t\}=\{V\le F(t)\}\) pentru orice \(t\in\R\). Pentru \(t<a\), \(F(t)\le F(a)<V\) a.s., deci \(\PP(T\le t)=0\). Pentru \(t\ge a\), scăzând \(F(a)\) și împărțind la \(1-F(a)>0\), \[ \PP(T\le t)=\PP\big(F(a)+(1-F(a))U\le F(t)\big)=\PP\Big(U\le\frac{F(t)-F(a)}{1-F(a)}\Big)=\frac{F(t)-F(a)}{1-F(a)}, \] deoarece \(\frac{F(t)-F(a)}{1-F(a)}\in[0,1]\). Pe de altă parte, din definiția probabilității condiționate, pentru \(t\ge a\), \[ \PP(X\le t\mid X>a)=\frac{\PP(a<X\le t)}{\PP(X>a)}=\frac{F(t)-F(a)}{1-F(a)}, \] iar pentru \(t<a\) această probabilitate este \(0\). Cele două funcții de repartiție coincid, deci \(T\sim\mathcal{L}(X\mid X>a)\). Metoda folosește o singură uniformă pe observație, oricât de mare ar fi \(a\), și este de preferat ori de câte ori \(F\) și \(F^{-1}\) se calculează precis; respingerea rămâne utilă când știm să simulăm \(X\), dar nu cunoaștem \(F\), iar \(\PP(X>a)\) nu este prea mică.

  3. Raționamentul de la (b) a folosit doar Lema 8 din Cursul 3 și \(F(a)<1\), deci se aplică și aici, deși \(F\) este strict crescătoare numai pe \((0,\infty)\). Pentru \(\Exp(\lambda)\) și \(a>0\): \(F(a)=1-e^{-\lambda a}\) și \(F^{-1}(v)=-\frac1\lambda\ln(1-v)\) (Exemplul 7). Atunci \[ 1-V=\big(1-F(a)\big)-\big(1-F(a)\big)U=\big(1-F(a)\big)(1-U)=e^{-\lambda a}(1-U), \] deci \[ T=-\frac1\lambda\ln(1-V)=-\frac1\lambda\Big(-\lambda a+\ln(1-U)\Big)=a-\frac1\lambda\ln(1-U). \] Cum \(-\frac1\lambda\ln(1-U)\sim\Exp(\lambda)\), obținem \(\mathcal{L}(X\mid X>a)=\mathcal{L}(a+X)\): condiționat de depășirea pragului \(a\), excesul \(X-a\) este din nou \(\Exp(\lambda)\) — proprietatea de lipsă de memorie.

    Un calcul numeric. Pentru \(\lambda=1\), \(a=4\) și \(u=0.37\): \(F(4)=1-e^{-4}\approx0.98168\), \(v=F(4)+(1-F(4))u\approx0.98168+0.01832\cdot0.37\approx0.98846\) și \(t=-\ln(1-v)=-\ln0.01154\approx4.462\); direct, \(t=4-\ln(1-0.37)=4-\ln0.63\approx4+0.462\). O singură uniformă a produs o observație din coadă, în locul celor \(54.6\) exponențiale necesare în medie la punctul (a).

Exercițiul 3 (Normala trunchiată)

Repartiția \(\Norm(0,1)\) trunchiată la \([b,\infty)\), \(b>0\), are densitatea \(f(x)=\frac{\phi(x)}{\Phi(-b)}\Ind_{\{x\ge b\}}\), proporțională cu \(f_1(x)=e^{-x^2/2}\Ind_{\{x\ge b\}}\); este repartiția unei variabile \(Z\sim\Norm(0,1)\) condiționate de \(\{Z\ge b\}\).

  1. Care este probabilitatea de acceptare a respingerii cu propunere \(\Norm(0,1)\)?

  2. Pentru propunerea \(g_\lambda(x)=\lambda e^{-\lambda(x-b)}\Ind_{\{x\ge b\}}\), \(\lambda>0\), determinați \(M(\lambda)=\sup_xf_1(x)/g_\lambda(x)\), valoarea optimă \(\lambda^*\) și algoritmul.

  3. Verificați, pentru \(b=3\), media \(\E[Z\mid Z\ge b]=\phi(b)/\Phi(-b)\).

Soluție

Ce se cere și ce folosim. La (a) recunoaștem ținta ca repartiție condiționată și aplicăm Exercițiul 2. La (b) parcurgem pașii metodei respingerii pentru o țintă cunoscută până la o constantă: raportul \(f_1/g_\lambda\), supremumul \(M(\lambda)\), minimizarea în \(\lambda\), condiția de acceptare și probabilitatea de acceptare \(K/M\) (observația despre densitățile nenormalizate). La (c) calculăm media exactă și o comparăm cu media unui eșantion simulat.

  1. Pentru \(Z\sim\Norm(0,1)\) și \(A\) borelian, \(\int_Af(x)\dd x=\frac{\PP(Z\in A,\ Z\ge b)}{\PP(Z\ge b)}\), cu \(\PP(Z\ge b)=1-\Phi(b)=\Phi(-b)\): ținta este repartiția lui \(Z\) condiționată de \(\{Z\ge b\}\). Din Exercițiul 2(a) (Teorema 5 cu \(B=[b,\infty)\)), generăm \(Z_1,Z_2,\dots\) i.i.d. \(\Norm(0,1)\) până la primul \(Z_n\ge b\), iar probabilitatea de acceptare este \(\mu(B)=\Phi(-b)\): \(0.0228\) pentru \(b=2\) și \(2.9\cdot10^{-7}\) pentru \(b=5\) — metoda este inutilizabilă pentru \(b\) mare.

  2. Raportul. Pentru \(x\ge b\), \[ \frac{f_1(x)}{g_\lambda(x)}=\frac{e^{-x^2/2}}{\lambda e^{-\lambda(x-b)}}=\frac1\lambda\,e^{-\lambda b}\,e^{\psi(x)},\qquad\psi(x)=-\frac{x^2}{2}+\lambda x , \] iar \(\psi\) este o parabolă concavă, cu \(\psi'(x)=\lambda-x\): crește pe \((-\infty,\lambda]\) și descrește pe \([\lambda,\infty)\). Supremumul pe \([b,\infty)\) depinde de poziția lui \(\lambda\) față de \(b\):

  • dacă \(\lambda\ge b\), maximul lui \(\psi\) pe \([b,\infty)\) este \(\psi(\lambda)=\frac{\lambda^2}{2}\) și \(M(\lambda)=\frac1\lambda e^{\lambda^2/2-\lambda b}\);
  • dacă \(\lambda<b\), \(\psi\) este descrescătoare pe \([b,\infty)\), maximul este \(\psi(b)=-\frac{b^2}{2}+\lambda b\) și \(M(\lambda)=\frac1\lambda e^{-\lambda b}e^{-b^2/2+\lambda b}=\frac1\lambda e^{-b^2/2}\).

Minimizarea lui \(M\). Pe ramura \(\lambda<b\), \(M(\lambda)=\frac1\lambda e^{-b^2/2}\) este strict descrescătoare, cu limita \(\frac1be^{-b^2/2}=M(b)\) când \(\lambda\nearrow b\) (cele două formule coincid în \(\lambda=b\)) — deci \(M(\lambda)>M(b)\) pentru \(\lambda<b\), iar minimul nu se atinge pe această ramură. Pe ramura \(\lambda\ge b\), \(\ln M(\lambda)=-\ln\lambda+\frac{\lambda^2}{2}-\lambda b\), cu \[ \frac{\dd}{\dd\lambda}\ln M(\lambda)=-\frac1\lambda+\lambda-b=\frac{\lambda^2-b\lambda-1}{\lambda},\qquad \frac{\dd^2}{\dd\lambda^2}\ln M(\lambda)=\frac{1}{\lambda^2}+1>0 . \] Trinomul \(\lambda^2-b\lambda-1\) are rădăcinile \(\frac{b\pm\sqrt{b^2+4}}{2}\), dintre care doar \(\lambda^*=\frac{b+\sqrt{b^2+4}}{2}\) este pozitivă; cum \(\sqrt{b^2+4}>b\), avem \(\lambda^*>b\). Derivata lui \(\ln M\) este negativă pe \([b,\lambda^*)\) (în \(\lambda=b\) ea este \(-\frac1b<0\)) și pozitivă pe \((\lambda^*,\infty)\), deci minimul global al lui \(M\) pe \((0,\infty)\) se atinge în \(\lambda^*\).

Algoritmul. Propunerea \(g_{\lambda^*}\) este densitatea lui \(b+E\), cu \(E\sim\Exp(\lambda^*)\) (o exponențială translatată în \(b\)), deci se simulează prin \(X=b-\frac{1}{\lambda^*}\ln U_1\) (metoda inversă, Exemplul 7). Generăm \(U_2\sim\Unif(0,1)\) independentă de \(U_1\) și, înlocuind \(M(\lambda^*)=\frac{1}{\lambda^*}e^{\lambda^{*2}/2-\lambda^*b}\) (ramura \(\lambda\ge b\)), acceptăm dacă \[ U_2\le\frac{f_1(X)}{M(\lambda^*)g_{\lambda^*}(X)}=\frac{e^{-X^2/2}}{\frac{1}{\lambda^*}e^{\lambda^{*2}/2-\lambda^*b}\cdot\lambda^*e^{-\lambda^*(X-b)}}=e^{-\frac{X^2}{2}+\lambda^*X-\frac{\lambda^{*2}}{2}}=e^{-(X-\lambda^*)^2/2}. \] Altfel reluăm cu o pereche nouă. Este aceeași formă ca în Exemplul 15: propunerea \(x\) este acceptată cu probabilitatea \(e^{-(x-\lambda^*)^2/2}\), egală cu \(1\) în \(x=\lambda^*\). Pe scurt: \(M(\lambda)\) este minim pentru \(\lambda^*=\frac{b+\sqrt{b^2+4}}{2}\), cu \(M(\lambda^*)=\frac{1}{\lambda^*}e^{\lambda^{*2}/2-\lambda^*b}\); generăm \(X=b-\frac{1}{\lambda^*}\ln U_1\) și îl acceptăm dacă \(U_2\le e^{-(X-\lambda^*)^2/2}\).

Un calcul numeric pentru \(b=3\). \(\lambda^*=\frac{3+\sqrt{13}}{2}\approx3.3028\). Pentru \(u_1=0.37\): \(x=3-\frac{\ln0.37}{3.3028}\approx3+0.301=3.301\), practic egal cu \(\lambda^*\), deci acceptat aproape sigur (\(e^{-(3.301-3.3028)^2/2}\approx1.000\)). Pentru \(u_1=0.04\): \(x=3-\frac{\ln0.04}{3.3028}\approx3.975\), acceptat cu probabilitatea \(e^{-(3.975-3.3028)^2/2}=e^{-0.226}\approx0.798\).

Probabilitatea de acceptare. Ținta este nenormalizată: \(f_1=Kf\), cu \(K=\int_b^\infty e^{-x^2/2}\dd x=\sqrt{2\pi}\,\Phi(-b)\). Din observația despre densitățile nenormalizate, probabilitatea de acceptare este \(K/M(\lambda^*)\). Pentru \(b=3\): \(M(\lambda^*)=\frac{1}{3.3028}e^{5.4542-9.9083}=\frac{e^{-4.4541}}{3.3028}\approx\frac{0.011630}{3.3028}\approx0.003521\) și \(K=\sqrt{2\pi}\cdot\Phi(-3)\approx2.5066\cdot0.0013499\approx0.003384\), deci \(K/M(\lambda^*)\approx0.961\). La fel se obțin \(0.934\) pentru \(b=2\) și \(0.983\) pentru \(b=5\) — spre deosebire de (a), eficiența crește cu \(b\): departe în coadă, densitatea normală trunchiată seamănă tot mai mult cu o exponențială translatată. Pentru \(b=0\) regăsim \(\lambda^*=1\), \(M(1)=e^{1/2}\), \(K=\sqrt{2\pi}/2\) și acceptarea \(\sqrt{\pi/(2e)}\approx0.760\) din Exemplul 15.

  1. Media repartiției cu densitatea \(f\) este \(\int_b^\infty xf(x)\dd x\). Din \(\phi'(x)=-x\phi(x)\), funcția \(-\phi\) este o primitivă a lui \(x\phi(x)\), deci \(\E[Z\mid Z\ge b]=\frac{1}{\Phi(-b)}\int_b^\infty x\phi(x)\dd x=\frac{[-\phi(x)]_b^\infty}{\Phi(-b)}=\frac{\phi(b)}{\Phi(-b)}\). Pentru \(b=3\): \(\phi(3)\approx0.004432\) și \(\Phi(-3)\approx0.001350\), deci media este \(\approx3.283\) — observațiile din coadă sunt, în medie, foarte aproape de prag.

Codul de mai jos aplică algoritmul de la (b) pentru \(b=3\): generează \(m=10^5\) propuneri \(X=b-\ln U_1/\lambda^*\), păstrează valorile acceptate și afișează proporția de acceptări (de comparat cu \(K/M(\lambda^*)\)) și media valorilor acceptate (de comparat cu \(\phi(3)/\Phi(-3)\)).

set.seed(31)
b <- 3; lam <- (b + sqrt(b^2 + 4)) / 2; m <- 1e5
x <- b - log(runif(m)) / lam                        # propunerea g_lambda
z <- x[runif(m) <= exp(-(x - lam)^2 / 2)]           # acceptare
M <- exp(lam^2 / 2 - lam * b) / lam
c(acceptare = length(z) / m, teoretic = sqrt(2 * pi) * pnorm(-b) / M,
  media = mean(z), media_teoretica = dnorm(b) / pnorm(-b))
#>       acceptare        teoretic           media media_teoretica 
#>          0.9601          0.9609          3.2831          3.2831

Proporția de propuneri acceptate, \(0.9601\), este foarte apropiată de valoarea teoretică \(0.9609\), iar media celor aproximativ \(96000\) de valori acceptate, \(3.2831\), coincide la patru zecimale cu \(\phi(3)/\Phi(-3)\). Prin respingerea directă de la (a), aceleași \(10^5\) propuneri normale ar fi produs în medie doar \(10^5\cdot\Phi(-3)\approx135\) de observații.

Exercițiul 4 (Propunerea Cauchy pentru repartiția normală)

Pentru ținta \(\phi\) (densitatea \(\Norm(0,1)\)) și propunerea \(g(x)=\frac{1}{\pi(1+x^2)}\), determinați constanta optimă, probabilitatea de acceptare și condiția de acceptare; comparați cu propunerea Laplace din Exemplul 15.

Soluție

Ce se cere și ce folosim. Parcurgem pașii metodei respingerii (Teorema 9 și observația care îi urmează): calculăm raportul \(\phi/g\), îi determinăm supremumul \(c\) studiind semnul derivatei, scriem condiția de acceptare \(U\le\phi(X)/(cg(X))\) și citim probabilitatea de acceptare \(1/c\). Propunerea Cauchy se simulează prin metoda inversă (Exemplul 8) și are cozi mai grele decât ținta, deci raportul este mărginit.

Pasul 1: raportul. Pentru \(x\in\R\), \[ \frac{\phi(x)}{g(x)}=\frac{1}{\sqrt{2\pi}}e^{-x^2/2}\cdot\pi(1+x^2)=\sqrt{\frac\pi2}\,k(x),\qquad k(x)=(1+x^2)\,e^{-x^2/2}, \] deoarece \(\frac{\pi}{\sqrt{2\pi}}=\sqrt{\frac{\pi}{2}}\); funcția \(k\) este pară.

Pasul 2: supremumul. Derivând produsul, \[ k'(x)=2xe^{-x^2/2}-x(1+x^2)e^{-x^2/2}=x(1-x^2)e^{-x^2/2}, \] pozitivă pe \((0,1)\) și negativă pe \((1,\infty)\); deci, pe \([0,\infty)\), \(k\) crește pe \([0,1]\) și descrește pe \([1,\infty)\), cu maximul \(k(1)=2e^{-1/2}\approx1.213\) (iar \(k(0)=1\) și \(k(x)\to0\) când \(x\to\infty\)). Fiind pară, \(k\) are pe \(\R\) maximul global \(2e^{-1/2}\), atins în \(x=\pm1\). Constanta optimă este supremumul raportului: \[ c=\sup_x\frac{\phi(x)}{g(x)}=\sqrt{\frac\pi2}\cdot2e^{-1/2}=\sqrt{\frac{4\pi}{2e}}=\sqrt{\frac{2\pi}{e}}\approx1.520,\qquad \frac1c=\sqrt{\frac{e}{2\pi}}\approx0.658 . \]

Pasul 3: condiția de acceptare. Factorul \(\sqrt{\pi/2}\) se simplifică: \[ U\le\frac{\phi(X)}{cg(X)}=\frac{\sqrt{\pi/2}\;k(X)}{\sqrt{\pi/2}\cdot2e^{-1/2}}=\frac{(1+X^2)\,e^{-X^2/2}}{2e^{-1/2}}=\frac{1+X^2}{2}\,e^{-(X^2-1)/2}, \] cu \(X=\tan\big(\pi(U'-\frac12)\big)\sim\Cauchy(0,1)\), unde \(U'\sim\Unif(0,1)\) este independentă de \(U\). Membrul drept este probabilitatea cu care este acceptată propunerea \(X=x\): ea este \(1\) în \(x=\pm1\) (punctele în care \(cg\) atinge ținta), \(\frac12e^{1/2}\approx0.82\) în \(x=0\), \(\frac{1.25}{2}e^{0.375}\approx0.91\) în \(x=0.5\) și numai \(5e^{-4}\approx0.09\) în \(x=3\). Deci \(c=\sqrt{2\pi/e}\approx1.520\), probabilitatea de acceptare este \(\sqrt{e/(2\pi)}\approx0.658\), iar propunerea Cauchy \(X\) este acceptată dacă \(U\le\frac{1+X^2}{2}e^{-(X^2-1)/2}\).

Pasul 4: comparația. În medie sunt acceptate \(65.8\%\) dintre propuneri, față de \(76.0\%\) pentru propunerea Laplace (\(c\approx1.316\)), deși ambele propuneri au cozi mai grele decât ținta. Explicația: densitatea Cauchy își „irosește” masa în cozi, unde aproape toate propunerile sunt respinse. De exemplu, \(\PP(|X|>3)=1-\frac2\pi\arctan3\approx0.20\) pentru Cauchy, \(e^{-3}\approx0.05\) pentru Laplace și \(2\Phi(-3)\approx0.0027\) pentru normală. Cozile propunerii trebuie să fie suficient de grele, dar nu mai mult decât este necesar.

Codul de mai jos generează \(m=5\cdot10^4\) propuneri Cauchy prin metoda inversă, aplică condiția de acceptare de la Pasul 3 și afișează proporția de acceptări, împreună cu media și varianța valorilor acceptate.

set.seed(106)
m <- 5e4
x <- tan(pi * (runif(m) - 0.5))                       # propunerea Cauchy(0,1)
acc <- runif(m) <= (1 + x^2) / 2 * exp(-(x^2 - 1) / 2)
c(acceptare = mean(acc), teoretic = sqrt(exp(1) / (2 * pi)),
  media = mean(x[acc]), varianta = var(x[acc]))
#> acceptare  teoretic     media  varianta 
#> 0.6589200 0.6577446 0.0004464 0.9940581

Proporția de acceptări, \(0.6589\), este apropiată de \(1/c\approx0.6577\), iar valorile acceptate au media \(0.0004\) și varianța \(0.994\), de comparat cu media \(0\) și varianța \(1\) ale repartiției \(\Norm(0,1)\).

De reținut
  • Monte Carlo: \(I=\E[h(X)]\approx\hat I_N=\frac1N\sum_{i=1}^Nh(X_i)\); \(\hat I_N\) este nedeplasat și \(\hat I_N\asto I\) (LNM); eroarea standard este \(\sigma/\sqrt N\), independent de dimensiune; intervalul aproximativ de nivel \(1-\alpha\) este \(\hat I_N\pm z_{1-\alpha/2}\hat\sigma_N/\sqrt N\) (TLC + Slutsky); pentru eroare \(\le\varepsilon\) cu probabilitate \(\approx1-\alpha\): \(N\ge(z_{1-\alpha/2}\sigma/\varepsilon)^2\).
  • Metoda inversă: \(F^{-1}(U)\sim F\) pentru orice \(F\) (Cursul 3); discret — \(X=x_k\) dacă \(s_{k-1}<U\le s_k\), cu \(s_k=p_1+\dots+p_k\); \(\Geom(p)\): \(\lceil\ln U/\ln(1-p)\rceil\); continuu — \(\Exp(\lambda)\): \(-\frac1\lambda\ln U\); \(\Cauchy(0,1)\): \(\tan(\pi(U-\frac12))\); alte repartiții: Tabelul 1.
  • Respingerea pe o mulțime: dacă \(M_n\) sunt \(\iid\) cu repartiția \(\mu\), \(\mu(B)>0\) și \(T=\inf\{n:M_n\in B\}\), atunci \(T\sim\Geom(\mu(B))\) și \(M_T\sim\mu(\cdot\mid B)\). Uniforme pe un dreptunghi \(C\supseteq B\), generate până la primul punct din \(B\), dau un punct uniform pe \(B\); probabilitatea de acceptare este \(\lambda_d(B)/\lambda_d(C)\).
  • Metoda respingerii pentru densități: \(f\le cg\) (deci \(c\ge1\)); generăm \(X\sim g\) și \(U\sim\Unif(0,1)\) până când \(U\le\frac{f(X)}{cg(X)}\); valoarea acceptată are densitatea \(f\); numărul de propuneri este \(\Geom(1/c)\), cu media \(c\); \(c^*=\sup_xf(x)/g(x)\); \(f\) poate fi cunoscută doar până la o constantă; propunerea trebuie să aibă cozi cel puțin la fel de grele ca ținta.
  • Transformări: dacă densitatea comună a lui \((U,V)\) este \(a(u)\,b(v)\), atunci \(U\) și \(V\) sunt independenți, cu densități proporționale cu \(a\), respectiv \(b\); Box–Muller: \(\sqrt{-2\ln U_2}\,(\cos2\pi U_1,\sin2\pi U_1)\) sunt două \(\Norm(0,1)\) independente; \(-\frac1\lambda\ln(U_1\cdots U_n)\sim\GammaD(n,\lambda)\); \(\sum_{i\le k}Z_i^2\sim\chi^2_k=\GammaD(\frac k2,\frac12)\); \(\sum_{i\le m}\Ind_{\{U_i<p\}}\sim\Bin(m,p)\).

Legătura cu cursurile următoare. Simularea este, de acum înainte, instrumentul nostru de verificare. În Cursul 5 vom folosi Teorema schimbării de variabilă și criteriul de factorizare (Lema 10) pentru a demonstra teorema lui Fisher despre eșantioanele din populația normală și vom ilustra rezultatul prin simulare; în Cursul 6 vom studia prin simulare statisticile de ordine și funcția de repartiție empirică; începând cu Cursul 7, principiul Monte Carlo (Propoziția 1) ne va permite să aproximăm deplasarea, varianța și eroarea pătratică medie ale estimatorilor, probabilitățile de acoperire ale intervalelor de încredere (Cursul 12) și puterea testelor (Cursul 14). Metoda inversă și metoda Monte Carlo sunt exersate în Seminarul 4.

Bibliografie

Billingsley, Patrick. 1995. Probability and Measure. 3rd ed. Wiley.
Casella, George, and Roger L. Berger. 2002. Statistical Inference. 2nd ed. Duxbury.
Delmas, Jean-François. 2010. Introduction Au Calcul Des Probabilités Et à La Statistique. Exercices, Problèmes Et Corrections. Les Presses de l’ENSTA.
Devroye, Luc. 1986. Non-Uniform Random Variate Generation. Springer.
Knight, Keith. 2000. Mathematical Statistics. Texts in Statistical Science. Chapman & Hall/CRC.
Robert, Christian P., and George Casella. 2004. Monte Carlo Statistical Methods. 2nd ed. Springer.