Fisher-Yates Shuffle (nimetty Ronald Fisherin ja Frank Yatesin mukaan, joka tunnetaan myös nimellä Knuth Shuffle ( Donald Knuthin mukaan)) on algoritmi, jolla luodaan rajallisen joukon satunnaisia permutaatioita , yksinkertaisesti sanottuna joukon sekoittamiseksi satunnaisesti . Muunnos Fisher- Yates-sekoitusta, joka tunnetaan nimellä Sattolo-algoritmi , voidaan käyttää generoimaan satunnainen permutaatiosykli, jonka pituus on n . Oikein toteutettu Fisher-Yates-sekoitusalgoritmi on puolueeton ., joten jokainen permutaatio generoidaan samalla todennäköisyydellä. Algoritmin moderni versio on erittäin tehokas ja vie aikaa suhteessa joukon elementtien määrään, eikä vaadi lisämuistia.
Fisher-Yates-sekoituksen perusmenettely on samanlainen kuin hatusta numeroiden tai korttien satunnainen vetäminen pakasta elementtien toisensa jälkeen, kunnes elementit loppuvat. Algoritmi tarjoaa tehokkaan ja tiukan menetelmän tällaisiin operaatioihin, mikä takaa puolueettoman tuloksen.
Fisher-Yates-sekoituksen alkuperäisessä muodossaan kuvasivat vuonna 1938 Ronald Fisher ja Frank Yates kirjassaan Statistical Tables for Research in Biology, Architecture and Medicine [1] (Kirjan viimeisin painos kuvaa erilaista sekoitusalgoritmia C. R. Raon ansioksi .) Heidän menetelmänsä kehitettiin kynää ja paperia varten ja käyttivät ennalta laskettuja satunnaislukutaulukoita satunnaisuuden lähteenä. Se näytti tältä:
Jos vaiheessa 2 käytetyt luvut ovat todellakin satunnaisia eivätkä puolueettomia, saamme samat satunnaiset permutaatiot (satunnaiset ja ei-harhaiset). Fisher ja Yates kuvasivat, kuinka saada tällaisia satunnaislukuja mille tahansa aikavälille, ja tarjosivat taulukoita harhan välttämiseksi. He kuvittelivat myös mahdollisuuden yksinkertaistaa menetelmää - valita satunnaisia lukuja yhdestä N : ään ja sitten hylätä toistot - luoda puolet generoidusta permutaatiosta ja käyttää vasta sitten monimutkaisempaa algoritmia jäljellä olevalle puolelle, muuten myös toistuvat numerot törmäävät. usein.
Richard Durstenfeld esitteli tietokoneissa käytettävän Fisher-Yates-sekoitusalgoritmin modernin version vuonna 1964 Communications of the ACM Volume 7, Issue 7, nimeltään "Algoritmi 235: Random permutation" [2] , ja Donald Knuth teki sen suosituksi . kirjansa The Art of Programming as Algorithm P toisessa osassa [3] . Durstenfeld ja Knuth eivät maininneet Fisherin ja Yatesin algoritmia kirjan ensimmäisessä painoksessa eivätkä näyttäneet tienneen siitä. The Art of Programmingin toisessa painoksessa tämä puute kuitenkin korjattiin [4]
Durstenfeldin kuvaama algoritmi eroaa Fisherin ja Yatesin algoritmista pienillä mutta merkittävillä yksityiskohdilla. Jotta algoritmin tietokonetoteutus ei tuhlaa aikaa iteroimiseen jäljellä olevien lukujen läpi vaiheessa 3, Durstenfeldin valitsemat luvut siirrettiin luettelon loppuun kussakin iteraatiossa permutoimalla viimeisellä valitsemattomalla numerolla. Tämä modifikaatio vähensi algoritmin aikamonimutkaisuuden arvoon O ( n ) verrattuna alkuperäisen algoritmin arvoon O ( n2 ) [5] . Tämä muutos johtaa seuraavaan algoritmiin.
Jos haluat sekoittaa n-elementin taulukon a ( indeksit 0..n-1): kaikille i : lle arvoista n − 1 arvoon 1 , suorita j ← satunnaisluku 0 ≤ j ≤ i vaihda a [ j ] ja a [ i ]Fischer-Yates-sekoitus Durstenfeld-versiossa on sekoitus paikallaan . Toisin sanoen, kun sille annetaan täytetty taulukko, se sekoittaa saman taulukon elementit sen sijaan, että luodaan kopio taulukosta elementeillä uudelleen järjestettyinä. Tämä voi antaa merkittävän edun suuria ryhmiä sekoitettaessa.
Matriisin alustaminen ja sekoittaminen samanaikaisesti voi lisätä tehokkuutta hieman, jos käytät sekoituksen "käänteistä" versiota. Tässä versiossa alkuperäinen elementti indeksissä i siirretään satunnaiseen paikkaan ensimmäisten i -paikkojen joukossa sen jälkeen, kun elementti on siirretty tästä paikasta kohtaan i . Jos valitaan satunnaisluku, joka on yhtä suuri kuin i , määrittämätön arvo siirretään ensin, mutta se korvataan välittömästi oikealla arvolla. Tässä variantissa ei tarvita erillistä alustusta, eikä permutaatioita suoriteta. Jos lähde määritellään yksinkertaisella funktiolla, kuten kokonaisluvuilla 0 - n - 1 , lähde voidaan yksinkertaisesti korvata tällä funktiolla, koska lähde ei koskaan muutu ajon aikana.
Matriisin a luominen n satunnaisesti sekoitetusta lähdeelementistä : i : lle 0 - n − 1 tee j ← satunnainen kokonaisluku, jossa 0 ≤ j ≤ i a [ i ] ← a [ j ] a [ j ] ← lähde [ i ]"Käänteisen" sekoituksen oikeellisuus voidaan todistaa induktiolla; mikä tahansa n :stä ! Algoritmin toiminnan aikana saadut eri satunnaislukusekvenssit muodostavat oman permutaationsa siten, että kaikki permutaatiot vastaanotetaan vain kerran.
Toinen tämän lähestymistavan etu on, että tietämättä edes numeroa "n", lähteen elementtien lukumäärää , voimme luoda tasaisesti jakautuneita permutaatioita. Alla oleva taulukko a luodaan iteratiivisesti alkaen tyhjästä ja .length edustaa sen nykyistä pituutta.
kun taas lähde .iselther j ← satunnaisluku 0 ≤ j ≤ a .length jos j = a .length a .add( lähde .nextItem) muuten a .add( a [ j ]) a [ j ] ← lähde .nextItemJärjestetään esimerkiksi luvut uudelleen 1:stä 8:aan käyttämällä alkuperäistä Fisher-Yates -menetelmää . Ensin kirjoitetaan numerot paperille:
| Intervalli | Valittu | Luonnos | Tulos |
|---|---|---|---|
| 1 2 3 4 5 6 7 8 |
Otetaan nyt satunnaisluku k 1:stä 8:aan - olkoon se 3 - ja yliviivataan k :s (eli kolmas) luku (3, tietysti) ja siirretään se tuloksena olevaan sarjaan:
| Intervalli | Valittu | Luonnos | Tulos |
|---|---|---|---|
| 1-8 | 3 | 1 2 3 4 5 6 7 8 | 3 |
Nyt valitaan toinen satunnaisluku, tällä kertaa väliltä 1-7, olkoon sen 4. Nyt yliviivataan neljäs numero , jota ei ole vielä yliviivattu luonnoksesta - tämä on numero 5 - ja lisää se tulokseen:
| Intervalli | Valittu | Luonnos | Tulos |
|---|---|---|---|
| 1-7 | neljä | 1 2 3 4 5 6 7 8 | 3 5 |
Nyt valitsemme satunnaisluvun väliltä 1-6, sitten väliltä 1-5 ja niin edelleen, toistaen yliviivausprosessin edellä kuvatulla tavalla:
| Intervalli | Valittu | Luonnos | Tulos |
|---|---|---|---|
| 1-6 | 5 | 1 2 3 4 5 6 7 8 | 3 5 7 |
| 1-5 | 3 | 1 2 3 4 5 6 7 8 | 3 5 7 4 |
| 1-4 | neljä | 1 2 3 4 5 6 7 8 | 3 5 7 4 8 |
| 1-3 | yksi | 1 2 3 4 5 6 7 8 | 3 5 7 4 8 1 |
| 1-2 | 2 | 1 2 3 4 5 6 7 8 | 3 5 7 4 8 1 6 |
| 1 2 3 4 5 6 7 8 | 3 5 7 4 8 1 6 2 |
Tehdään sama Durstenfeld-menetelmällä . Tällä kertaa sen sijaan, että yliviivaamme valitut numerot ja kopioimme ne jonnekin, järjestämme ne uudelleen numeroilla, joita ei ole vielä valittu. Kuten aiemmin, aloitamme kirjoittamalla numerot 1-8:
| Intervalli | Valittu | Luonnos | Tulos |
|---|---|---|---|
| 1 2 3 4 5 6 7 8 |
Valitaan ensimmäinen satunnaisluku väliltä 1-8, oletetaan, että se on 6, joten vaihda luettelon kuudes ja kahdeksas numero keskenään:
| Intervalli | Valittu | Luonnos | Tulos |
|---|---|---|---|
| 1-8 | 6 | 1 2 3 4 5 8 7 | 6 |
Valitsemme seuraavan satunnaisluvun väliltä 1 - 7 ja annamme sen olla 2. Nyt vaihdamme 2. ja 7. numerot:
| Intervalli | Valittu | Luonnos | Tulos |
|---|---|---|---|
| 1-7 | 2 | 1 7 3 4 5 8 | 26 _ |
Valitsemme seuraavan satunnaisluvun väliltä 1 - 6 ja annamme sen olla 6, mikä tarkoittaa, että meidän pitäisi jättää kuudes numero paikalleen (edellisten permutaatioiden jälkeen numero 8 on tässä). Jatkamme toimintaa tällä tavalla, kunnes koko permutaatio on muodostettu:
| Intervalli | Valittu | Luonnos | Tulos |
|---|---|---|---|
| 1-6 | 6 | 1 7 3 4 5 | 8 2 6 |
| 1-5 | yksi | 5 7 3 4 | 1 8 2 6 |
| 1-4 | 3 | 5 7 4 | 3 1 8 2 6 |
| 1-3 | 3 | 5 7 | 4 3 1 8 2 6 |
| 1-2 | yksi | 7 | 5 4 3 1 8 2 6 |
Sandra Sattolo julkaisi vuonna 1986 hyvin samanlaisen algoritmin tasaisesti jakautuneiden (maksimi)pituisten n syklien generoimiseksi [6] Durstenfeldin ja Sattolon algoritmien ero on vasta vaiheessa 2 – Sattolon algoritmissa valitaan satunnaisluku j väli 1 - i -1, ei 1 - i . Tämä yksinkertainen muunnos johtaa permutaatioihin, jotka koostuvat yhdestä syklistä.
Itse asiassa, kuten alla on kuvattu, on helppo ottaa vahingossa käyttöön Sattolo-algoritmi, kun yritetään luoda Fisher-Yates-algoritmi. Tällainen virhe johtaa permutaatioiden generointiin pienemmästä joukosta ( n − 1)! jaksoja, joiden pituus on N , n: n täyden joukon sijaan ! mahdollisia permutaatioita.
Se, että Suttolon algoritmi luo aina n pituisen syklin, voidaan osoittaa induktiolla. Oletetaan, että ensimmäisen iteraation jälkeen (joka siirsi elementin n paikkaan 1 pituisten elementtien syklin.−nnloput)n<k Hyväksytyn oletuksen mukaan pääsemme alkuasentoon vain käymällä läpi kaikki muut asennot. Viimeinen elementti, siirryttyään kohtaan k ja ensimmäisten n − 1 alkioiden peräkkäiset permutaatiot, päätyy paikkaan l ; vertaa kaikkien n elementin permutaatiota π ensimmäisten n − 1 alkioiden permutaatioon σ . Seuraamalla permutaatioita, kuten edellä mainittiin, emme löydä eroa π :n ja σ :n välillä ennen kuin saavutamme kohdan k . Kohdassa π asemassa k oleva elementti siirtyy viimeiseen paikkaan, ei paikkaan l , ja viimeisenä oleva elementti siirtyy kohtaan l . Tästä pisteestä alkaen elementtien π liikesarja osuu jälleen yhteen σ :n kanssa ja kaikki paikat ajetaan ennen paluuta alkuasentoon tarpeen mukaan.
Kuten permutaatioiden tasatodennäköisyyden todistamisen tapauksessa, riittää osoittamaan, että Sattolon algoritmi luo ( n − 1)! erilaisia permutaatioita, joilla on sama todennäköisyys satunnaislukugeneraattorin oletetun puolueettomuuden vuoksi. ( n −1)! Algoritmin generoimat erilaiset permutaatiot kattavat tarkalleen n pituisten jaksojen joukon .
Yksinkertainen Python -toteutus Sattolon algoritmista :
satunnaisesta tuontivalikoimasta _ _ def sattoloCycle ( kohteet ): i = len ( kohteet ) while i > 1 : i = i - 1 j = Rangerange ( i ) # 0 <= j <= i-1 kohdetta [ j ], kohteet [ i ] = kohteet [ i ], tuotteet [ j ] palautuvatFisher-Yates-algoritmi on varsin tehokas, ja vielä enemmän sen nopeus ja muistikustannukset ovat asymptoottisesti optimaaliset. Käytettäessä korkealaatuista puolueetonta satunnaislukugeneraattoria, algoritmi takaa puolueettoman tuloksen. Algoritmilla on vielä yksi etu - jos vaaditaan jokin osa permutaatioista, algoritmi voidaan pysäyttää puoliväliin tai jopa pysäyttää ja jatkaa useita kertoja.
On olemassa vaihtoehtoinen menetelmä - jokaiselle joukon elementille annetaan satunnaisluku, jonka jälkeen joukko lajitellaan annettujen numeroiden mukaan. Lajittelun asymptoottinen nopeusestimaatti on parhaimmillaan O ( n log n ) , mikä on vertaansa vailla Fisher-Yates-algoritmin O ( n ) nopeusestimaatin kanssa. Kuten Fisher-Yates shuffle, lajittelumenetelmä tuottaa puolueettomia permutaatioita, mutta se on vähemmän herkkä mahdollisille satunnaislukugeneraattorin ongelmille. Satunnaislukujen luomiseen tulee kuitenkin kiinnittää erityistä huomiota toiston välttämiseksi, koska lajiteltu algoritmi ei yleensä lajittele elementtejä satunnaisesti.
Lajittelumenetelmästä on muunnos, jossa luettelo lajitellaan vertailufunktiolla, joka palauttaa satunnaisluvun. Tämä on kuitenkin poikkeuksellisen huono menetelmä : se muodostaa hyvin todennäköisesti epäyhtenäisen jakauman, lisäksi käytetystä lajittelumenetelmästä riippuen [7] [8] . Esimerkiksi käytettäessä pikalajittelua , jolloin aloituselementtinä käytetään kiinteää elementtiä. Tämä lajittelualgoritmi vertaa luettelon jäljellä olevia elementtejä valittuun (pienempi tai suurempi kuin se) ja tällä tavalla määritetään elementin tuloksena oleva sijainti. Jos vertailu palauttaa "pienempi kuin" ja "suurempi kuin" yhtä suurella todennäköisyydellä, niin valittu elementti on keskellä paljon suuremmalla todennäköisyydellä kuin päissä. Toinen lajittelumenetelmä, kuten yhdistämislajittelu , voi tuottaa permutaatioita tasaisemmalla todennäköisyydellä, mutta siinä on silti haittoja, koska kahden sekvenssin yhdistäminen satunnaisvalinnan kanssa samalla todennäköisyydellä (kunnes satunnaislukujono loppuu) ei tuota tulosta. tuottaa tuloksen tasaisella todennäköisyysjakaumalla, koska sekvenssin valinnan todennäköisyyden on oltava verrannollinen sekvenssin elementtien lukumäärään. Itse asiassa mikään "kolikonheitto"-menetelmä, ts. kahden mahdollisuuden peräkkäinen valinta, ei voi luoda permutaatioita (enemmän kuin kahdesta elementistä), joilla on tasainen jakautuminen, koska minkä tahansa tämän järjestelmän mukaisen tapahtuman todennäköisyys on rationaalisen murtoluvun muodossa. jakaja on yhtä suuri kuin potenssi kaksi, kun taas vaaditun todennäköisyyden on oltava 1/ n !.
Periaatteessa tällaiset sekoitusmenetelmät voivat johtaa algoritmisilmukaan tai muistin käyttövirheeseen, koska lajittelualgoritmin oikeellisuus voi riippua järjestysominaisuuksista, kuten transitiivisuudesta [9] . Vaikka tällaista käyttäytymistä ei pitäisi tapahtua sellaisella tavalla, jossa vertailua ei voida ennustaa aikaisempien vertailujen perusteella, tällaisiin vertailuihin on joskus syitä. Esimerkiksi sitä, että elementin on aina oltava yhtä suuri kuin itsensä, voidaan tehokkuuden vuoksi käyttää jonkinlaisena merkkinä tai lippuna, mikä satunnaisissa vertailuissa rikkoo lajittelualgoritmia.
Fisher-Yates-algoritmia toteutettaessa on oltava varovainen sekä itse algoritmin että sen perustana olevan satunnaislukugeneraattorin suhteen. Alla on lueteltu joitakin yleisiä toteutusvirheitä.
Yleinen virhe Fisher-Yates-sekoituksen toteutuksessa on satunnaislukujen valitseminen väärästä intervallista [10] . Viallinen algoritmi saattaa näyttää toimivan oikein, mutta se ei luo kaikkia mahdollisia permutaatioita samalla todennäköisyydellä, ja joitain permutaatioita ei ehkä luoda ollenkaan. Esimerkiksi yleinen ali- tai yliarviointivirhe yhdellä voi tapahtua, kun yllä olevassa esimerkissä vaihdettavan elementin indeksi j on aina pienempi kuin indeksi i , jolla elementti vaihdetaan. Seurauksena on, että Fisher-Yates-sekoituksen sijaan saamme Sattolo-algoritmin , joka muodostaa permutaatioita, jotka vaikuttavat kaikkiin elementteihin. Erityisesti tässä tapauksessa mikään elementti ei voi olla alkuasennossa.
Vastaavasti j :n valitseminen kaikista taulukon indekseistä kussakin iteraatiossa muodostaa myös epätodennäköisiä permutaatioita, vaikkakaan ei niin ilmeisiä. Tämä voidaan todeta siitä tosiasiasta, että tällainen toteutus tuottaa n n eri elementtivaihtoa, kun taas niitä on vain n ! n elementin taulukon mahdolliset permutaatiot . Koska n n ei voi koskaan olla jaollinen n :llä ! ei jäännöstä arvolle n > 2 (koska n ! on jaollinen luvulla n − 1, jolla ei ole yhteisiä alkujakajia n : n kanssa ), joidenkin permutaatioiden täytyy esiintyä useammin kuin toisten. Tarkastellaan erityistä esimerkkiä kolmen elementin permutaatioista [1, 2, 3]. Tästä joukosta on 6 mahdollista permutaatiota (3! = 6), mutta algoritmi tuottaa 27 permutaatiota (3 3 = 27). Tässä tapauksessa [1, 2, 3], [3, 1, 2] ja [3, 2, 1] esiintyvät kukin 4 kertaa 27 sekoituskerrassa, kun taas loput 3 esiintyvät kukin 5 kertaa.
Oikealla oleva matriisi näyttää todennäköisyyden, että jokainen listan pituus 7 alkio ilmestyy lopulliseen paikkaan. Huomaa, että useimpien elementtien kohdalla alkuperäisessä asennossaan (matriisin päälävistäjä) pysymisellä sekoittamisen aikana on pienin todennäköisyys ja yhden sijainnin siirtäminen vasemmalle on suurin todennäköisyys.
Fisher-Yates-algoritmi käyttää näytettä tasaisesti jakautuneista satunnaisluvuista eri alueilta. Useimmat satunnaislukugeneraattorit , sekä todelliset satunnaiset että näennäissatunnaiset, antavat kuitenkin lukuja kiinteällä alueella, esimerkiksi 0 - 2 32 −1. Yksinkertainen ja yleisesti käytetty menetelmä tällaisten lukujen pienentämiseksi haluttuun väliin on käyttää jaon loppuosaa ylärajalla. Tarve generoida satunnaislukuja kaikilla aikaväleillä 0-1 - 0- n varmistaa, että jotkin näistä rajoista eivät jaa generaattorin luonnollista rajaa tasaisesti. Tämän seurauksena jakautuminen ei ole tasaista ja pieniä jäämiä esiintyy useammin.
Oletetaan esimerkiksi, että generaattori tuottaa satunnaislukuja välillä 0 ja 99 (kuten Fisher ja Yates tekivät alkuperäisissä laskentataulukoissaan) ja haluat satunnaislukuja välillä 0 ja 15. Jos löydät yksinkertaisesti luvun loppuosan, kun se jaetaan 16:lla , huomaat, että luvut 0-3 esiintyvät 17 % useammin kuin muut. Syynä tähän on se, että 16 ei jaa 100:aa tasaisesti - luvun 16 suurin kerrannainen, joka ei ylitä 100:aa, on 6x16 = 96, ja loput luvut välillä 96-99 luovat epätasaisuutta. Helpoin tapa välttää tämä ongelma on hylätä tällaiset numerot ennen kuin otat loput. Vaikka periaatteessa tällaisen intervallin lukuja voi törmätä, matemaattinen odotus uudelleenyritysten lukumäärästä on aina pienempi kuin yksi.
Samanlainen ongelma ilmenee käytettäessä satunnaislukugeneraattoria, joka tuottaa liukulukuja , yleensä välillä [0,1). Saatu luku kerrotaan halutun alueen koolla ja pyöristetään ylöspäin. Ongelmana tässä on se, että jopa siististi luoduilla satunnaisilla liukulukuluvuilla on äärellinen tarkkuus, mikä tarkoittaa, että voit saada vain äärellisen määrän mahdollisia liukulukuja, ja kuten yllä olevassa tapauksessa, nämä luvut hajoavat segmenteiksi, jotka eivät jaa lukua on kokonaisluku ja joidenkin segmenttien esiintymistodennäköisyys on suurempi kuin toisten.
Muita ongelmia syntyy käytettäessä pseudosatunnaislukugeneraattoria (PRNG). Tällaisten generaattoreiden näennäissatunnaisen sekvenssin luominen määräytyy täysin niiden sisäisen tilan perusteella generoinnin alussa. Tällaiseen generaattoriin perustuva sekoitusohjelma ei voi luoda enempää permutaatioita kuin generaattorin sisäisten tilojen lukumäärä. Vaikka mahdollisten generaattoritilojen lukumäärä on päällekkäinen permutaatioiden määrän kanssa, jotkut permutaatiot voivat esiintyä useammin kuin toiset. Epätasaisen jakautumisen välttämiseksi satunnaislukugeneraattorin sisäisten tilojen lukumäärän tulee ylittää permutaatioiden lukumäärä useilla suuruusluokilla.
Esimerkiksi sisäänrakennettu pseudosatunnaislukugeneraattori, joka löytyy monista ohjelmointikielistä ja kirjastoista, käyttää tyypillisesti 32-bittistä lukua sisäisille tiloille, mikä tarkoittaa, että tällainen generaattori pystyy generoimaan vain 232 erilaista satunnaislukua. Jos tällaista generaattoria käytettäisiin 52 pelikortin pakan sekoittamiseen , se voisi tuottaa hyvin pienen osan 52:sta! ≈ 2225,6 mahdollista permutaatiota. Generaattori, jolla on alle 226 bittiä sisäisiä tilaa, ei voi luoda kaikkia permutaatioita 52 pelikortin pakassa. Uskotaan, että tasaisen jakauman luomiseksi tarvitaan generaattori, jolla on vähintään 250-bittiset tilat.
Luonnollisesti mikään pseudosatunnaislukugeneraattori ei voi luoda enemmän eri alkutiedoilla antamia satunnaissarjoja kuin näiden alkutietojen lukumäärä. Joten generaattori, jolla on 1024-bittiset sisäiset tilat ja joille on annettu 32-bittiset alkuparametrit, voi luoda vain 232 erilaista permutaatiosekvenssiä. Voit saada lisää permutaatioita valitsemalla generaattorista tarpeeksi satunnaislukuja ennen kuin käytät sitä sekoitusalgoritmissa, mutta tämä lähestymistapa on erittäin tehoton - esimerkiksi 2 30 satunnaisluvun otanta ennen sekvenssin käyttöä sekoitusalgoritmissa vain lisää permutaatioiden määrää numeroon 262 .
Toinen ongelma syntyy käytettäessä yksinkertaista lineaarista kongruential PRNG:tä, kun jaon loppuosaa käytetään pienentämään satunnaislukujen väliä, kuten edellä mainittiin. Ongelmana tässä on, että lineaarisen kongruentin PRNG:n alemmat bitit ovat vähemmän satunnaisia kuin korkeammat bitit - alemmilla n bitillä on enintään 2 n jakso . Jos jakaja on kahden potenssi, jäännöksen ottaminen tarkoittaa korkean kertaluvun bittien hylkäämistä, mikä johtaa merkittävään satunnaisuuden vähenemiseen.
Lopuksi on huomattava, että jopa hienoa generaattoria käytettäessä algoritmissa voi syntyä virhe generaattorin väärästä käytöstä. Kuvittele esimerkiksi, että algoritmin Java -toteutus luo uuden generaattorin jokaiselle sekoitusprosessin kutsulle asettamatta parametreja konstruktoriin. Nykyistä aikaa (System.currentTimeMillis()) käytetään generaattorin alustamiseen. Siten kaksi puhelua, joiden aikaero on alle millisekunnin, antavat identtiset permutaatiot. Tämä tapahtuu lähes varmasti, jos sekoitus tapahtuu toistuvasti ja nopeasti, mikä johtaa erittäin epätasaiseen permutaatioiden jakautumiseen. Sama ongelma voi ilmetä vastaanotettaessa satunnaislukuja kahdesta eri virrasta. On oikeampaa käyttää yhtä generaattorin staattista esiintymää, joka on määritelty sekoitusrutiinin ulkopuolella.