Doğum günü problemi sayfasının kaynağını görüntüle

{{çoklu sorun|
{{düzenle|tarih=Mart 2020}}
{{teknik|tarih=Mart 2020}}
}}
[[Olasılık teorisi]]nde, '''doğum günü problemi''' veya '''doğum günü paradoksu''', ''n'' adet [[rastgele]] seçilmiş kişiden oluşan bir grup içindeki bazı çiftlerin [[doğum günü]]nün aynı olma olasılığını inceler. [[Güvercin deliği ilkesi]]ne göre, kişi sayısı 367'ye ulaştığında (29 Şubat dahil, 366 adet olası doğum günü olduğu için) olasılık %100'e ulaşır fakat, %99,9 olasılığa sadece 70 kişi ile ve %50 olasılığa 23 kişi ile ulaşılır. Bu sonuçlar, yılın her gününün (29 Şubat hariç) eşit derecede olası bir doğum günü olduğu varsayımına dayanır.

Mevcut doğum kayıtları farklı günlerde farklı sayıda insanın doğduğunu gösterir. Bu durumda, %50 eşiğine ulaşmak için gereken insan sayısının 23 veya daha az olduğu söylenebilir.<ref name="Borja">{{Akademik dergi kaynağı |yazar1 = Mario Cortina Borja |yazar2 = John Haigh |başlık= The Birthday Problem |dergi= Significance |tarih= September 2007 |cilt= 4 |sayı= 3 |sayfalar=124-127|yayıncı= Royal Statistical Society |doi= 10.1111/j.1740-9713.2007.00246.x|doi-access = ücretsiz}}</ref> Örneğin, insanların yarısı bir günde ve diğer yarısı başka bir günde doğmuş olsaydı, bu durumda herhangi iki kişinin doğum gününü paylaşma şansı %50 olurdu.

Gruptaki en az iki kişinin aynı doğum gününe sahip olma olasılığının %50'ye ulaşılması için sadece 23 kişilik bir grubun gerektiği şaşırtıcı görünebilir: bu sonuç, bir bireye sabitlenmenin ve onun doğum gününü diğerleriyle karşılaştırmanın aksine doğum günü karşılaştırmasının aslında, olası her bir çift arasında = 23 x 22/2 = 253 karşılaştırma -bir yıl içindeki gün sayısının yarısından (en fazla 183) daha çok- yapılmasıyla daha makul olabilir. Doğum günü problemi kendisiyle mantıksal çelişkili olma anlamda bir “[[paradoks]]” değildir, ancak ilk bakışta anlaşılamaz.

Doğum günü probleminin gerçek hayattaki uygulamaları arasında doğum günü saldırısı isimli bir [[kriptografi]]k saldırı vardır; bu saldırı bu olasılık modelini kullanarak bir [[özet fonksiyonu]] için çarpışma bulma karmaşıklığını azaltır ve büyüklüğü belirli bir popülasyonun özetleri arasında bulunan bir özet çarpışmasının yaklaşık riskini hesaplar.

Problemin tarihi bilinmemektedir. W. W. Rouse Ball, bunun ilk olarak Harold Davenport<ref name="ReferenceA">{{Kitap kaynağı|editör1-ad=P.|editör6-ad=G.|yayıncı=Amer. Math. Soc.|tarih=1964|sayfalar=313-334|cilt=2|başlık=Selected Papers of Richard von Mises|editör6-soyadı=Birkhoff|editör5-soyadı=Szegö|editör1-soyadı=Frank|editör5-ad=G.|editör4-soyadı=Prager|editör4-ad=W.|editör3-soyadı=Kac|editör3-ad=M.|editör2-soyadı=Goldstein|editör2-ad=S.|yer=Providence, Rhode Island}}</ref>  tarafından ele alındığını belirtmiştir (alıntı yok). Ancak, Richard von Mises, bugün doğum günü problemi olarak bilinen şeyin daha eski bir versiyonunu sunmuştur. <sup><ref name="ReferenceA"/></sup> 
[[Dosya:Birthday_Paradox.svg|alt=|küçükresim|En az iki kişinin doğum günü paylaşma olasılığına karşı kişi sayısı]]

== Olasılığın hesaplanması ==
Problem, ''n'' kişiden oluşan bir grup içindeki en az iki kişinin doğum gününün aynı olma olasılığını yaklaşık olarak hesaplamaktır. Basitlik adına, [[artık yıl]]lar, [[İkizler (tıp)|ikizler]], sezonluk veya iş günü değişiklikleri gibi dağılımdaki değişimler göz ardı edilmiştir ve 365 olası doğum gününün hepsinin eşit derecede olası olduğu varsayılmıştır. (Gerçekte doğum günü dağılımları düzenli değildir çünkü tüm tarihler eşit derecede olası değildir, fakat bu düzensizliklerin analiz üzerinde çok az etkisi vardır{{refn|In reality, birthdays are not evenly distributed throughout the year; there are more births per day in some seasons than in others, but for the purposes of this problem the distribution is treated as uniform. In particular, many children are born in the summer, especially the months of August and September (for the northern hemisphere) [http://scienceworld.wolfram.com/astronomy/LeapDay.html], and in the U.S. it has been noted that many children are conceived around the holidays of [[Christmas]] and [[New Year's Day]].<ref name="Borja" /> Also, because hospitals rarely schedule [[caesarian section]]s and [[induced labor]] on the weekend, more people are born between Tuesday and Friday than on weekends;<ref name="Borja" /> where many of the people share a birth year (e.g. a class in a school), this creates a tendency toward particular dates. In Sweden 9.3% of the population is born in March and 7.3% in November when a uniform distribution would give 8.3% [http://www.scb.se/statistik/BE/BE0101/2006A01a/BE0101_2006A01a_SM_BE12SM0701.pdf Swedish statistics board]. See also:
* {{Web kaynağı | soyadı = Murphy | ad = Ron | başlık = An Analysis of the Distribution of Birthdays in a Calendar Year | erişimtarihi = 27 Aralık 2011 | url = http://www.panix.com/~murphy/bday.html | arşivurl = https://web.archive.org/web/20010526234141/http://www.panix.com/~murphy/bday.html | arşivtarihi = 26 Mayıs 2001 | ölüurl =evet}}
* {{Dergi kaynağı
|doi= 10.1093/ije/12.3.326
| cilt = 12
| sayı = 3
| sayfalar =326-331| soyadı = Mathers
| ad = C D
| yazar2 = R S Harris
| başlık = Seasonal Distribution of Births in Australia
| dergi = International Journal of Epidemiology
| erişimtarihi = 27 Aralık 2011
| yıl = 1983
| url = http://ije.oxfordjournals.org/content/12/3/326.abstract
| pmid = 6629621
|arşivurl= https://web.archive.org/web/20120223085148/http://ije.oxfordjournals.org/content/12/3/326.abstract
|arşivtarihi= 23 Şubat 2012
| ölüurl = hayır
}}
These factors tend to increase the chance of identical birth dates, since a denser subset has more possible pairs (in the extreme case when everyone was born on three days, there would obviously be many identical birthdays). The problem of a non-uniform number of births occurring during each day of the year was first understood by [[Murray Klamkin]] in 1967. A formal proof that the probability of two matching birthdays is least for a uniform distribution of birthdays was given by Bloom {{Harv|Bloom|1973}}.|group=nb|name="nonuniform birthdays"}}. Aslında, doğum günlerinin düzenli dağılımı en kötü durumdur.<sup><ref>{{Kitap kaynağı|url=http://books.google.com/books?id=7GDyRMrlgDsC&printsec=frontcover&dq=isbn:9780521546775&hl=&cd=1&source=gbs_api|başlık=The Cauchy‑Schwarz Master Class|erişimtarihi=|tarih=2004|dil=İngilizce|sayfa=|sayfalar=206, 277|çalışma=|yer=Cambridge|yayıncı=Cambridge University Press|isbn=9780521546775|yazar1=J. Michael Steele|arşivurl=https://web.archive.org/web/20130516234900/http://books.google.com/books?id=7GDyRMrlgDsC|arşivtarihi=16 Mayıs 2013|ölüurl=hayır}}</ref></sup>)

Amaç, P(A) ile ifade edilen, odadaki en az iki kişinin doğum gününün aynı olma olasılığını hesaplamaktır. Ancak, P(A') ile ifade edilen, odadaki hiç kimsenin doğum gününün aynı olmama olasılığını hesaplamak daha kolaydır. Bu durumda, sadece A ve A' olasılık dahilinde ve [[Ayrık Olay Simülasyonu|ayrık olaylar]] olduğu için, P(A)=1-P(A').

P(A)’nın %50’den fazla olması için gereken kişi sayısının en az 23 olduğunu belirten yaygın çözümleri dikkate alarak, aşağıdaki P(A) hesaplamasında örnek olarak 23 kişi kullanılacaktır. Eğer 23 kişi 1’den 23’e kadar numaralandırılırsa, 23 kişinin hepsinin farklı doğum günlerine sahip olması olayı, 2. kişinin 1. kişi ile aynı doğum gününe sahip olmama [[olay]]ı ile ve 3. kişinin 1. ve 2. kişiyle aynı doğum gününe sahip olmama olayı, vb.; ve son olarak 23. kişinin 1’den 22’ye kadar olan kişilerin hiçbiri ile aynı doğum gününe sahip olmama olayı ile aynıdır. Bu olaylar sırasıyla “Olay 2”, “Olay 3” vb. olarak isimlendirilsin. “Olay 1” olarak ise, 1. kişinin doğum gününe sahip olma olayı ki bu olayın olasılığı 1'dir, eklenebilir. Bu olayların birleşimi [[koşullu olasılık]] kullanılarak hesaplanabilir: Olay 2'nin olasılığı 364/365'tir, çünkü 2. kişinin doğum günü, 1. kişinin doğum günü dışındaki herhangi bir günde olabilir. Benzer şekilde, Olay 2'nin gerçekleştiği göz önüne alındığında, Olay 3'ün olasılığı 363/365'tir, çünkü 3. kişinin doğum günü 1. ve 2. kişinin doğum günleri dışında her gün olabilir. Bu, önceki tüm olayların gerçekleştiği göz önüne alındığında, Olay 23'ün olasılığı 343/365 olana kadar devam eder. Son olarak, koşullu olasılık prensibi, P(A')’nın bu ayrı olasılıkların çarpımına eşit olduğunu belirtir: {{NumBlk|:|<math>P(A')=\frac{365}{365}\times\frac{364}{365}\times\frac{363}{365}\times\frac{362}{365}\times\cdots\times\frac{343}{365}</math>|{{EquationRef|1}}}} Denklem ( {{Denklem notu|1}} )’in terimleri tek tarafta toplanırsa: {{NumBlk|:|<math>P(A')=\left(\frac{1}{365}\right)^{23}\times(365\times364\times363\times\cdots\times343)</math>|{{EquationRef|2}}}} Denklem ( {{Denklem notu|2}} ) çözümü  {{Matematik|''P''(''A''′) ≈ 0.492703}}'ü verir.

Bu nedenle, {{Matematik|''P''(''A'') ≈ 1 − 0.492703 {{=}} 0.507297}} &nbsp; (50,7297%).

Bu yöntem n kişiden oluşan bir grup için genelleştirilebilir, p(n) n kişiden en az iki kişinin bir doğum günü paylaşması olasılığıdır. Öncelikle, tüm n doğum günlerinin farklı olma olasılığını, ''p''(''n''), hesaplamak daha kolaydır. Güvercin yuvası prensibine göre, n>365 ise ''p''(''n)'' sıfırdır. n ≤ 365 ise:

: <math> \begin{align} \bar p(n) &= 1 \times \left(1-\frac{1}{365}\right) \times \left(1-\frac{2}{365}\right) \times \cdots \times \left(1-\frac{n-1}{365}\right) \\[6pt] &= \frac{ 365 \times 364 \times \cdots \times (365-n+1) }{ 365^n } \\[6pt] &= \frac{ 365! }{ 365^n (365-n)!} = \frac{n!\cdot\binom{365}{n}}{365^n} = \frac{_{365}P_n}{365^n}\end{align} </math>

! [[Faktöriyel|faktöriyel operatörü]], {{Matematik|<big><big>(</big></big>{{su|p=365|b=''n''|a=c}}<big><big>)</big></big>}}  [[Binom dağılımı|binom katsayısı]] ve {{Matematik|''<sub>k</sub>P<sub>r</sub>''}} [[permütasyon]]u ifade eder.

Bu denklem, ilk kişinin kimseyle doğum günü paylaşmadığı gerçeğini ifade eder, bununla birlikte, ikinci kişi ilk kişi ile ({{Sfrac|364|365}} ) aynı doğum gününe sahip olamaz, üçüncü kişinin doğum günü ilk iki kişi ile ({{Sfrac|364|365}}) ve genel olarak n’inci doğum günü önceki hiçbir n-1 doğum günü ile aynı olamaz.

n kişiden en az ikisinin aynı doğum gününe sahip olma olayı, tüm n doğum günlerinin farklı olması ile tamamlayıcıdır. Bu nedenle, olasılığı

: <math> p(n) = 1 - \bar p(n). </math>

Aşağıdaki tablo {{Mvar|n}}’in diğer bazı değerleri için olasılıkları göstermektedir (bu tabloda artık yılların varlığı göz ardı edilmiştir ve her doğum gününün eşit derecede olası olduğu varsayılmıştır): 
[[Dosya:Birthdaymatch.svg|sağ|küçükresim| n kişilik bir grupta herhangi iki kişinin doğum günü paylaşmama olasılığı. Düşey ölçek logaritmiktir (aşağı doğru her adım 10<sup>20</sup> kat daha az olasıdır)]]
{| class="wikitable"
!{{mvar|n}}
!{{math|''p''(''n'')}}
|-
| align="right" |1
|{{0}}0.0%
|-
| align="right" |5
|{{0}}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
|{{val|99.99997}}%
|-
| align="right" |200
|{{val|99.9999999999999999999999999998}}%
|-
| align="right" |300
|(100 − {{val|6|e=-80}})%
|-
| align="right" |350
|(100 − {{val|3|e=-129}})%
|-
| align="right" |365
|(100 − {{val|1.45|e=-155}})%
|-
| align="right" |≥ 366
|100%
|}
'''Artık yıllar'''. Eğer <math> \bar p(n) </math>  formülünde 365 yerine 366 yazarsak, benzer bir hesaplama ile artık yıllar için, bir [[Eşleme (matematik)|eşleşme]] olasılığının %50'den fazla olması için gerekli kişi sayısının 23 olduğunu gösterir; bu durumda eşleşme olasılığı %50.6'dır 
[[Dosya:Birthday_paradox_probability.svg|sağ|küçükresim| Doğum gününü ( {{Renk|kırmızı|red}} ) ve tamamlayıcı etkinliğini ( {{Renk|blue|blue}} ) paylaşan en az iki kişinin yaklaşık olasılıklarını gösteren grafikler]]
[[Dosya:Birthday_paradox_approximation.svg|sağ|küçükresim| {{Matematik|1 − ''e''<sup>−{{frac|''n''<sup>2</sup>|730}}</sup>}} bir yaklaşım {{Matematik|1 − ''e''<sup>−{{frac|''n''<sup>2</sup>|730}}</sup>}} doğruluğunu gösteren bir grafiktir {{Matematik|1 − ''e''<sup>−{{frac|''n''<sup>2</sup>|730}}</sup>}} {{Renk|red|red}}]]
[[Üstel fonksiyon]]un [[Taylor serisi]] açılımı (sabit {{Matematik|''e'' ≈ {{val|2.718281828}}}})

: <math> e^x = 1 + x + \frac{x^2}{2!}+\cdots </math>

<math>|x| \ll 1</math> değerleri için, {{Matematik|''e''<sup>''x''</sup>}}  için birinci dereceden yaklaşım sağlar.

: <math> e^x \approx 1 + x.</math>

Bu yaklaşımı {{Matematik|''{{overline|p}}''(''n'')}} için türetilmiş ilk denkleme uygulamak için,

{{Matematik|''x'' {{=}} −{{sfrac|''a''|365}}}}. Böylece,

: <math> e^{-a/365} \approx 1 - \frac{a}{365}. </math>

Bu durumda, {{Matematik|''a'' {{=}} ''n'' − 1}} olana kadar  {{Matematik|''{{overline|p}}''(''n'')}} formülündeki {{Mvar|a}} negatif olmayan tam sayılarla değiştirilirse, örneğin, ne {{Matematik|''a'' {{=}} 1}} iken,

: <math> e^{-1/365} \approx 1 - \frac{1}{365}. </math>

{{Matematik|''{{overline|p}}''(''n'')}} için türetilmiş ilk denklem, şu şekilde yaklaşık olarak bulunabilir:

: <math>
\begin{align}
\bar p(n) & \approx 1 \cdot e^{-1/365} \cdot e^{-2/365} \cdots e^{-(n-1)/365} \\[6pt]
& = e^{-\left.\big( 1+2+ \,\cdots\, +(n-1)\big)\right/365} \\[6pt]
& = e^{-(n(n-1)/2)/365} = e^{-n(n-1)/730}.
\end{align}
</math>

Bu nedenle,

: <math> p(n) = 1-\bar p(n) \approx 1 - e^{-n(n-1)/730}.</math>

Daha kaba bir yaklaşım şu şekilde verilir

: <math>p(n)\approx 1-e^{-n^2/730},</math>

ki, grafikte görüldüğü üzere, hala oldukça doğrudur.

Yaklaşıma göre, aynı yöntem herhangi bir sayıda “insan” ve “gün” için de uygulanabilir. Eğer 365 gün yerine {{mvar|d}} varsa, {{mvar|n}} kişi varsa ve {{math|''n'' ≪ ''d''}} ise, o zaman yukarıdaki yaklaşımı kullanarak, {{math|''p''(''n'', ''d'')}} {{mvar|n}} kişiden en az iki kişinin, {{mvar|d}} uygun gün içerisinden aynı doğum gününü paylaşma olasılığını belirtiyor ise, ulaşacağımız sonuç:

: <math>\begin{align}
 p(n, d) & \approx 1-e^{-n(n-1)/(2d)} \\[6pt]
& \approx 1-e^{-n^2/(2d)}.
\end{align}</math>

=== Basit üssalma ===
Herhangi iki kişinin aynı doğum gününe sahip olmama olasılığı 
{{sfrac|364|365}}’tir. ''n'' kişinin olduğu bir odada {{math|<big><big>(</big></big>{{su|p=''n''|b=2|a=c}}<big><big>)</big></big> {{=}} {{sfrac|''n''(''n''&nbsp;−&nbsp;1)|2}}}} &nbsp;çift insan, bir başka deyişle {{math|<big><big>(</big></big>{{su|p=''n''|b=2|a=c}}<big><big>)</big></big>}} olay vardır. Hiçbir iki kişinin aynı doğum gününü paylaşmama olasılığı, bu olayların bağımsız olduğunu varsaymak ve olasılıklarını beraber çarpmak ile yaklaşık olarak bulunabilir. Kısaca

{{sfrac|364|365}} kendisi ile {{math|<big><big>(</big></big>{{su|p=''n''|b=2|a=c}}<big><big>)</big></big>}} kere çarpılır, bu da:

: <math>\bar p(n) \approx \left(\frac{364}{365}\right)^\binom{n}{2}.</math>

Bu kimsenin aynı doğum gününe sahip olmama olasılığı olduğu için, birinin bir doğum günü paylaşma olasılığı:

: <math>p(n) \approx 1 - \left(\frac{364}{365}\right)^\binom{n}{2}.</math>

=== Poisson yaklaşımı ===
Binom için [[Poisson dağılımı|Poisson yaklaşımının]] 23 kişilik gruba uygulanmasıyla,

: <math>\operatorname{Poi}\left(\frac{\binom{23}{2}}{365}\right) =\operatorname{Poi}\left(\frac{253}{365}\right) \approx \operatorname{Poi}(0.6932)</math>

bu yüzden,

: <math>\Pr(X>0)=1-\Pr(X=0) \approx 1-e^{-0.6932} \approx 1-0.499998=0.500002.</math>

Sonuç, önceki açıklamalar gibi %50’nin üzerindedir. Bu yaklaşım yukarıdaki <math> e^x \approx 1 + x</math> kullanan Taylor açılımı yaklaşımıyla aynıdır.

=== Kare yaklaşımı ===
Zihinsel hesaplama için kullanılabilecek iyi bir kural,

: <math>p(n) \approx \frac{n^2}{2m}</math>

ayrıca şu şekilde de yazılabilir

: <math>n \approx \sqrt { 2m \times p(n)}</math>

 {{sfrac|1|2}}’den küçük veya {{sfrac|1|2}}’ye eşit olasılıklar için etkilidir. Bu denklemlerde, {{mvar|m}} bir yıldaki gün sayısıdır.

Örneğin, ortak bir doğum günü şansının {{sfrac|1|2}} olması için gereken kişi sayısını tahmin etmek için

: <math>n \approx \sqrt{ 2 \times 365 \times \tfrac12} = \sqrt{365} \approx 19</math>

Bu da doğru cevap olan 23’ten çok uzak değildir.

=== Kişi sayısı yaklaşımı ===
Bu aynı zamanda, eşleşme şansın en az {{sfrac|1|2}} olması için gereken kişi sayısı, aşağıdaki formül kullanılarak yaklaşık olarak hesaplanabilir:

: <math>n \approx \tfrac{1}{2} + \sqrt{\tfrac{1}{4} + 2 \times \ln(2) \times 365} = 22.999943.</math>

Bu, {{math|{{sfrac|1|''k''}}}} olasılığı olan bir olayın, eğer {{math|''k'' [[natural logarithm of 2|ln 2]]}} kere tekrarlanırsa, en az bir kere gerçekleşme şansının {{sfrac|1|2}} olacağına dair iyi bir yaklaşımın sonucudur.<ref>{{Dergi kaynağı|url=http://http.cs.berkeley.edu/~daw/papers/genbday-crypto02.ps|başlık=A Generalized Birthday Problem|tarih=Haziran 1991|sayı=2|sayfalar=265-270|dergi=SIAM Review|cilt=33|soyadı=Mathis|ad=Frank H.|issn=0036-1445|pmc=|doi=10.1137/1033051|bibcode=|oclc=37699182|jstor=2031144}}{{Ölü bağlantı|date=Şubat 2024 }}</ref>

=== Olasılık tablosu ===
{| class="wikitable" style="white-space:nowrap;"
! rowspan="2" |length of 
hex string
! rowspan="2" |no. of
bits
({{mvar|b}})
! rowspan="2" |hash space
size
({{math|2<sup>''b''</sup>}})
! colspan="10" |Number of hashed elements such that probability of at least one hash collision&nbsp;≥&nbsp;{{mvar|p}}
|-
!{{mvar|p}} = {{val||e=-18}}
!{{mvar|p}} = {{val||e=-15}}
!{{mvar|p}} = {{val||e=-12}}
!{{mvar|p}} = {{val||e=-9}}
!{{mvar|p}} = {{val||e=-6}}
!{{mvar|p}} = 0.001
!{{mvar|p}} = 0.01
!{{mvar|p}} = 0.25
!{{mvar|p}} = 0.50
!{{mvar|p}} = 0.75
|- align="center"
| bgcolor="#F2F2F2" |8
| bgcolor="#F2F2F2" |32
| bgcolor="#F2F2F2" |{{val|4.3|e=9}}
|2
|2
|2
|2.9
|93
|{{val|2.9|e=3}}
|{{val|9.3|e=3}}
|{{val|5.0|e=4}}
|{{val|7.7|e=4}}
|{{val|1.1|e=5}}
|- align="center"
| bgcolor="#F2F2F2" |(10)
| bgcolor="#F2F2F2" |(40)
| bgcolor="#F2F2F2" |({{val|1.1|e=12}})
|2
|2
|2
|47
|{{val|1.5|e=3}}
|{{val|4.7|e=4}}
|{{val|1.5|e=5}}
|{{val|8.0|e=5}}
|{{val|1.2|e=6}}
|{{val|1.7|e=6}}
|- align="center"
| bgcolor="#F2F2F2" |(12)
| bgcolor="#F2F2F2" |(48)
| bgcolor="#F2F2F2" |({{val|2.8|e=14}})
|2
|2
|24
|{{val|7.5|e=2}}
|{{val|2.4|e=4}}
|{{val|7.5|e=5}}
|{{val|2.4|e=6}}
|{{val|1.3|e=7}}
|{{val|2.0|e=7}}
|{{val|2.8|e=7}}
|- align="center"
| bgcolor="#F2F2F2" |16
| bgcolor="#F2F2F2" |64
| bgcolor="#F2F2F2" |{{val|1.8|e=19}}
|6.1
|{{val|1.9|e=2}}
|{{val|6.1|e=3}}
|{{val|1.9|e=5}}
|{{val|6.1|e=6}}
|{{val|1.9|e=8}}
|{{val|6.1|e=8}}
|{{val|3.3|e=9}}
|{{val|5.1|e=9}}
|{{val|7.2|e=9}}
|- align="center"
| bgcolor="#F2F2F2" |(24)
| bgcolor="#F2F2F2" |(96)
| bgcolor="#F2F2F2" |({{val|7.9|e=28}})
|{{val|4.0|e=5}}
|{{val|1.3|e=7}}
|{{val|4.0|e=8}}
|{{val|1.3|e=10}}
|{{val|4.0|e=11}}
|{{val|1.3|e=13}}
|{{val|4.0|e=13}}
|{{val|2.1|e=14}}
|{{val|3.3|e=14}}
|{{val|4.7|e=14}}
|- align="center"
| bgcolor="#F2F2F2" |32
| bgcolor="#F2F2F2" |128
| bgcolor="#F2F2F2" |{{val|3.4|e=38}}
|{{val|2.6|e=10}}
|{{val|8.2|e=11}}
|{{val|2.6|e=13}}
|{{val|8.2|e=14}}
|{{val|2.6|e=16}}
|{{val|8.3|e=17}}
|{{val|2.6|e=18}}
|{{val|1.4|e=19}}
|{{val|2.2|e=19}}
|{{val|3.1|e=19}}
|- align="center"
| bgcolor="#F2F2F2" |(48)
| bgcolor="#F2F2F2" |(192)
| bgcolor="#F2F2F2" |({{val|6.3|e=57}})
|{{val|1.1|e=20}}
|{{val|3.5|e=21}}
|{{val|1.1|e=23}}
|{{val|3.5|e=24}}
|{{val|1.1|e=26}}
|{{val|3.5|e=27}}
|{{val|1.1|e=28}}
|{{val|6.0|e=28}}
|{{val|9.3|e=28}}
|{{val|1.3|e=29}}
|- align="center"
| bgcolor="#F2F2F2" |64
| bgcolor="#F2F2F2" |256
| bgcolor="#F2F2F2" |{{val|1.2|e=77}}
|{{val|4.8|e=29}}
|{{val|1.5|e=31}}
|{{val|4.8|e=32}}
|{{val|1.5|e=34}}
|{{val|4.8|e=35}}
|{{val|1.5|e=37}}
|{{val|4.8|e=37}}
|{{val|2.6|e=38}}
|{{val|4.0|e=38}}
|{{val|5.7|e=38}}
|- align="center"
| bgcolor="#F2F2F2" |(96)
| bgcolor="#F2F2F2" |(384)
| bgcolor="#F2F2F2" |({{val|3.9|e=115}})
|{{val|8.9|e=48}}
|{{val|2.8|e=50}}
|{{val|8.9|e=51}}
|{{val|2.8|e=53}}
|{{val|8.9|e=54}}
|{{val|2.8|e=56}}
|{{val|8.9|e=56}}
|{{val|4.8|e=57}}
|{{val|7.4|e=57}}
|{{val|1.0|e=58}}
|- align="center"
| bgcolor="#F2F2F2" |128
| bgcolor="#F2F2F2" |512
| bgcolor="#F2F2F2" |{{val|1.3|e=154}}
|{{val|1.6|e=68}}
|{{val|5.2|e=69}}
|{{val|1.6|e=71}}
|{{val|5.2|e=72}}
|{{val|1.6|e=74}}
|{{val|5.2|e=75}}
|{{val|1.6|e=76}}
|{{val|8.8|e=76}}
|{{val|1.4|e=77}}
|{{val|1.9|e=77}}
|}
Bu tabloda açık renkli alanlar, belli bir bit boyutunda verilen özet alanı (satır) belirli çarpışma olasılığını (sütun) başarmak için gereken özet sayısını göstermektedir. Doğum günü benzetmesi kullanılarak: “özet alan boyutu” “uygun günler”e, “çarpışma olasılığı” “ortak doğum günü olasılığı”na ve “gerekli özet elementi sayısı” "bir grup içerisinden gerekli kişi sayısı”na benzemektedir. Bu grafik ayrıca gerekli minimum özet boyutunu (özet üst sınırları ve hata olasılığı verildiğinde) veya çarpışma olasılığını (sabit sayıda özet ve hata olasılığı için) belirlemek için de kullanılabilir.

Karşılaştırma yapılırsa, {{val|e=-18}} ile {{val|e=-15}}, tipik bir sabit diskin bit olarak düzeltilemez hata oranıdır.<ref>Jim Gray, Catharine van Ingen. [[arxiv:cs/0701166|Empirical Measurements of Disk Failure Rates and Error Rates]]</ref> Teorik olarak, [[:en:MD5|MD5]]gibi 128-bit özet fonksiyonları, olası çıktıları çok daha fazla olsa bile, yaklaşık {{val|8.2|e=11}} belgeye kadar bu aralıkta kalmalıdır.

== Olasılık üst sınırı ve kişi sayısı alt sınırı ==
Aşağıdaki argüman Paul Halmos'un bir görüşünden uyarlanmıştır. {{Refn|In his autobiography, Halmos criticized the form in which the birthday paradox is often presented, in terms of numerical computation. He believed that it should be used as an example in the use of more abstract mathematical concepts. He wrote:
{{Alıntı|The reasoning is based on important tools that all students of mathematics should have ready access to. The birthday problem used to be a splendid illustration of the advantages of pure thought over mechanical manipulation; the inequalities can be obtained in a minute or two, whereas the multiplications would take much longer, and be much more subject to error, whether the instrument is a pencil or an old-fashioned desk computer. What [[calculator]]s do not yield is understanding, or mathematical facility, or a solid basis for more advanced, generalized theories.}}}}

Yukarıda belirtildiği gibi, hiçbir iki doğum gününün örtüşmeme olasılığı

: <math>1-p(n) = \bar p(n) = \prod_{k=1}^{n-1}\left(1-\frac{k}{365}\right) .</math>

Önceki paragraflardaki gibi, {{math|''p''(''n'') > {{sfrac|1|2}}}}’i sağlayan en küçük {{mvar|n}} değeri ile veya {{math|''{{overline|p}}''(''n'') < {{sfrac|1|2}}}}’i sağlayan en küçük {{mvar|n}} değeri ile ilgilenilmektedir.

 {{math|1 − ''x'' < ''e''<sup>−''x''</sup>}} eşitsizliği kullanılarak, yukarıdaki denklemde {{math|1 − {{sfrac|''k''|365}}}} yerine {{math|''e''<sup>{{frac|−''k''|365}}</sup>}} yazıldığında

: <math>\bar p(n) = \prod_{k=1}^{n-1}\left(1-\frac{k}{365}\right) < \prod_{k=1}^{n-1}\left(e^{-k/365}\right) = e^{-n(n-1)/730} .</math>

Bu nedenle, yukarıdaki denklem yalnızca bir yaklaşım değil, aynı zamanda {{math|''{{overline|p}}''(''n'')}} için bir [[Üst ve alt sınır|üst sınır]]dır. [[Eşitsizlikler|Eşitsizlik]]

: <math> e^{-n(n-1)/730} < \frac{1}{2}</math>

{{Matematik|''{{overline|p}}''(''n'') < {{sfrac|1|2}}}} olduğunu gösterir. {{mvar|n}} için çözülürse

: <math>n^2-n > 730 \ln 2 .</math>

Bu durumda, {{math|730 ln 2}} yaklaşık olarak 505.997’ye eşittir, ki bu 506’nın çok az altındadır, {{math|''n''<sup>2</sup> − ''n''}} değeri {{math|''n'' {{=}} 23}} iken elde edilir. Bu nedenle 23 kişi yeterlidir. Yeri gelmişken, {{math|''n''<sup>2</sup> − ''n'' {{=}} 730 ln 2}} denkleminin ''n'' için çözülmesi, yukarıda bahsedilen Frank H. Mathis’in formülünü yaklaşık olarak verir.

Bu derivasyon sadece, eşit şansa sahip bir doğum günü eşleşmesi sağlamak için en fazla 23 kişiye ihtiyaç duyulduğunu göstermektedir; n’in 22 veya daha az olmasının işe yarama olasılığının ucunu açık bırakmaktadır.

== Genelleştirmeler ==

=== Genelleştirilmiş doğum günü problemi ===
Verilen {{mvar|d}} adet güne sahip bir yılda, genelleştirilmiş doğum günü problemi, rastgele seçilen {{mvar|n}} kişilik bir grupta bir doğum gününün örtüşme olasılığını en az %50 yapan minimum {{math|''n''(''d'')}} sayısını sorar. Başka bir deyişle, {{math|''n''(''d'')}} minimum {{mvar|n}} tam sayısıdır öyle ki,

: <math>1-\left(1-\frac{1}{d}\right)\left(1-\frac{2}{d}\right)\cdots\left(1-\frac{n-1}{d}\right)\geq \frac{1}{2}.</math>

Klasik doğum günü problemi bu nedenle, {{math|''n''(365)}}’in belirlenmesine karşılık gelir. {{math|''n''(''d'')}}’nin ilk 99 değeri burada verilmiştir {{OEIS|id=A033810}}:  
{| class="wikitable" style="text-align:center;"
! scope="row" |{{mvar|d}}
|1–2
|3–5
|6–9
|10–16
|17–23
|24–32
|33–42
|43–54
|55–68
|69–82
|83–99
|-
! scope="row" |{{math|''n''(''d'')}}
|2
|3
|4
|5
|6
|7
|8
|9
|10
|11
|12
|}
Benzer bir hesaplama, {{mvar|d}} 341-372 aralığında olduğunda {{math|''n''(''d'')}}=23 olduğunu gösterir

 {{math|''n''(''d'')}} için bir dizi sınır ve formül yayınlanmıştır.<ref>{{Kaynak|yazar=D. Brink|başlık=A (probably) exact solution to the Birthday Problem|dergi=Ramanujan Journal|yıl=2012|url=https://link.springer.com/article/10.1007/s11139-011-9343-9|erişim-tarihi=24 Mart 2020|arşivurl=https://web.archive.org/web/20201027163106/https://link.springer.com/article/10.1007/s11139-011-9343-9|arşivtarihi=27 Ekim 2020|ölüurl=hayır}}</ref> Tüm {{math|''d'' ≥ 1}} için {{math|''n''(''d'')}} sayısı aşağıdaki eşitsizliği sağlar:<ref>{{Harvs|author=Brink|year=2012|nb=yes|loc=Theorem 2}}</ref>

: <math>\frac{3-2\ln2}{6}<n(d)-\sqrt{2d\ln2}\leq 9-\sqrt{86\ln2}.</math>

Bu limitler, {{math|''n''(''d'') − {{sqrt|2''d'' ln 2}}}} dizisinin aşağıdaki sayıya rastgele yakınlaşması açısından uygundur;

: <math>\frac{3-2\ln2}{6} \approx 0.27,</math>

aslında,

: <math>9-\sqrt{86\ln2}\approx 1.28</math>

 {{math|''d'' {{=}} 43}} alındığında maksimumdadır.

Limitler, tüm olayların %99'unda {{math|''n''(''d'')}}'nin tam değerini verecek kadar sıkıdır, örneğin {{math|''n''(365) {{=}} 23}}. Genel olarak, bu sınırlardan {{math|''n''(''d'')}}'nin daima

: <math>\left\lceil\sqrt{2d\ln2}\,\right\rceil \quad\text{veya}\quad \left\lceil\sqrt{2d\ln2}\,\right\rceil+1</math>

‘e eşit olduğu görülür; {{Matematik|⌈ · ⌉}} tavan fonksiyonunu ifade eder. Formül

: <math>n(d) = \left\lceil\sqrt{2d\ln2}\,\right\rceil</math>

tüm [[Tam sayı|tamsayı]] {{mvar|d}}'lerin %73'ü için geçerlidir.<ref name="Brink4">{{Harvs|author=Brink|year=2012|nb=yes|loc=Theorem 3}}</ref> Formül

: <math>n(d) = \left\lceil\sqrt{2d\ln2}+\frac{3-2\ln2}{6}\right\rceil</math>

neredeyse tüm  {{Mvar|d}} ’ler için, yani asimptotik yoğunluğu 1 olan tam sayı {{mvar|d}} [[küme]]si için, geçerlidir.

Formül

: <math>n(d)=\left\lceil \sqrt{2d\ln2}+\frac{3-2\ln2}{6}+\frac{9-4(\ln2)^2}{72\sqrt{2d\ln2}}\right\rceil</math>

 {{math|''d'' ≤ {{val|e=18}}}} için geçerlidir, ancak bu formüle sonsuz sayıda karşı örnek olduğu tahmin edilir.<ref name="ReferenceA2">{{Harvs|author=Brink|year=2012|nb=yes|loc=Table 3, Conjecture 1}}</ref>

Formül

: <math>n(d)=\left\lceil \sqrt{2d\ln2}+\frac{3-2\ln2}{6}+\frac{9-4(\ln2)^2}{72\sqrt{2d\ln2}}-\frac{2(\ln2)^2}{135d}\right\rceil</math>

 {{math|''d'' ≤ {{val|e=18}}}} için geçerlidir ve bu formülün tüm {{mvar|d}} değerleri için geçerli olduğu tahmin edilir.

=== 2 kişiden fazla ===
Problem, gruptan en az 3/4/5 vb. kişinin aynı doğum gününü paylaşma olasılığının %50’den fazla olması için kaç kişilik bir grubun gerektiğini sormak için genişletilebilir.

İlk birkaç değer şöyledir: 3 kişinin bir doğum günü paylaşma olasılığı>50% - 88 kişi; 4 kişinin bir doğum günü paylaşma olasılığı>50% - 187 kişi. Tüm liste Tam sayı Dizilerinin Çevrimiçi Ansiklopedisi’nin A014088 dizisinde bulunabilir.<ref>{{Web kaynağı | url = https://oeis.org/A014088 | başlık = Minimal number of people to give a 50% probability of having at least n coincident birthdays in one year. | erişimtarihi = 17 Şubat 2020 | website = The On-line Encyclopedia of Integer Sequences | yayıncı = OEIS | arşivurl = https://web.archive.org/web/20110901030326/https://oeis.org/A014088 | arşivtarihi = 1 Eylül 2011 | ölüurl =evet}}</ref>

=== Bir çarpışma problemi olarak tahmin ===
Doğum günü problemi aşağıdaki şekilde genelleştirilebilir:

{{Matematik|[1,''d'']}} aralığındaki [[Tekdüze dağılım (ayrık)|ayrı bir muntazam dağılımdan]] alınan {{mvar|n}}  rastgele tam sayı verildiğinde, en az iki sayının aynı olma olasılığı, {{Matematik|''p''(''n''; ''d'')}} nedir? ( {{Matematik|''d'' {{=}} 365}} olağan doğum günü problemini verir. )<ref>{{konferans kaynağı|başlık=Birthday Paradox for Multi-collisions|soyadı1=Suzuki|ad1=K.|soyadı2=Tonien|ad2=D.|yazarlarıgöster=et al|tarih=2006|yayıncı=Springer|kitapbaşlığı=Lecture Notes in Computer Science, vol 4296|yer=Berlin|tanıtıcı=Information Security and Cryptology – ICISC 2006|editör=Rhee M.S., Lee B.|doi=10.1007/11927587_5}}</ref>

Genel sonuçlar yukarıda verilen aynı argümanlar kullanılarak türetilebilir.

: <math>\begin{align}
p(n;d) &= \begin{cases} 1-\displaystyle\prod_{k=1}^{n-1}\left(1-\frac{k}{d}\right) & n\le d \\ 1 & n > d \end{cases} \\[8px]
& \approx 1 - e^{-\frac{n(n-1)}{2d}} \\
& \approx 1 - \left( \frac{d-1}{d} \right)^\frac{n(n-1)}{2}
\end{align}</math>

Diğer taraftan, eğer {{math|''n''(''p''; ''d'')}} en az iki sayının aynı olma olasılığını elde etmek için {{math|[1,''d'']}}’den alınan rastgele tamsayıların sayısını belirtirse,

: <math>n(p;d)\approx \sqrt{2d \cdot \ln\left(\frac{1}{1-p}\right)}.</math>

Daha genel anlamdaki bu doğum günü problemi [[Özet fonksiyonu|özet fonksiyonları]] için geçerlidir: çarpışma almadan önce oluşturulabilecek {{Matematik|''N''}} - [[Bit (bilişim)|Bit]] özet sayısı  {{Matematik|2<sup>''N''</sup>}} değil, sadece  {{Matematik|2<sup>{{frac|''N''|2}}</sup>}}'dir. Bu, [[Kriptografik özet fonksiyonu|kriptografik karma işlevlerine]] yapılan [[Doğum günü akını|doğum günü saldırıları]]  tarafından istismar edilir ve [[Doğum günü akını|doğum günü saldırıları]]  az sayıda çarpışmanın, tüm pratik amaçlar için, kaçınılmaz olmasının nedenidir.

Doğum günü probleminin arkasında yatan [[teori]] Zoe Schnabel<ref>Z. E. Schnabel (1938) ''The Estimation of the Total Fish Population of a Lake'', [[American Mathematical Monthly]] '''45''', 348–352.</ref>  [[İşaretleyin ve yeniden yakalayın|Mark and recapture]] istatistikleri adı altında, göllerdeki balık popülasyonunun büyüklüğünü tahmin etmek için kullanılmıştır.

==== Çoklu tip için genelleştirme ====
[[Dosya:2d_birthday.png|küçükresim|En az bir erkek ve bir kadın arasındaki en az bir ortak doğum günü olasılığının grafiği]]
Temel problem, tüm denemelerin tek bir “tip” olduğunu kabul eder. Doğum günü problemi, rastgele tip sayısını hesaba katmak için genelleştirilebilir.<ref>[[Michael Christopher Wendl|M. C. Wendl]] (2003) ''[https://dx.doi.org/10.1016/S0167-7152(03)00168-8 Collision Probability Between Sets of Random Variables]'', Statistics and Probability Letters '''64'''(3), 249–254.</ref> En basit kapsamda, {{mvar|m}} erkek ve {{mvar|n}} kadın olmak üzere iki tip insan vardır ve problem, en az bir erkek ve bir kadın arasındaki ortak doğum günü olasılığını simgeler. (İki erkek veya iki kadın arasındaki ortak doğum günleri sayılmaz.) Burada paylaşılan doğum günlerinin olmama olasılığı

: <math>p_0 =\frac{1}{d^{m+n}} \sum_{i=1}^m \sum_{j=1}^n S_2(m,i) S_2(n,j) \prod_{k=0}^{i+j-1} d - k</math>

 {{math|''d'' {{=}} 365}} ve {{math|''S''<sub>2</sub>}} ikinci dereceden Stirling sayılarıdır. Dolayısıyla, istenen olasılık {{math|1 − ''p''<sub>0</sub>}}’dır.

Doğum günü probleminin bu değişimi ilginçtir çünkü toplam insan sayısı {{math|''m'' + ''n''}} için tek özgün çözüm yoktur. Örneğin, olağan %50 olasılık değeri, hem 16 erkek ve 16 kadından oluşan 32 üyeli grup için hem de 43 kadın ve 6 erkekten oluşan 49 üyeli grup için gerçekleştirilir.

== Notlar==
<references group="nb"/>

== Kaynakça ==
{{Kaynakça|45em}}

==Konuyla iligli yayınlar==
* {{Dergi kaynağı|başlık=More Birthday Surprises|url=https://archive.org/details/sim_american-mathematical-monthly_1970-10_77_8/page/856|yazarlar=Abramson|sayı=8|sayfalar=856-858|çalışma=[[American Mathematical Monthly]]|yıl=1970|cilt=77}}
* {{Dergi kaynağı|başlık=A Birthday Problem|url=https://archive.org/details/sim_american-mathematical-monthly_1973-12_80_10/page/1141|yazarlar=Bloom|sayı=10|sayfalar=1141-1142|çalışma=[[American Mathematical Monthly]]| kaynak = harv|yıl=1973|cilt=80}}
* Kemeny, John G.; Snell, J. Laurie; Thompson, Gerald (1957). Introduction to Finite Mathematics (First ed.).
* {{Dergi kaynağı|başlık=Extensions of the Birthday Surprise|yazarlar=Klamkin|sayı=3|sayfalar=279-282|çalışma=Journal of Combinatorial Theory|yıl=1967|cilt=3}}
* {{Dergi kaynağı|başlık=Generalized Birthday Problem|url=https://archive.org/details/sim_american-mathematical-monthly_1966-04_73_4/page/385|yazarlar=McKinney|sayı=4|sayfalar=385-387|çalışma=[[American Mathematical Monthly]]|yıl=1966|cilt=73}}
* {{Kitap kaynağı|isbn=978-0-465-03292-1|başlık=Math on Trial|url=http://books.google.com/books?id=8QTTDQAAQBAJ&printsec=frontcover&dq=isbn:9780465032921&hl=&cd=1&source=gbs_api|dil=İngilizce|yazar1=Leila Schneps|yazar2=Coralie Colmez|tarih=12 Mart 2013|yayıncı=Basic Books (AZ)}}
* {{Kitap kaynağı|isbn=978-0-12-407163-6|url=https://books.google.com/books?id=M7TCNAEACAAJ|başlık=Guide to Essential Math|dil=İngilizce|yazar1=S. M. Blinder|tarih=2013|yayıncı=Elsevier Science Limited|erişimtarihi=24 Mart 2020|arşivurl=https://web.archive.org/web/20200815025128/https://books.google.com/books?id=M7TCNAEACAAJ|arşivtarihi=15 Ağustos 2020|ölüurl=hayır}}

[[Kategori:Matematiksel problemler]]
[[Kategori:Doğum günleri]]
[[Kategori:Uygulamalı olasılık]]