Náhodné permutácie

Náhodné permutácie sú mojou obľúbenou témou na ilustráciu základných techník v teórii pravdepodobnosti. Keď som na Wolfram demonstrations objavil programík na grafické znázorňovanie cyklov náhodnej permutácie, rozhodol som sa, že o náhodných permutáciách napíšem krátky príspevok do blogu. Možno táto téma niekoho zaujme; bola by napríklad vhodná na bakalársku (a možno aj diplomovú) prácu pre teoretickejšie orientovaného matematika.

Uvažujme postupnosť (1,2,...,n), ktorú "dokonale" náhodne premiešame, napríklad pomocou jednoduchého Fisherovho-Yatsovho algoritmu. Tým dosiahneme to, že každá z n! možných výsledných permutácií má pravdepodobnosť 1/n!. Uvedomme si, že každá permutácia rozloží množinu čísiel 1,...,n na niekoľko podmnožín zodpovedajúcich "cyklom" (pozri ilustračný obrázok vľavo hore pre n=24).

Napríklad pre n=6 má permutácia (2,1,4,6,5,3) tri cykly: cyklus „...-3-4-6-3-4-6-...“ dĺžky 3 (pretože pôvodná pozícia 3 je v novej permutácii obsadená číslom 4, pôvodná pozícia 4 je obsadená číslom 6 a pôvodná pozícia 6 je obsadená číslom 3), ďalej cyklus „...-1-2-1-2-1-...“ dĺžky 2, a cyklus „...-5-5-5-...“ dĺžky 1. Permutácia na ilustračnom obrázku má 5 cyklov dĺžok 1,1,3,5 a 14.

Z pravdepodobnostného hľadiska je práve zaujímavé študovať charakteristiky počtu cyklov a ich dĺžok v náhodnej permutácií.

Najklasickejší problém z oblasti náhodných permutácií, ktorý sa objavuje na prednáškach z pravdepodobnosti po celom svete, môžeme formulovať napríklad takto: Sekretárka náhodne rozdelí n (rôznych) listov do n (rôznych) obálok s adresami. Aká je pravdepodobnosť, že aspoň jeden list vloží do správnej obálky? V reči náhodných permutácií a cyklov sa pýtame na otázku aká je pravdepodobnosť, že náhodná permutácia n čísiel bude mať aspoň jeden cyklus dĺžky jedna. To je možné vyriešiť jednoduchou aplikáciou princípu zapojenia vypojenia. Na tomto príklade je tiež zaujímavé to, že pre n ide do nekonečna sa výsledná pravdepodobnosť blíži presne k 1-1/e.

Veľa podobných otázok je vyriešených v podrobnom článku Wikipédie pomocou techniky vytvárajúcich funkcií. Niektoré z týchto otázok sa však dajú vyriešiť oveľa elementárnejšie, priamočiarym využitím linearity strednej hodnoty. Takto je napríklad možné ukázať, že stredná hodnota počtu cyklov dĺžky k je presne 1/k (nezávisle na n). To znamená, že v priemere sa vygeneruje jeden cyklus dĺžky 1, "pol" cyklu dĺžky dva, atď. Z toho tiež okamžite plynie, že stredná hodnota počtu všetkých cyklov je n-té harmonické číslo H(n) . To je aj pre veľké n kontraintuitívne nízke číslo; napríklad stredný počet cyklov náhodnej permutácie milión čísiel je približne 14,4. Dá sa preto tušiť, že v náhodnej permutácií by sa mali s "veľkou pravdepodobnosťou" vyskytovať "veľké cykly". Skutočne to tak je; napríklad jednoduchým trikom je možné ukázať, že pravdepodobnosť výskytu cyklu obsahujúceho nadpolovičnú väčšinu čísiel je H(n)-H(n/2). (Pre jednoduchosť berieme n párne.) Hodnota H(n)-H(n/2) konverguje k číslu ln(2), čo je približne 0,693. To znamená, že pre veľké n vznikne s pravdepodobnosťou zhruba 70% v náhodnej permutácii n čísiel cyklus obsahujúci nadpolovičnú väčšinu čísiel.