Ziggurat algoritm

Această intrare sau secțiune despre subiectul algoritmilor nu menționează sursele necesare sau cei prezenți sunt insuficienți . Puteți îmbunătăți această intrare adăugând citate din surse de încredere în conformitate cu liniile directoare privind utilizarea surselor .

Acest articol sau secțiune despre informatică conține erori de ortografie sau sintactice sau este scris într-o formă îmbunătățită . Ajutați la corectarea acestuia în conformitate cu convențiile din limba italiană și manualul de stil Wikipedia . Urmați sfaturile de proiectare de referință .

Algoritmul zigurat este un algoritm folosit pentru prelevarea de probe numerică pseudo - aleatoare. Aparținând clasei de așa-numitele eșantionare de respingere algoritmi, se bazează pe utilizarea unei surse de numere aleatoare uniform distribuite, în general , un generator de numere de pseudo-aleatoare , și a tabelelor pre-calculate. Algoritmul este utilizat pentru a genera valori de la o monotone descrescătoare distribuției de probabilitate . Acesta poate fi , de asemenea , aplicate simetrice distribuții unimodale, cum ar fi distribuția normală . Acesta a fost dezvoltat în anii 1960 de către George Marsaglia și altele.

Pentru a produce o valoare cu acest algoritm, este necesar pentru a genera un aleatoare plutitoare punct de valoare, un indice al unui tabel aleatoare, o căutare a valorii în tabel, o multiplicare și o comparație. În unele cazuri, sunt necesare mai multe etape. În orice caz, algoritmul de procesare este mai rapid decât alte două metode cele mai folosite pentru a genera numere aleatoare distribuite normal , care sunt metoda polară Marsaglia și transformarea Box-Muller . Cu toate acestea, din moment ce algoritmul zigurat este complex pentru a pune în aplicare, acesta este de obicei folosit atunci când o cantitate mare de numere aleatoare trebuie să fie generate.

Datele algoritmului pe termen zigurat înapoi la articolul scris de Marsaglia și Wai Wan Tsang în 2000; este numit astfel deoarece se bazează pe acoperirea conceptual distribuției de probabilitate cu segmente dreptunghiulare suprapuse în ordinea mărimii descrescătoare, rezultând într - o figură care seamănă cu un ziggurat .

Ziggurat Algoritmul utilizat pentru a genera valori de exemplu , cu o distribuție normală (numai valori pozitive sunt prezentate pentru simplitate). puncte roz sunt inițial numere aleatoare, care sunt distribuite în mod egal. Funcția de distribuție dorită este mai întâi segmentată în zone egale „A“. Un strat i este selectat aleatoriu din sursa uniformă pe stânga. Apoi , o valoare aleatoare de la sursă este înmulțită cu lățimea stratului ales , iar rezultatul este x testat pentru a vedea ce regiune a fantei cade în. Rezultatele posibile sunt: 1) (stânga, regiunea neagră) eșantionul clar sub curba și se trece direct la ieșire, 2) (dreapta, regiune cu dungi verticale) valoarea eșantionului poate fi sub curba și trebuie să fie testate în continuare. În acest caz, o valoare y este generat aleator în interiorul stratului ales și comparat cu f (x). Dacă inferior, punctul este sub curbă , iar valoarea x este de ieșire. În caz contrar, punctul x ales este respins , iar algoritmul este reluat de la început.

Teoria funcționării

Algoritmul ziggurat este o prelevare de probe de respingere algoritm, adică, generează aleator un punct într - o distribuție puțin mai mare decât distribuția dorită, apoi se verifică dacă punctul generat este în distribuția dorită. Având în vedere un punct aleatoriu sub o densitate de probabilitate curba, x coordonata este un număr aleator cu distribuția dorită.

Distribuția aleasă de către algoritmul zigurat este compus din n regiuni de suprafață egală.

Având în vedere o monotonă scădere a densității probabilității funcției f (x), definit pentru orice x ≥ 0, baza zigguratul este definită ca toate punctele din distribuție și sub y ₁ = f (x _1). Aceasta constă dintr - o regiune dreptunghiulară din (0, 0) până la (x _1, y _1), plus coadă ( de obicei infinit) de distribuție, unde x> x ₁ (și y <y _1).

Acest strat (strat 0) are o suprafata A. In plus, un strat dreptunghiular de lățime _{se adaugă} x ₁ și înălțimea A / x _1, deci cu întotdeauna zona A. Partea superioară a acestui strat este de la y ₂ = y ₁ + A / x ₁ și se intersectează cu funcția de densitate într - un punct (x _2, y _2), unde y ₂ = f (x _2). Acest strat include fiecare punct al funcției de densitate între y ₁ și y _2, dar (spre deosebire de stratul de bază) , de asemenea , include puncte ca (x _1, y ₂₎ , care nu sunt în distribuția dorită.

straturi suplimentare sunt apoi stivuite. Pentru a utiliza un tabel precalculate de dimensiune n (256 de obicei), x ₁ este aleasă astfel încât x _n = 0, ceea ce înseamnă că nivelul superior, nivelul n - 1, ajunge exact la vârf de distribuție a (0, f (0)) .

Layer i se extinde vertical de la y _i y _{i + 1} și poate fi împărțit orizontal în două regiuni: ( în general mai mare) de la 0 până la x _{i +1} , care este conținută în întregime în distribuția dorită și porțiunea (mică) din x _{i + 1} la x _i, care este doar parțial conținut.

Ignorând pentru un moment nivelul 0 problemă, și având în vedere variabilele aleatoare uniforme U ₀ și U ₁ ∈ [0,1), algoritmul zigurat operează acești pași:

1. Alegeți un nivel aleatoriu 0 ≤ i <n.
2. Fie x = U ₀ x _i.
3. Dacă x <x _{i + 1,} x întoarcere.
4. Să y = y _i + ₁ U (y _{i + 1} - y _i).
5. F Se calculează (x). Dacă y <f (x), x retur.
6. În caz contrar, pentru a alege noi numere aleatoare și du-te înapoi la pasul 1.

Pasul 1 este echivalent cu alegerea de coordonate y. Pasul 3 verifică dacă coordona x este în funcția de densitate dorită. Altfel, etapa 4 alege un coordonate y și pasul 5 efectueazã testul de acceptare.

Rețineți că , pentru nivelul superior n - 1 acest test nu reușește întotdeauna, pentru că x _n = 0.

Optimizări

Algoritmul poate fi realizată în mod eficient , folosind tabele de pre-calculat pentru x _i și y _i = f (x _i), dar există unele îmbunătățiri pentru a face chiar mai rapid:

• Nimic din algoritmul zigurat depinde de normalizarea funcției de distribuție a probabilității (integrala de sub curba egală cu 1) , astfel încât eliminarea constantelor de normalizare poate accelera calculul lui f (x).
• In loc de a compara U ₀ x _i cu x _{i + 1} în pasul 3, este posibil să precompute x _{i + 1} / x _i și se compară cu U ₀ direct. Dacă U ₀ este un generator de numere aleatoare întreg, aceste limite pot fi premultiplied de 2 ³² (sau 2 ^31, după caz) , astfel încât o comparație întreg poate fi utilizat.
• La generarea IEEE 754 cu o singură precizie valori în virgulă mobilă, care au doar o mantisă de 24 biți (inclusiv implicit lider 1), biții cei mai puțin semnificativi ai unui bit-32 întregi aleatoare nu sunt utilizate. Acești biți pot fi utilizate pentru a selecta numărul de niveluri.

Alte proiecte

• Wikimedia Commons conține imagini sau alte fișiere despre algoritmul zigurat

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică