Satunnainen permutaatio - Random permutation

Satunnainen vaihtelu on satunnainen tilaaminen joukko esineitä,, eli permutaatio -arvoiset satunnaismuuttuja . Satunnaisten permutaatioiden käyttö on usein olennaista kentille, jotka käyttävät satunnaistettuja algoritmeja , kuten koodausteoriaa , salaustekniikkaa ja simulointia . Hyvä esimerkki satunnainen permutaatio on sekoitus on korttipakan : tämä on ihanteellisesti satunnainen permutaatio 52 korttia.

Satunnaisten permutaatioiden luominen

Entry-by-entry brute force -menetelmä

Yksi tapa luoda satunnainen permutaatio pituudelta n tasaisesti satunnaisesti (eli jokainen n ! Permutaatio esiintyy yhtä todennäköisesti) on luoda sekvenssi ottamalla satunnaisluku välillä 1 ja n peräkkäin, varmistamalla, että ei ole toistoa, ja tulkita tämä sekvenssi ( x ₁ , ..., x _n ) permutaationa

${\ displaystyle {\ begin {pmatrix} 1 & 2 & 3 & \ cdots & n \\ x_ {1} & x_ {2} & x_ {3} & \ cdots & x_ {n} \\\ end {pmatrix}},}$

näkyy tässä kaksirivisessä merkinnässä .

Tämä raa'an voiman menetelmä vaatii satunnaisia ​​uudelleenyrityksiä aina, kun satunnaisluku valitaan jo valitun luvun toisto. Tämä voidaan välttää, jos on i : nnen vaiheen (kun x ₁ , ..., x _{i - 1} on jo valittu), yksi valitsee useita j sattumanvaraisesti välillä 1 ja n - i + 1 ja asetetaan x _i yhtä suuri kuin sen j : nnen suurin valitsematta jäävät numerot.

Fisher-Yates sekoittaa

Yksinkertainen algoritmi tuottaa permutaatio n kohdetta yhdenmukaisesti sattumanvaraisesti ilman uudelleenyritykset, joka tunnetaan nimellä Fisher-Yates sekoitus , on aloittaa minkä tahansa permutaation (esimerkiksi identiteetti permutaatio ), ja sitten läpi asennot 0 kautta n - 2 (käytämme sopimusta, jossa ensimmäinen elementti on indeksi 0, ja viimeinen elementti on indeksi n - 1), ja jokaisen aseman i vaihtaa elementin tällä hetkellä, jossa on satunnaisesti valitun elementin asemissa i kautta n - 1 (lopussa) , mukaan lukien. On helppo varmistaa, että kaikki n -elementin permutaatiot tuotetaan tällä algoritmilla todennäköisyydellä 1/ n !, Jolloin saadaan tasainen jakauma kaikille tällaisille permutaatioille.

unsigned uniform(unsigned m); /* Returns a random integer 0 <= uniform(m) <= m-1 with uniform distribution */

void initialize_and_permute(unsigned permutation[], unsigned n)
{
    unsigned i;
    for (i = 0; i <= n-2; i++) {
        unsigned j = i+uniform(n-i); /* A random integer such that i ≤ j < n */
        swap(permutation[i], permutation[j]);   /* Swap the randomly picked element with permutation[i] */
    }
}

Huomaa, että jos uniform()funktio toteutetaan yksinkertaisesti kuten random() % (m)silloin, tuloksissa esitetään bias, jos palautusarvojen määrä random()ei ole m: n monikerta, mutta tästä tulee merkityksetön, jos palautusarvojen määrä random()on suuruusluokkaa suurempi kuin m.

Tilastot satunnaisista permutaatioista

Kiinteät pisteet

Todennäköisyysjakauma lukumäärän kiintopisteitä on tasaisesti jakautunut satunnainen permutaatio lähestyy Poisson-jakauma , jossa on odotettu arvo 1, kun n kasvaa. Erityisesti osallisuuden ja poissulkemisen periaatteen tyylikäs soveltaminen osoittaa, että todennäköisyys, että kiinteitä pisteitä ei ole, lähestyy 1/ e . Kun n on suuri riitä, todennäköisyysjakauma on kiinteiden pisteiden on lähes Poissonin jakauma kanssa odotusarvo 1. Ensimmäinen n hetket tämän jakauman ovat täsmälleen samat kuin Poisson-jakauman.

Satunnaisuustesti

Kuten kaikkien satunnaisprosessien tapauksessa, satunnaistetun algoritmin, kuten Knuth -sekoituksen, toteutuksen tuloksena olevan jakauman laatu (eli kuinka lähellä se on halutulle yhtenäiselle jakaumalle) riippuu satunnaisuuden taustalla olevan lähteen laadusta, kuten valesatunnaislukugeneraattoriin . Satunnaisia ​​permutaatioita varten on monia mahdollisia satunnaisuustestit , kuten jotkut Diehard -testit . Tyypillinen esimerkki tällaisesta testistä on ottaa jokin permutaatiotilasto , jonka jakauma tunnetaan, ja testata, onko tämän tilastotason jakauma satunnaisesti muodostetuille permutaatiojoukoille lähentänyt todellista jakaumaa.

Katso myös

• Ewensin näytteenottokaava - yhteys populaatiogenetiikkaan
• Faro shuffle
• Golomb – Dickman -vakio
• Satunnaiset permutaatiotilastot
• Sekoitusalgoritmit - satunnainen lajittelumenetelmä, iteratiivinen vaihtomenetelmä

Viitteet

Ulkoiset linkit

• Satunnainen vaihtelu on MathWorld
• Satunnainen permutaation luominen -yksityiskohtainen ja käytännöllinen selitys Knuth -sekoitusalgoritmille ja sen muunnelmille k -permutaatioiden ( luettelosta valittujen k -elementtien permutaatiot ) ja k -alajoukkojen (luettelon elementtien osajoukon luominen ilman korvaamista) luomiseksi pseudokoodilla