A.S.: Da, se pare că singularul lui „dice” este „die”. 😉
O sarcină complicată de programare a circulat pe Internet care, după cum probabil ați ghicit din încercarea mea de a da un titlu pragmatic, poate fi formalizată după cum urmează:
Dată o funcție care returnează un număr uniform aleator între 1 și 5 (inclusiv), proiectați o funcție care returnează un număr uniform aleator între 1 și 7 (inclusiv).
Dacă intersecția dintre algoritmi și statistică este genul tău de lucru, nu ezita să încerci! O provocare în plus este să faceți ca algoritmul dvs. să fie mărginit în timp. Mi s-a părut un exercițiu amuzant, doar că mi-am dat seama că există limitări fundamentale în joc aici.
Desigur, un zar înseamnă aici un generator aleatoriu perfect uniform care există doar în teorie. Zarurile din lumea reală sunt guvernate de legile naturale și de imperfecțiunile mediului în așa fel încât ele sunt doar o aproximare (deși una bună) a acestui model abstract.
O soluție nemărginită
Să ne uităm la o familie de algoritmi nemărginită. Pentru a crea un generator aleator care să aibă cel puțin 7 rezultate, va trebui să aruncăm zarul cu 5 fețe de cel puțin două ori. Aruncându-l de două ori se creează 5^2=25 de rezultate posibile și, deși acesta nu este un factor de 7, putem atribui primele 21 de rezultate la 7 grupe de mărime egală cu 3. Totuși, dacă ajungem la unul dintre cele 4 rezultate rămase, atunci procedura trebuie reluată. Nu putem atribui pur și simplu oricare dintre aceste 4 stări finale ghinioniste unei ieșiri, deoarece acest lucru va da peste cap proprietatea uniformă de aleatorism.
În graficul de mai sus, cercurile reprezintă „stări” ale programului nostru, iar textul din interior reprezintă cea mai recentă valoare a zarului aruncat. Cutiile verzi reprezintă apoi ieșirea pe care o atribuim în funcție de starea finală (= după ce am aruncat zarul de două ori). În 84% din cazuri, obținem o ieșire după două aruncări și algoritmul se termină. După cum puteți vedea, o buclă este prezentă și face ca algoritmul să fie nemărginit. Acest lucru înseamnă că pentru fiecare număr întreg, indiferent cât de mare, există o probabilitate mică, dar diferită de zero, ca numărul total de aruncări să depășească această sumă pentru a calcula o valoare de ieșire. Prin urmare, aplicațiile în timp real cu cerințe stricte de timp ies din discuție, cu excepția cazului în care sunteți dispuși să faceți compromisuri în ceea ce privește acuratețea statistică a algoritmului.
O variantă a acestei soluții aruncă inițial până la trei zaruri înainte de a reporni: acest lucru creează 5^3=125 de stări finale, iar noi putem atribui cel mult 119 dintre ele la 7 grupuri de dimensiuni egale 17. Acum, există o probabilitate de 95,2% de a termina după un maxim de trei aruncări. Rețineți că, în medie, trebuie să aruncăm de mai puține ori decât înainte (280/119 ≈ 2,35 față de 50/21 ≈ 2,38), deoarece, de cele mai multe ori, putem deja să luăm o scurtătură după primele două aruncări și să cartografiem direct aceste stări intermediare la o ieșire. Această cantitate medie de rostogoliri continuă să scadă pe măsură ce continuăm tendința.
Dacă sunteți familiarizați cu teoria informației, atunci luați în considerare faptul că o aruncare a unui zar cu 5 fețe (= rand5) generează log2(5) ≈ 2,32 biți de informație, iar o aruncare a unui zar cu 7 fețe (= rand7) generează log2(7) ≈ 2,81 biți de informație. Se pare că, în cazul limită, avem nevoie doar de log(7)/log(5) ≈ 1,21 apeluri de rand5 pentru fiecare valoare rand7 pe care dorim să o obținem. Implementarea exactă care funcționează în mod arbitrar aproape de această limită este destul de complicată și iese din sfera de aplicare a acestui articol. Ar trebui să stocăm informații de stare între mai multe apeluri ale rand7, iar algoritmul pe care îl am în minte este încă nemărginit nu numai în timp, ci și în memorie. Vă invit cu plăcere să îmi comunicați o metodă care să rezolve această din urmă problemă!
O soluție mărginită
Nu există un algoritm mărginit care să calculeze o valoare aleatoare perfect uniformă între 1 și 7, dat fiind un generator aleator între 1 și 5 doar. Luați în considerare familia de soluții nemărginite de mai sus. Așa cum am sugerat, în fiecare punct va exista întotdeauna o cantitate de stări „rămase” (variind între 1 și 6) care determină repornirea algoritmului. Acest lucru se datorează faptului că 5 și 7 sunt numere prime și nicio putere a lui 5 nu poate fi vreodată multiplu de 7. Oricât de tentant ar fi să folosim mica teoremă a lui Fermat, astfel de încercări vor duce la erori „off-by-one”, deoarece teoria de bază a numerelor face imposibilă o soluție delimitată în această familie.
Ați putea sublinia, pe bună dreptate, că numărul de stări finale nu este întotdeauna o putere a lui 5, de exemplu în cazul „până la trei aruncări”, unde putem lua scurtături după două aruncări deja. Poate că am putea aranja graficul de stări astfel încât să creăm un algoritm mărginit cu căi de lungime variabilă și 7n stări finale? Totuși, luați în considerare următoarele:
- Aceste stări finale nu vor fi la fel de probabile, deoarece nu toate căile au aceeași lungime (= cantitatea de apeluri rand5).
- Pot fi foarte ușor să extindem arborele pentru a face ca fiecare cale să fie la fel de lungă, apelând inutil rand5 de un număr corespunzător de ori ori de câte ori ne aflăm într-o stare finală prematură. Acum, cantitatea de stări finale devine din nou o putere a lui 5, iar toate stările finale sunt la fel de probabile.
Desigur, aceasta nu este o demonstrație formală, dar sper că v-am dat o oarecare intuiție despre problemă. După cum vedem, uneori o problemă poate părea foarte realistă, doar pentru a da peste fapte matematice ca acestea. După această analiză, vă puteți da seama dacă este posibil să simulăm un zar cu 8 fețe pornind de la un zar cu 4 fețe?
.