Rođendanski paradoks

mini|desno|300px|Grafik prikazuje funkciju porasta vjerovatnoće da bar dvije osobe imaju isti rođendan, u odnosu na broj odabranog uzorka osoba. ***x-osa*** - *Broj osoba;*  ***y-osa*** - *Vjerovatnoća;*
**Rođendanski paradoks** često nazvan i *rođendanski problem* je primjer pogrešne procjene u vjerovatnoći, u kojem se intuitivno dolazi do pogrešnog zaključka. Razlozi pogrešne procjene, objašnavaju se sklonošću ljudskog načina razmišljanja i prihvaćanja linearne funkcije, te nesposobnosti poimanja eksponencijalne funkcije.

Do pogrešne procjene u rođendanskom paradoksu dolazi, jer je postavljeno pitanje, kolika je vjerovatnoća, da dvije neovisno odabrane osobe iz jedne grupe imaju isti proizvoljno odabrani rođendan. Često se ovo pitanje tumači, kao - sa kolikom vjerovatnoćom se može tvrditi da jedna određena osoba iz jedne grupe ima na jedan određeni dan rođendan (npr. u odnosu na rođendan neke druge osobe), te je ta vjerovatnoća u stvarnosti mnogo niža.

Paradoks se često pripisuje Richard von Mises, a po Donaldu E. Knuthu ovaj izvor nije siguran: Ovaj se paradoks u matematici pojavljuje 1930-ih godina, ali inicijator paradoksa nije poznat.

## Objašnjenje 
***Pitanje:** Kolika je vjerovatnoća da od 23 osobe najmanje dvije osobe imaju rođendan u isti dan?* 
***Odgovor:** Odgovor je obično iznenađujući i vodi ka paradoksu. Većina ljudi procjenjuje vjerovatnoću za deset potencija niže nego što je ustvari. Odgovori se kreću između 1&nbsp;% und 5&nbsp;%, dok je prava vjerovatnoća preko 50&nbsp;%, a kod 50 osoba čak iznad 97&nbsp;%.

Za razliku od ovog primjera, vjerovatnoća da neko ima rođendan na neki određeni dan (bez obzira na godinu rođenja), a u usporedbi sa primjerom od 23 osobe, rođendan jedne od tih osoba, je mnogo niža. Da bi vjerovatnoća bila u istom opsegu, računato po binomskoj raspodjeli potrebno je još 231 osoba (ukupno 254).

### Teoretski pristup 
Razlog za ovako veliku razliku je da se od n osoba može napraviti \tfrac{n(n-1)}{2} različitih parova; Broj mogućih parova raste sve brže sa rastećim brojem osoba u grupi, te ako u grupu dođe još (n+1) osoba po redu, broj se parova povećava za n. Uslov za ispunjenje pitanja je već ispunjen, ako se uspostavi jedan jedini par sa istim rođendanom. Kako je vjerovatnoća, imati na isti dan rođendan, za svaki par jednaka, broj parova sa povećanjem broja osoba brzo raste, povećava se i vjerovatnoća, da dvije osobe u jednoj grupi imaju isti dan, direkto sa povećanjem veličine grupe.

### Praktični pristup 
U stvarnosti broj rođenih po datumima nije ravnomjeran po danima. Tako je poznato da se ljeti rađa više djece nego zimi. Time je i vjerovatnoća višlja, da osobe iz tog perioda imaju na isti dan rođendan. Kako broj rođenih zavisi i takođe od klimatskih, socijalnih i društvenih prilika, ta je raspodjela uglavnom neravnomjena. Simulacije, na osnovu stvarnih podataka, pokazuju da vjerovatnoća rođendana u isti dan, u grupi od 23 osobe uvijek prelazi 50&nbsp;%. Takođe uračunavanjem prestupne godine i 29. februara, ne mijenja statističku vrijedost vjerovatnoće. Tako je npr. po podacima Statističkog zavoda Austrije broj rođenih u Austriji najveći krajem septembra, a najniži krajem decembra.
## Značaj u kriptografiji 
## Matematičko objašnjenje 
Slijedeći dokaz je proračun vjerovatnoće, sa zanemarivanjem 29. februara, koji uzima rođendane neodređenog broja osoba n, kao ravnomjerno raspoređenu slučajnu varijablu iz direktne ravnomjerne raspodjele iz skupa elemenata (D-datum) sa 365 članova D={1. jan., 2. jan., …, 31. dec.} Ovaj dokaz ne vrijedi, ako se u skupu n osoba nalaze blizanci rođeni istog dana.

### Vjerovatnoća da dvije osobe imaju rođendan isti dan 
mini|380px|p(n) = *Vjerovatnoća za najmanje jedan dvostruki rođendan* 
q(n) = *Vjerovatnoća da se jedan rođendan poklapa sa unapred definiranim rođendanom* ***x-osa*** - *Broj osoba;*  ***y-osa*** - *Vjerovatnoća;*
Broj svih kombinacija za n osoba je *m*&nbsp;=&nbsp;365*n*, gdje sve varijante parova imaju istu vjerovatnoću. Tako npr. za dvije osobe broj kombinacija iznosi 3652&nbsp;=&nbsp;13.322.

Od ovih mogućih slučajeva
: u = 365 \cdot 364 \cdots (365-(n-1))
su broj različitih rođendana. Za prvu osobu iz skupa se može odabrati rođendan, za drugu je to 364 dana, u kojima prvoj osobi nije rođendan.

Na osnovu Laplasove formule, vjerovatnoća da sve osobe n imaju različite rođendane iznosi: 
: \frac{u}{m} = \frac{365 \cdot 364 \cdots (365-(n-1))}{365^n},

Za broj osobe n = 23 korištenjem ove formule dobije se:  
:1 - \frac{365 \cdot 364 \cdots 343}{365^{23}} \approx 0{,}5073 > 0{,}5.

Po Dirichletovom principu kutija, a isključivanjem 29. februara za sve slučajave n > 365. je vjerovatnoća jednaka 1, što znači da se sa sigurnošču može tvrditi da u definisanom skupu postoje dvije osobe sa istim rođendanom. Ukoliko se 29. februar takođe računa, ovaj princip vrijedi za n = 366.

#### Aproksimacija 
Izraz P se aproksimativno može pojednostaviti kao:
:P = 1-\frac{u}{m} = 1-\frac{365!}{(365-n)!\cdot365^n} = 1-\frac{n!\cdot{365 \choose n}}{365^n}.

a sa Stirlingovom formulom, može se približno izračunati i preko džepnog računara:
:P \approx 1 - \left(\frac{365}{365-n}\right)^{365.5 - n}\!\!\!\!\!\cdot\, e^{-n},

### Vjerovatnoća za jedan određeni rođendan 
Ako želimo izračunati vjerovatnoću za jedan određeni datum, te sa izostavljanjem 29. februara, onda je vjerovatnoća da jedna osoba ima isti rođendan, na jedan određeni definisani dan jednaka 1/365 ≈ 0,27 %.
Suprotna vjerovatnoća, odnosno vjerovatnoća da ta osoba nema rođenadan na taj dan je:
: q = 1-\frac 1 {365}\approx99{,}73\,\%.

U daljem slijedu, je vjerovatnoća da dvije osobe nemaju rođendan na taj dan je q^2\,

Da bi najmanje jedna osoba od dvije, imala rođendan na taj dan, je suprotna vjerovatnoća gornjeg izraza :
: P = 1-q^2.\,

Time je moguće izračunati, koliko osoba n je potrebno, za ostvarivanje jedne određene vjerovatnoće *P*, da barem jedna osoba ima rođendan na taj dan:

: \left(1-\frac 1 {365}\right)^n = 1-P

: \Leftrightarrow n = \frac{\ln(1-P)}{\ln(1-\frac 1 {365})}.

odnosno za vjerovatnoću od 50&nbsp;% potrebno je

: n \ge \frac{\ln(\frac 1 2)}{\ln(\frac{364}{365})} \approx 253\, osoba.

Vjerovatnoća za slučaj da jedna od  n osoba ima rođendan kao i druga osoba od preostalih n-1 je:
:1-q^{n-1}.\,

Za razliku od vjerovatnoće, kao ugornjem primjeru, da najmanje dvije osobe imaju rođendan na isti dan, ne postoji broj  *n*, za koji se sa sigurnošću može tvrditi da za svaki određeni broj osoba, izabrani dan nije rođendan tih osoba. Za sve osobe *n* vrijedi
: P = 1-q^n 

## Slični problemi 
Sličan problem je u memorijskoj igri Memory, gdje je cilj otkriti dvije iste karte, koje leže sa naličjem na stolu. Na početku igre, sve karte leže pokrivene, a cilj je igre okretanjem dviju karata naći isti par. Ovim se pravilom postavlja pitanje, koliko karata se mora otkriti da bi se sa nekom određenom vjerovatnoćom (50&nbsp;%) moglo tvrditi da će otkrivene karte biti sa istim sadržajem.

Broj *N*  označava broj različitih motiva karata i odgovara broju dana u godini (365) u rođendanskom paradoksu. Obično se igra Memory igra sa 32 para, ali moguće su i druge varijante, te se broj *N* može smatrati promjenljivim.

Definisanjem vjerovatnoće sa otkrivanjem broja karti *n* kao P^\text{Mem}_N(n), u funkciji broja karti *N*, vrijednost se izračunava:

: P^\text{Mem}_N(n) = \frac{2N}{2N}\cdot\frac{2(N-1)}{2N-1}\cdot\frac{2(N-2)}{2N-2}\cdots \frac{2(N-n+1)}{2N-n+1}.

te za vrijednosti *N = 32* sa 10 otkrivenih karti, može se sa vjerovatnoćom većom od 50&nbsp;% tvrditi da će se otkriti dvije iste karte
:(*1 - P32(10)* = 56,4 %). 
Za vrijednost *N=50* broj potrebnih karata je 12, a kod jedne hipotetički zamišljene igre sa 183 para, morale bi se otkriti 23 karte, kod 356 parova su 32 karte neophodne.

## Također pogledajte 
* Problem sa skupljanjem sličica - gdje se analizira potreban broj sakupljenih sličica, da se sa odrešenom vjerovatnoćom može tvrditi, da su sve sličice u posjedu. Prenesno na rođendanski paradoks - postavlja se pitanje koliko osoba mora biti izabrano, da bi se moglo tvrditi da za svaki dan u godini postoji osoba sa rođendanom.
* Lincoln-Kennedyjeva misterija

## Napomene 
## Reference 
## Vanjski linkovi 
* *The art of computer programming: Sorting and searching'' birthday+paradox 

Kategorija:Paradoksi teorije vjerovatnoće
Kategorija:Rođendani
Kategorija:Matematički problemi
Kategorija:Koincidencija