O permutație aleatorie de mărime N, este o permutație luată uniform în setul de permutații de mărime N.
Mulți parametri au fost studiați pe permutații aleatorii, de exemplu, numărul mediu de puncte fixe sau lungimea ciclurilor. Mai mulți algoritmi exista pentru a genera permutări aleatoare de la un generator de numere aleatoare, de exemplu amestecul Fisher-Yates .
În așteptarea dezvoltării acestei secțiuni, consultați secțiunile
În așteptarea dezvoltării acestei secțiuni, consultați secțiunile
De exemplu, cea mai lungă subsecvență în creștere a permutării (15423) este (123) de lungimea 3. Legea acestei lungimi este legată de percolarea ultimei treceri în pătrat.
În așteptarea dezvoltării acestei secțiuni, ne putem referi la paginile următoare
Să fie o secvență de variabile aleatoare IID cu densitate , definită pe un spațiu probabilized Pentru orice număr întreg k între 1 și n , să
Astfel, este interpretat ca rangul din eșantion, odată ce este aranjat în ordine crescătoare.
Propunere - Harta este o permutare uniformă aleatorie.
Vom găsi aici o dovadă a propoziției de mai sus în cazul în care distribuția probabilității comune variabilelor este legea uniformă pe [0,1] . Putem, de fapt, să fim mulțumiți de variabile iid a căror lege este difuză (fără atomi) modulo o modificare minoră a dovezii. Cu toate acestea, legea uniformă este deosebit de convenabilă pentru diverse aplicații.
Amestecul de Fisher-Yates , de asemenea , numit de amestecare Knuth , este un algoritm stabilit pentru a aplica o permutare aleatoare n în elemente timp liniar, n ! permutările posibile fiind echipabile la ieșire.
Principiul acestui algoritm este după cum urmează:
pour i de n - 1 descendant_à 1 : j ← nombre aléatoire entier 0 ≤ j ≤ i échanger a[j] et a[i]