Problema saptamanii - Probabilitati (solutie)

Cosmin
Cosmin Negruseri
20 noiembrie 2008

Problema curenta a fost rezolvat de Ovidiu Gheorghioiu, Delia David, Andrei Olariu si de Radu Grigore.

Nu exista nici o modalitate prin care sa obtinem rezultate uniform aleatoare folosind un numar finit de aruncari pentru ca se poate intampla ca la orice aruncare a monedei sa obtinem cap la infinit si atunci nu avem cum sa obtinem rezultate diferite.

Solutiile lui Andrei:

1. Se arunca moneda de cate 2 ori. Daca pica pajura si apoi cap -> pajura, daca avem cap si apoi pajura -> cap, daca avem 2 rezultate egale, repetam ambele aruncari.

2. Generam doua numere din multimea {0, 1} folosind metoda de la pct 1. Obtinem 00 -> mar, 01 -> para, 10 -> portocala, 11 -> repetam cele 2 generari.

Prima problema are mai mult de 50 de ani fiind rezolvata de unul dintre pionierii informaticii, John Von Neumann

A doua e interesanta in contextul generatoarelor de numere aleatoare. De exemplu in C++ unii folosim, pentru a genera numere aleatoare de la 0 la n - 1, instructiunile rand() % n. Acum dupa ce ati vazut problema 2 este clar ca unele rezultate sunt mai probabile ca altele.

In java sau Python generatoarele aleatoare sunt mai bune.

Varianta implementata in java:

public int nextInt(int n) {
     if ((n & -n) == n)  // i.e., n is a power of 2
         return (int)((n * (long)next(31)) >> 31);

     int bits, val;
     do {
         bits = next(31);
         val = bits % n;
     } while(bits - val + (n-1) < 0);
     return val;
 }

puteti citi aici explicatia codului.

O varianta care foloseste ceva mai multe dintre rezultatele aruncarilor pentru prima problema ar fi sa consideram si rezultatele de genul cap, cap, pajura, pajura ca 0 si pajura, pajura, cap, cap ca 1 si asa mai departe.

Ovidiu sugera urmatoarea generalizare pentru problema 2: Care e numarul mediu maxim de numere aleatoare intre 0 si k - 1 pe care le putem obtine dintr-un stream de biti uniform aleatori.

Categorii: potw
remote content