Generatori pseudoslučajnih brojeva i metode za njihovo testiranje. Generator pseudoslučajnih brojeva - slučajni

Imajte na umu da bi u idealnom slučaju krivulja gustoće distribucije slučajnih brojeva izgledala kao ona prikazana na Sl. 22.3. Odnosno, u idealan slučaj Svaki interval sadrži isti broj točaka: N i = N/k , gdje N je ukupan broj bodova, k- broj intervala, i= 1, …, k .

Treba imati na umu da se generiranje proizvoljnog slučajnog broja sastoji od dvije faze:

• generiranje normaliziranog slučajnog broja (to jest, jednoliko raspoređenog od 0 do 1);
• transformacija normaliziranih slučajnih brojeva r i u slučajne brojeve x i, koji se distribuiraju prema (proizvoljnom) zakonu distribucije koji zahtijeva korisnik ili u potrebnom intervalu.

Generatori slučajnih brojeva prema načinu dobivanja brojeva dijele se na:

• fizički;
• tablični;
• algoritamski.

Fizički RNG-ovi

Primjeri fizičkih RNG-ova su: novčić ("orao" - 1, "rep" - 0); kocke; bubanj sa strelicom podijeljenom na sektore s brojevima; hardverski generator buke (GS), koji se koristi kao bučni toplinski uređaj, na primjer, tranzistor (sl. 22.4–22.5).

Tablični RNG

Tablični RNG kao izvor slučajnih brojeva koriste posebno sastavljene tablice koje sadrže provjerene nekorelirane, odnosno brojeve koji ni na koji način ne ovise jedan o drugom. U tablici. 22.1 prikazuje mali ulomak takve tablice. Šetajući tablicom s lijeva na desno od vrha do dna, možete dobiti slučajne brojeve ravnomjerno raspoređene od 0 do 1 sa željenim brojem decimalnih mjesta (u našem primjeru koristimo tri decimalna mjesta za svaki broj). Budući da brojevi u tablici ne ovise jedan o drugom, tablicom se može prijeći na različite načine, na primjer, odozgo prema dolje, ili s desna na lijevo, ili, recimo, možete odabrati brojeve koji su na parnim pozicijama.

Dostojanstvo ovu metodu u tome što daje doista slučajne brojeve, budući da tablica sadrži provjerene nekorelirane brojeve. Nedostaci metode: potrebno je puno memorije za pohranjivanje velikog broja znamenki; velike poteškoće u generiranju i provjeravanju takvih tablica, ponavljanja pri korištenju tablice više ne jamče slučajnost brojčanog niza, a time i pouzdanost rezultata.

Postoji tablica koja sadrži 500 apsolutno slučajnih provjerenih brojeva (preuzeto iz knjige I. G. Venetsky, V. I. Venetskaya "Osnovni matematički i statistički koncepti i formule u ekonomskoj analizi").

Algoritamski RNG

Brojevi generirani pomoću ovih RNG-ova uvijek su pseudoslučajni (ili kvazislučajni), odnosno svaki sljedeći generirani broj ovisi o prethodnom:

r i + 1 = f(r i) .

Nizovi sastavljeni od takvih brojeva tvore petlje, odnosno nužno postoji ciklus koji se ponavlja beskonačan broj puta. Ciklusi koji se ponavljaju nazivaju se periodima.

Prednost RNG podataka je brzina; generatori praktički ne zahtijevaju memorijske resurse, kompaktni su. Nedostaci: brojevi se ne mogu u potpunosti nazvati slučajnim, jer postoji ovisnost između njih, kao i prisutnost razdoblja u nizu kvazi-slučajnih brojeva.

Razmotrite nekoliko algoritamskih metoda za dobivanje RNG-a:

• metoda srednjih kvadrata;
• metoda srednjih proizvoda;
• metoda miješanja;
• linearna kongruentna metoda.

Metoda srednjeg kvadrata

Postoji neki četveroznamenkasti broj R 0 . Taj se broj kvadrira i unosi R jedan . Dolazi iz R 1 uzima se sredina (četiri srednje znamenke) - novi slučajni broj - i upisuje se R 0 . Zatim se postupak ponavlja (vidi sliku 22.6). Imajte na umu da je zapravo, kao slučajni broj, potrebno uzeti ne ghij, ali 0.ghij- s nulom i decimalnim zarezom dodijeljenim lijevo. Ova činjenica se ogleda na sl. 22.6, a kasnije slične slike.

Nedostaci metode: 1) ako u nekoj iteraciji broj R 0 postaje nula, tada generator degenerira, pa je važan ispravan izbor početne vrijednosti R 0; 2) generator će ponoviti niz M n koraci (u najboljem slučaju), gdje n- znamenkasti kapacitet broja R 0 , M je baza brojevnog sustava.

Za primjer na sl. 22.6 : ako je broj R 0 će biti predstavljeno u binarnom brojevnom sustavu, tada će se slijed pseudoslučajnih brojeva ponoviti nakon 2 4 = 16 koraka. Imajte na umu da se ponavljanje niza može dogoditi i ranije ako je početni broj neuspješno odabran.

Gore opisanu metodu predložio je John von Neumann i datira iz 1946. godine. Budući da se ova metoda pokazala nepouzdanom, brzo je napuštena.

Metoda medijana proizvoda

Broj R 0 pomnoženo sa R 1 , iz rezultata R 2 sredina je uklonjena R 2 * (ovo je još jedan slučajni broj) i pomnožen sa R jedan . Prema ovoj shemi izračunavaju se svi sljedeći slučajni brojevi (vidi sliku 22.7).

Metoda miješanja

Metoda miješanja koristi operacije za rotiranje sadržaja ćelije lijevo i desno. Ideja metode je sljedeća. Neka ćelija pohrani početni broj R 0 . Cikličnim pomicanjem sadržaja ćelije ulijevo za 1/4 duljine ćelije, dobivamo novi broj R 0*. Slično, cikličkim pomicanjem sadržaja ćelije R 0 udesno za 1/4 duljine ćelije, dobivamo drugi broj R 0**. Zbroj brojeva R 0 * i R 0** daje novi slučajni broj R jedan . Unaprijediti R 1 je upisan R 0 , a cijeli slijed operacija se ponavlja (vidi sliku 22.8).

Imajte na umu da je broj dobiven zbrajanjem R 0 * i R 0 ** , možda neće u potpunosti stati u ćeliju R jedan . U tom slučaju, dodatne znamenke treba odbaciti iz primljenog broja. Objasnimo to za Sl. 22.8, gdje su sve ćelije predstavljene s osam binarnih znamenki. Neka bude R 0 * = 10010001 2 = 145 10 , R 0 ** = 10100001 2 = 161 10 , onda R 0 * + R 0 ** = 100110010 2 = 306 10 . Kao što vidite, broj 306 zauzima 9 znamenki (u binarnom brojevnom sustavu), a ćelija R 1 (kao i R 0) može sadržavati najviše 8 bita. Stoga, prije unosa vrijednosti u R 1 potrebno je ukloniti jedan "dodatni", krajnji lijevi bit iz broja 306, što rezultira R 1 više neće ići 306, već 00110010 2 = 50 10 . Također imajte na umu da se u jezicima kao što je Pascal, "skraćenje" dodatnih bitova kada se ćelija prelije automatski vrši u skladu s zadanim tipom varijable.

Linearna kongruentna metoda

Linearna kongruencijalna metoda jedan je od najjednostavnijih i trenutno najčešće korištenih postupaka koji simuliraju slučajne brojeve. Ova metoda koristi mod ( x, y) , koji vraća ostatak nakon dijeljenja prvog argumenta s drugim. Svaki sljedeći slučajni broj izračunava se na temelju prethodnog slučajnog broja pomoću sljedeće formule:

r i+ 1 = mod( k · r i + b, M) .

Slijed slučajnih brojeva dobiven ovom formulom naziva se linearni kongruentni niz. Mnogi autori nazivaju linearni kongruentni niz kao b = 0 multiplikativna kongruentna metoda, i kada b ≠ 0 — mješovita kongruentna metoda.

Za visokokvalitetni generator potrebno je odabrati prikladne koeficijente. Potrebno je da broj M bio prilično velik budući da razdoblje ne može imati više M elementi. S druge strane, podjela korištena u ovoj metodi je prilično spora operacija, pa bi za binarno računalo logičan izbor bio M = 2 N, jer se u ovom slučaju pronalaženje ostatka dijeljenja unutar računala svodi na binarnu logičku operaciju "AND". Također je uobičajeno odabrati najveći prosti broj M, manje od 2 N: u posebnoj literaturi je dokazano da su u ovom slučaju najmanje značajne znamenke rezultirajućeg slučajnog broja r i+ 1 ponašaju se jednako nasumično kao i stariji, što ima pozitivan učinak na cijeli niz slučajnih brojeva u cjelini. Primjer je jedan od Mersenneovi brojevi, jednako 2 31 - 1 , i stoga, M= 2 31 – 1 .

Jedan od zahtjeva za linearne kongruentne nizove je najduži mogući period. Duljina razdoblja ovisi o vrijednostima M , k I b. Teorem koji prikazujemo u nastavku omogućuje nam da odredimo je li moguće postići razdoblje maksimalne duljine za određene vrijednosti M , k I b .

Teorema. Linearni kongruentni niz definiran brojevima M , k , b I r 0 , ima period duljine M ako i samo ako:

• brojevima b I M koprimeran;
• k– 1 puta str za svaki jednostavan str, što je djelitelj M ;
• k– 1 je višekratnik od 4 ako M višestruko od 4.

Na kraju, zaključimo s nekoliko primjera korištenja linearne kongruencijalne metode za generiranje slučajnih brojeva.

Utvrđeno je da će se niz pseudoslučajnih brojeva generiranih na temelju podataka iz primjera 1 ponavljati svakih M/4 broja. Broj q se proizvoljno postavlja prije početka izračuna, međutim, treba imati na umu da serija ostavlja dojam da je nasumična k(i stoga q). Rezultat se može malo poboljšati ako b neparan i k= 1 + 4 q - u ovom slučaju, serija će se ponavljati svaki M brojevima. Nakon duge potrage k Istraživači su se odlučili na vrijednosti 69069 i 71365.

Generator slučajnih brojeva koristeći podatke iz primjera 2 će generirati slučajne neponavljajuće brojeve s periodom od 7 milijuna.

Multiplikativnu metodu za generiranje pseudoslučajnih brojeva predložio je D. H. Lehmer 1949. godine.

Provjera kvalitete generatora

Kvaliteta cjelokupnog sustava i točnost rezultata ovisi o kvaliteti RNG-a. Stoga, slučajni niz koji generira RNG mora zadovoljiti niz kriterija.

Provjere koje se provode su dvije vrste:

• provjere ujednačene raspodjele;
• testiranje statističke neovisnosti.

Provjerava ujednačenu raspodjelu

1) RNG bi trebao dati blizu sljedećih vrijednosti statističkih parametara karakterističnih za ujednačeni slučajni zakon:

2) Test frekvencije

Test frekvencije vam omogućuje da saznate koliko je brojeva palo u interval (m r – σ r ; m r + σ r) , odnosno (0,5 - 0,2887; 0,5 + 0,2887) ili, u konačnici, (0,2113; 0,7887) . Budući da je 0,7887 - 0,2113 = 0,5774, zaključujemo da bi u dobrom RNG-u oko 57,7% svih slučajnih brojeva koji su ispali trebalo pasti u ovaj interval (vidi sliku 22.9).

Također treba uzeti u obzir da broj brojeva u intervalu (0; 0,5) treba biti približno jednak broju brojeva u intervalu (0,5; 1).

3) Hi-kvadrat test

Hi-kvadrat test (χ 2 -test) jedan je od najpoznatijih statističkih testova; to je glavna metoda koja se koristi u kombinaciji s drugim kriterijima. Hi-kvadrat test je 1900. predložio Karl Pearson. Njegov izvanredan rad smatra se temeljom moderne matematičke statistike.

U našem slučaju, hi-kvadrat test će nam omogućiti da saznamo koliko smo stvorili stvaran RNG je blizak referenci RNG-a, tj. zadovoljava li zahtjev uniformne distribucije ili ne.

dijagram frekvencija referenca RNG je prikazan na sl. 22.10. Budući da je zakon distribucije referentnog RNG-a ujednačen, (teorijska) vjerojatnost str i pogađanje brojeva i-ti interval (ukupan broj ovih intervala k) jednako je str i = 1/k . I tako, u svakom k intervali će padati glatko, nesmetano na str i · N brojevi ( N je ukupan broj generiranih brojeva).

Pravi RNG će proizvesti brojeve raspoređene (i ne nužno ravnomjerno!) k intervale i svaki interval će uključivati n i brojevi (ukupno n 1 + n 2 + … + n k = N ). Kako možemo odrediti koliko je testirani RNG dobar i blizak referentnom? Sasvim je logično razmotriti kvadrate razlika između primljenog broja brojeva n i i "referenca" str i · N . Zbrojimo ih i kao rezultat dobijemo:

χ 2 exp. =( n 1- str jedan · N) 2 + (n 2- str 2 · N) 2 + … + ( n k – str k · N) 2 .

Iz ove formule slijedi da što je manja razlika u svakom od pojmova (a time i manja vrijednost χ 2 exp. ), to je jači zakon distribucije slučajnih brojeva generiranih realnim RNG-om teži da bude ujednačen.

U prethodnom izrazu, svakom od pojmova je dodijeljena ista težina (jednaka 1), što zapravo možda nije točno; stoga je za hi-kvadrat statistiku potrebno svaku normalizirati i th pojam, dijeleći ga sa str i · N :

Konačno, zapišimo rezultirajući izraz kompaktnije i pojednostavimo ga:

Dobili smo vrijednost hi-kvadrat testa za eksperimentalni podaci.

U tablici. 22.2 teorijski vrijednosti hi-kvadrata (χ 2 teor.), gdje je ν = N– 1 je broj stupnjeva slobode, str je korisnički specificirana razina pouzdanosti koja određuje koliko bi RNG trebao zadovoljiti zahtjeve ujednačene distribucije, ili str — je vjerojatnost da eksperimentalna vrijednost χ 2 exp. bit će manji od tabelarne (teorijske) χ 2 teor. ili jednak tome.

Smatrajte prihvatljivim str od 10% do 90%.

Ako je χ 2 exp. mnogo više od χ 2 teor. (tj str je velika), zatim generator ne zadovoljava zahtjev ujednačene raspodjele, budući da su promatrane vrijednosti n i otići predaleko od teoretskog str i · N i ne može se smatrati slučajnim. Drugim riječima, uspostavlja se tako veliki interval povjerenja da ograničenja u brojevima postaju vrlo labavi, a zahtjevi za brojeve slabi. U tom slučaju će se uočiti vrlo velika apsolutna pogreška.

Čak je i D. Knuth u svojoj knjizi "Umjetnost programiranja" primijetio da imajući χ 2 exp. mali također, općenito, nije dobar, iako se na prvi pogled čini izvanrednim s gledišta jednoličnosti. Doista, uzmite niz brojeva 0,1, 0,2, 0,3, 0,4, 0,5, 0,6, 0,7, 0,8, 0,9, 0,1, 0,2, 0,3, 0,4, 0,5, 0,6, ... - oni su idealni sa stajališta ujednačenost, a χ 2 exp. bit će praktički nula, ali je malo vjerojatno da ćete ih prepoznati kao nasumične.

Ako je χ 2 exp. mnogo manje od χ 2 teor. (tj str- malo), zatim generator ne zadovoljava zahtjev za slučajnu jednoličnu distribuciju, budući da su promatrane vrijednosti n i preblizu teoretskom str i · N i ne može se smatrati slučajnim.

Ali ako je χ 2 exp. leži u određenom rasponu, između dvije vrijednosti χ 2 teor. , što odgovara npr. str= 25% i str= 50%, tada možemo pretpostaviti da su vrijednosti slučajnih brojeva koje generira senzor potpuno slučajne.

Osim toga, mora se imati na umu da sve vrijednosti str i · N mora biti dovoljno velik, na primjer, veći od 5 (pronađeno empirijski). Tek tada (uz dovoljno velik statistički uzorak) eksperimentalni uvjeti mogu se smatrati zadovoljavajućima.

Dakle, postupak provjere je sljedeći.

Testovi za statističku neovisnost

1) Provjera učestalosti pojavljivanja znamenke u nizu

Razmotrimo primjer. Slučajni broj 0,2463389991 sastoji se od znamenki 2463389991, a broj 0,5467766618 sastoji se od znamenki 5467766618. Kombinirajući nizove znamenki, imamo: 2463348979656.

Jasno je da je teorijska vjerojatnost str i ispasti i brojka (od 0 do 9) je 0,1.

2) Provjera izgleda niza identičnih brojeva

Označiti sa n L broj nizova identičnih uzastopnih znamenki duljine L. Sve treba provjeriti L od 1 do m, gdje m je broj koji je odredio korisnik: maksimalni broj identičnih znamenki u nizu.

U primjeru "24633899915467766618" pronađene su 2 serije dužine 2 (33 i 77), tj. n 2 = 2 i 2 serije duljine 3 (999 i 666), t.j. n 3 = 2 .

Vjerojatnost niza duljine od L jednako je: str L= 9 10 – L (teorijski). Odnosno, vjerojatnost pojave niza duljine jednog znaka jednaka je: str 1 = 0,9 (teoretski). Vjerojatnost pojave serije od dva znaka je: str 2 = 0,09 (teoretski). Vjerojatnost pojavljivanja serije od tri znaka je: str 3 = 0,009 (teoretski).

Na primjer, vjerojatnost pojavljivanja niza duljine jednog znaka jednaka je str L= 0,9 , budući da može biti samo jedan znak od 10, a samo 9 znakova (nula se ne broji). A vjerojatnost da će se dva identična znaka "XX" sresti u nizu je 0,1 0,1 9, odnosno vjerojatnost od 0,1 da će se znak "X" pojaviti na prvoj poziciji množi se s vjerojatnošću od 0,1 da je isti znak pojavit će se na drugom mjestu "X" i pomnoženo s brojem takvih kombinacija 9.

Učestalost pojavljivanja serija izračunava se prema formuli "hi-kvadrat" koju smo prethodno analizirali koristeći vrijednosti str L .

Napomena: Generator se može provjeriti više puta, ali provjere nisu potpune i ne jamče da generator proizvodi nasumične brojeve. Primjerice, generator koji proizvodi sekvencu 12345678912345… smatrat će se idealnim tijekom provjera, što očito nije u potpunosti točno.

Zaključno, napominjemo da je treće poglavlje knjige Donalda E. Knutha "The Art of Programming" (svezak 2) u potpunosti posvećeno proučavanju slučajnih brojeva. Proučava razne metode generiranje slučajnih brojeva, statistički kriteriji za slučajnost i pretvaranje ravnomjerno raspoređenih slučajnih brojeva u druge vrste slučajnih varijabli. Više od dvjesto stranica posvećeno je prezentaciji ovog materijala.

U računalnim programima često je potrebno oponašati slučajnost. Na primjer, prilikom razvoja igara. Ako program ima određeni generator, tj. proizvođača, slučajnog broja, tada se pomoću tako dobivenog broja može izabrati jednu ili drugu granu izvršavanja programa, ili proizvoljan objekt iz kolekcije. Drugim riječima, glavna stvar je generirati broj. Na njemu se temelji emulacija slučajnosti druge vrste.

Zasigurno ne znamo postoji li nezgoda u prirodi ili nam se to samo čini zbog ograničenog znanja našeg znanja. Znamo samo da u programiranju nema prave slučajnosti. Nigdje uzeti proizvoljan broj, ne možete programirati njegov izgled niotkuda. Možete stvoriti samo program koji će, kao rezultat primjene složene formule na "sjeme", proizvesti broj, a činit će nam se da je taj broj slučajan.

"Zrno" je početni podatak za formulu. To može biti, na primjer, sustavno vrijeme u milisekundama, koje se stalno mijenja. Stoga će "zrno" biti stalno drugačije. Ili ga programer može sam postaviti.

Takav program (zapravo modul ili funkcija) naziva se generator pseudoslučajnih brojeva. Python standardna biblioteka uključuje nasumični modul. Sadrži puno funkcija koje se odnose na emulaciju slučajnosti (na primjer, "promiješavanje" elemenata niza), a ne samo funkcije za generiranje pseudoslučajnih brojeva.

Ovaj vodič će pokriti funkcije random(), randrange() i randint() iz random modula. Imajte na umu da random modul sadrži random() funkciju istog imena. Događa se.

Za pristup funkcijama morate uvesti nasumični modul:

>>> uvoz nasumično

Ili uvezite pojedinačne funkcije iz njega:

>>> iz slučajnog uvoza random , randrange, randint

Funkcije za dobivanje cjelobrojnih "slučajnih" brojeva - randint() i randrange()

Funkcije randint() i randrange() generiraju pseudoslučajne cijele brojeve. Prvi od njih je najjednostavniji i uvijek uzima samo dva argumenta - granice cjelobrojnog raspona iz kojeg se odabire bilo koji broj:

>>> nasumični .randint (0 , 10 ) 6

ili (ako su uvezene zasebne funkcije):

>>> randint (100 , 200 ) 110

U slučaju randint(), obje granice su uključene u raspon, tj. jezikom matematike, segment je opisan kao .

Brojevi mogu biti negativni:

>>> nasumično .randint (-100 , 10 ) -83 >>> nasumični .randint (-100 , -10 ) -38

Ali prvi broj uvijek mora biti manji ili barem jednak drugom. To je<= b.

Funkcija randrange() je složenija. Može potrajati jedan argument, dva ili čak tri. Ako je naveden samo jedan, onda vraća nasumični broj između 0 i navedenog argumenta. Štoviše, sam argument nije uključen u raspon. U jeziku matematike, to je