thumb|upright=1.3|Probabilitatea calculată ca cel puțin două persoane să aibă aceeași zi de naștere, în funcție de numărul de persoane
În teoria probabilităților, problema zilei de naștere constă în determinarea probabilității ca, într-un grup de persoane alese aleatoriu, cel puțin două să aibă aceeași zi de naștere. Paradoxul zilei de naștere, cunoscut și sub denumirile de paradoxul aniversării sau paradoxul aniversărilor, desemnează rezultatul contraintuitiv potrivit căruia sunt suficiente numai 23 de persoane pentru ca această probabilitate să depășească 50%.
Paradoxul zilei de naștere este un paradox veridic: la prima vedere pare greșit, dar este, în realitate, adevărat. Deși poate părea surprinzător că sunt suficiente numai 23 de persoane pentru ca probabilitatea ca două dintre acestea să aibă aceeași zi de naștere să ajungă la 50%, număr mai mic decât a cincisprezecea parte din numărul zilelor unui an, rezultatul devine mai intuitiv dacă se ține seama de faptul că sunt comparate zilele de naștere ale tuturor perechilor posibile de persoane. Pentru 23 de persoane, există de perechi posibile.
Printre aplicațiile practice ale problemei zilei de naștere se numără un atac criptografic denumit atacul zilei de naștere, care utilizează acest model probabilistic pentru a reduce complexitatea determinării unei coliziuni a unei funcții hash, numită și funcție de dispersie, precum și estimarea riscului de apariție a unei coliziuni între valorile hash corespunzătoare unui număr dat de elemente.
Problema îi este atribuită, în general, lui Harold Davenport, care ar fi formulat-o în jurul anului 1927, fără a o publica atunci. Davenport nu a susținut că ar fi descoperitorul acesteia, „deoarece nu putea crede că nu fusese formulată anterior”.David Singmaster, Sources in Recreational Mathematics: An Annotated Bibliography, Eighth Preliminary Edition, 2004, secțiunea 8.BH. S. M. Coxeter, „Mathematical Recreations and Essays, 11th edition”, 1940, p. 45, citat în I. J. Good, Probability and the weighing of evidence, 1950, p. 38 Prima versiune publicată a problemei zilei de naștere îi aparține lui Richard von Mises și datează din 1939.Richard Von Mises, „Über Aufteilungs- und Besetzungswahrscheinlichkeiten”, Revue de la faculté des sciences de l'Université d'Istanbul 4:145–163, 1939, republicată în
Calcularea probabilității Fie evenimentul potrivit căruia, într-un grup de persoane, toate zilele de naștere sunt distincte și fie evenimentul complementar, potrivit căruia cel puțin două dintre cele persoane au aceeași zi de naștere. Probabilitățile și ale celor două evenimente satisfac relația . Probabilitatea poate fi calculată cu ajutorul aranjamentelor fără repetiție, după cum urmează. Fie numărul total de moduri în care cele persoane pot avea zile de naștere distincte și fie numărul total de moduri în care pot fi distribuite zilele lor de naștere, inclusiv situațiile în care acestea se repetă. Probabilitatea este raportul dintre cele două numere, adică împărțit la . Pentru , cele două valori sunt
și
raportul acestora este , astfel încât
Problema zilei de naștere poate fi abordată și prin determinarea probabilității aproximative ca, într-un grup de persoane, cel puțin două să aibă aceeași zi de naștere. Pentru simplificare, se neglijează, în general, anii bisecți, gemenii, eroarea sistematică de selecție și variațiile sezoniere sau săptămânale ale natalității. Se presupune, în schimb, că există 365 de zile de naștere posibile și că ziua de naștere a fiecărei persoane poate coincide cu oricare dintre acestea cu aceeași probabilitate, independent de zilele de naștere ale celorlalte persoane din grup.
În ipoteza independenței zilelor de naștere, o distribuție uniformă minimizează probabilitatea ca două persoane dintr-un grup să aibă aceeași zi de naștere. Orice abatere de la uniformitate crește probabilitatea unei asemenea coincidențe. Totuși, distribuția reală a zilelor de naștere nu este suficient de neuniformă pentru a modifica semnificativ rezultatul: și în realitate sunt necesare 23 de persoane pentru ca probabilitatea ca două dintre ele să aibă aceeași zi de naștere să depășească 50%, la fel ca în modelul teoretic bazat pe distribuția uniformă.
Se urmărește calcularea probabilității ca cel puțin două persoane din încăpere să aibă aceeași zi de naștere. Este însă mai simplu să se calculeze , probabilitatea ca toate persoanele din încăpere să aibă zile de naștere diferite. Deoarece și sunt singurele două posibilități și constituie evenimente incompatibile, rezultă că
Pentru calculul acestei probabilități în cazul a 23 de persoane, acestea sunt numerotate de la 1 la 23. Evenimentul potrivit căruia toate cele 23 de persoane au zile de naștere diferite este echivalent cu îndeplinirea simultană a următoarelor condiții: persoana 2 nu are aceeași zi de naștere ca persoana 1, persoana 3 nu are aceeași zi de naștere ca persoana 1 sau persoana 2 și așa mai departe, până când persoana 23 nu are aceeași zi de naștere ca niciuna dintre persoanele 1–22. Aceste evenimente sunt denumite Evenimentul 2, Evenimentul 3 și așa mai departe. Evenimentul 1 constă în faptul că persoana 1 are o zi de naștere, ceea ce se realizează cu probabilitatea 1. Intersecția acestor evenimente poate fi analizată cu ajutorul probabilităților condiționate: probabilitatea Evenimentului 2 este , deoarece ziua de naștere a persoanei 2 poate fi oricare dintre cele 364 de zile diferite de ziua de naștere a persoanei 1. În mod similar, probabilitatea Evenimentului 3, condiționată de realizarea Evenimentului 2, este , deoarece persoana 3 poate avea oricare dintre zilele de naștere neocupate de persoanele 1 și 2. Procesul continuă până la Evenimentul 23, a cărui probabilitate, condiționată de realizarea tuturor evenimentelor precedente, este . Prin regula înmulțirii probabilităților condiționate, este egală cu produsul acestor probabilități:
Prin gruparea termenilor ecuației (), se obține:
Calcularea ecuației () conduce la .
Prin urmare, (50,7297%).
Raționamentul poate fi generalizat pentru un grup de persoane, unde reprezintă probabilitatea ca cel puțin două dintre acestea să aibă aceeași zi de naștere. Este mai simplu să se calculeze mai întâi probabilitatea complementară ca toate cele zile de naștere să fie distincte. Conform principiului cutiei, este egală cu zero atunci când . Dacă , atunci:
unde reprezintă factoriala, este coeficientul binomial, iar reprezintă numărul de aranjamente fără repetiție.
Ecuația exprimă faptul că prima persoană poate avea orice zi de naștere, a doua nu poate avea aceeași zi de naștere ca prima , a treia nu poate avea aceeași zi de naștere ca niciuna dintre primele două , iar, în general, ziua de naștere a celei de-a -a persoane nu poate coincide cu niciuna dintre cele zile de naștere precedente.
Evenimentul potrivit căruia cel puțin două dintre cele persoane au aceeași zi de naștere este complementar evenimentului potrivit căruia toate cele zile de naștere sunt distincte. Prin urmare, probabilitatea sa este
Tabelul următor prezintă probabilitatea pentru diferite valori ale lui ; se ignoră anii bisecți și se presupune că toate zilele de naștere sunt echiprobabile:
thumb|right|upright=1.4|Probabilitatea ca, într-un grup de persoane, toate zilele de naștere să fie distincte. Scara verticală este logaritmică: fiecare treaptă descendentă corespunde unei probabilități de 1020 de ori mai mici.
{| class="wikitable" !!! |- |align=right|1 || 0,0% |- |align=right|5 || 2,7% |- |align=right|10 || 11,7% |- |align=right|20 || 41,1% |- |align=right|23 || 50,7% |- |align=right|30 || 70,6% |- |align=right|40 || 89,1% |- |align=right|50 || 97,0% |- |align=right|60 || 99,4% |- |align=right|70 || 99,9% |- |align=right|75 || 99,97% |- |align=right|100 || % |- |align=right|200 || (100 − )% |- |align=right|300 || (100 − )% |- |align=right|350 || (100 − )% |- |align=right|365 || (100 − )% |- |align=right|≥ 366 || 100%
Aproximări thumb|right|upright=1.4|Graficele probabilității aproximative ca cel puțin două persoane să aibă aceeași zi de naștere () și ale probabilității evenimentului complementar () thumb|right|upright=1.4|Grafic care ilustrează precizia aproximării 1 − e−n2/730 () Dezvoltarea în serie Taylor a funcției exponențiale, unde ,
permite obținerea unei aproximări de ordinul întâi pentru , atunci când :
Pentru aplicarea acestei aproximări la prima expresie obținută pentru , se consideră . Rezultă:
Apoi, pentru fiecare termen din formula lui , este înlocuit succesiv cu numere întregi nenegative, până la . De exemplu, pentru ,
Prin urmare, prima expresie obținută pentru poate fi aproximată astfel:
În consecință,
O aproximare mai puțin precisă este
care, după cum arată graficul, rămâne totuși destul de exactă.
Aceeași metodă de aproximare poate fi aplicată unui număr arbitrar de „persoane” și „zile”. Dacă numărul zilelor disponibile este , numărul persoanelor este , iar , atunci probabilitatea ca cel puțin două dintre cele persoane să aibă aceeași zi de naștere dintre cele zile disponibile este aproximativ:
Ridicarea simplă la putere Probabilitatea ca două persoane date să nu aibă aceeași zi de naștere este . Într-un grup de n persoane există perechi de persoane, adică evenimente. Probabilitatea ca nicio pereche să nu aibă aceeași zi de naștere poate fi aproximată presupunând că aceste evenimente sunt independente și înmulțind probabilitățile lor. Independența ar fi echivalentă cu selectarea cu repunere a oricărei perechi de persoane din întreaga populație, nu doar din grupul analizat. Astfel, se ridică la puterea , obținându-se
Deoarece aceasta reprezintă probabilitatea ca toate zilele de naștere să fie distincte, probabilitatea ca cel puțin două persoane să aibă aceeași zi de naștere este
Pentru un grup de 23 de persoane, probabilitatea unei coincidențe este
Aproximarea Poisson Aplicând aproximarea distribuției binomiale prin distribuția Poisson pentru un grup de 23 de persoane, se obține
și, prin urmare,
Rezultatul depășește 50%, la fel ca în aproximările precedente. Această aproximare coincide cu cea obținută anterior prin dezvoltarea în serie Taylor și utilizarea relației .
Aproximarea pătratică O regulă empirică utilă pentru calculul mintal este relația
care poate fi scrisă și sub forma
și oferă rezultate satisfăcătoare pentru probabilități mai mici sau egale cu . În aceste ecuații, reprezintă numărul de zile ale unui an.
De exemplu, pentru estimarea numărului de persoane necesar astfel încât probabilitatea ca două persoane să aibă aceeași zi de naștere să fie , se obține
Rezultatul nu diferă foarte mult de valoarea exactă, care este de 23 de persoane.
Aproximarea numărului de persoane Numărul minim de persoane necesar pentru ca probabilitatea unei coincidențe să fie de cel puțin poate fi aproximat și prin formula:
Aceasta rezultă din aproximarea potrivit căreia un eveniment cu probabilitatea are o probabilitate de de a se produce cel puțin o dată dacă experimentul este repetat de ori.
Tabelul probabilităților
{| class="wikitable" style="white-space:nowrap;" |- ! rowspan="2" | lungimeașirului hexazecimal ! rowspan="2" | numărulde biți() ! rowspan="2" | dimensiunea spațiuluivalorilor hash() ! colspan="10" | Numărul de elemente necesar pentru ca probabilitatea existenței cel puțin unei coliziuni hash să fie ≥ |- ! = ! = ! = ! = ! = ! = 0,001 ! = 0,01 ! = 0,25 ! = 0,50 ! = 0,75 |- align="center" | bgcolor="#F2F2F2" | 8 | bgcolor="#F2F2F2" | 32 | bgcolor="#F2F2F2" | | 2 | 2 | 2 | 2,9 | 93
|- align="center" | bgcolor="#F2F2F2" | (10) | bgcolor="#F2F2F2" | (40) | bgcolor="#F2F2F2" | () | 2 | 2 | 2 | 47
|- align="center" | bgcolor="#F2F2F2" | (12) | bgcolor="#F2F2F2" | (48) | bgcolor="#F2F2F2" | () | 2 | 2 | 24
|- align="center" | bgcolor="#F2F2F2" | 16 | bgcolor="#F2F2F2" | 64 | bgcolor="#F2F2F2" | | 6,1
|- align="center" | bgcolor="#F2F2F2" | (24) | bgcolor="#F2F2F2" | (96) | bgcolor="#F2F2F2" | ()
|- align="center" | bgcolor="#F2F2F2" | 32