Doğum günü problemi

Şablon:Çoklu sorun Olasılık teorisinde, 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 ilkesine 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. Ö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 kriptografik 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 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.

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ıllar, 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Şablon:Refn. Aslında, doğum günlerinin düzenli dağılımı en kötü durumdur.)

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 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: Şablon:NumBlk Denklem ( Şablon:Denklem notu )’in terimleri tek tarafta toplanırsa: Şablon:NumBlk Denklem ( Şablon:Denklem notu ) çözümü Şablon:Matematik'ü verir.

Bu nedenle, Şablon:Matematik   (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:

$\begin{array}{cc}\overline{p}(n)& =1\times (1-\frac{1}{365})\times (1-\frac{2}{365})\times \cdots \times (1-\frac{n-1}{365})\\ & =\frac{365\times 364\times \cdots \times (365-n+1)}{365^n}\\ & =\frac{365!}{365^n(365-n)!}=\frac{n!\cdot (\genfrac{}{}{0ex}{}{365}{n})}{365^n}=\frac{{}_{365}{P}_n}{365^n}\end{array}$

! faktöriyel operatörü, Şablon:Matematik binom katsayısı ve Şablon:Matematik permütasyonu 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 (Şablon:Sfrac ) aynı doğum gününe sahip olamaz, üçüncü kişinin doğum günü ilk iki kişi ile (Şablon:Sfrac) 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ığı

$p(n)=1-\overline{p}(n).$

Aşağıdaki tablo Şablon:Mvar’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):

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²⁰ kat daha az olasıdır)

Şablon:Mvar	Şablon:Math
1	Şablon:00.0%
5	Şablon:02.7%
10	11.7%
20	41.1%
23	50.7%
30	70.6%
40	89.1%
50	97.0%
60	99.4%
70	99.9%
75	99.97%
100	Şablon:Val%
200	Şablon:Val%
300	(100 − Şablon:Val)%
350	(100 − Şablon:Val)%
365	(100 − Şablon:Val)%
≥ 366	100%

Artık yıllar. Eğer $\overline{p}(n)$ formülünde 365 yerine 366 yazarsak, benzer bir hesaplama ile artık yıllar için, bir 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

Doğum gününü ( Şablon:Renk ) ve tamamlayıcı etkinliğini ( Şablon:Renk ) paylaşan en az iki kişinin yaklaşık olasılıklarını gösteren grafikler

Şablon:Matematik bir yaklaşım Şablon:Matematik doğruluğunu gösteren bir grafiktir Şablon:Matematik Şablon:Renk

Üstel fonksiyonun Taylor serisi açılımı (sabit Şablon:Matematik)

$e^x=1+x+\frac{x^2}{2!}+\cdots$

$|x|\ll 1$ değerleri için, Şablon:Matematik için birinci dereceden yaklaşım sağlar.

$e^x\approx 1+x.$

Bu yaklaşımı Şablon:Matematik için türetilmiş ilk denkleme uygulamak için,

Şablon:Matematik. Böylece,

$e^{-a/365}\approx 1-\frac{a}{365}.$

Bu durumda, Şablon:Matematik olana kadar Şablon:Matematik formülündeki Şablon:Mvar negatif olmayan tam sayılarla değiştirilirse, örneğin, ne Şablon:Matematik iken,

$e^{-1/365}\approx 1-\frac{1}{365}.$

Şablon:Matematik için türetilmiş ilk denklem, şu şekilde yaklaşık olarak bulunabilir:

$\begin{array}{cc}\overline{p}(n)& \approx 1\cdot e^{-1/365}\cdot e^{-2/365}\cdots e^{-(n-1)/365}\\ & =e^{-(1+2+\cdots +(n-1))/365}\\ & =e^{-(n(n-1)/2)/365}=e^{-n(n-1)/730}.\end{array}$

Bu nedenle,

$p(n)=1-\overline{p}(n)\approx 1-e^{-n(n-1)/730}.$

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

$p(n)\approx 1-e^{-n^2/730},$

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 Şablon:Mvar varsa, Şablon:Mvar kişi varsa ve Şablon:Math ise, o zaman yukarıdaki yaklaşımı kullanarak, Şablon:Math Şablon:Mvar kişiden en az iki kişinin, Şablon:Mvar uygun gün içerisinden aynı doğum gününü paylaşma olasılığını belirtiyor ise, ulaşacağımız sonuç:

$\begin{array}{cc}p(n,d)& \approx 1-e^{-n(n-1)/(2d)}\\ & \approx 1-e^{-n^2/(2d)}.\end{array}$

Basit üssalma

Herhangi iki kişinin aynı doğum gününe sahip olmama olasılığı Şablon:Sfrac’tir. n kişinin olduğu bir odada Şablon:Math  çift insan, bir başka deyişle Şablon:Math 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

Şablon:Sfrac kendisi ile Şablon:Math kere çarpılır, bu da:

$\overline{p}(n)\approx {\left(\frac{364}{365}\right)}^{(\genfrac{}{}{0ex}{}{n}{2})}.$

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ığı:

$p(n)\approx 1-{\left(\frac{364}{365}\right)}^{(\genfrac{}{}{0ex}{}{n}{2})}.$

Poisson yaklaşımı

Binom için Poisson yaklaşımının 23 kişilik gruba uygulanmasıyla,

$\mathrm{Poi}\left(\frac{(\genfrac{}{}{0ex}{}{23}{2})}{365}\right)=\mathrm{Poi}\left(\frac{253}{365}\right)\approx \mathrm{Poi}(0.6932)$

bu yüzden,

$\mathrm{Pr}(X>0)=1-\mathrm{Pr}(X=0)\approx 1-e^{-0.6932}\approx 1-0.499998=0.500002.$

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

Kare yaklaşımı

Zihinsel hesaplama için kullanılabilecek iyi bir kural,

$p(n)\approx \frac{n^2}{2m}$

ayrıca şu şekilde de yazılabilir

$n\approx \sqrt{2m\times p(n)}$

Şablon:Sfrac’den küçük veya Şablon:Sfrac’ye eşit olasılıklar için etkilidir. Bu denklemlerde, Şablon:Mvar bir yıldaki gün sayısıdır.

Örneğin, ortak bir doğum günü şansının Şablon:Sfrac olması için gereken kişi sayısını tahmin etmek için

$n\approx \sqrt{2\times 365\times \frac{1}{2}}=\sqrt{365}\approx 19$

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 Şablon:Sfrac olması için gereken kişi sayısı, aşağıdaki formül kullanılarak yaklaşık olarak hesaplanabilir:

$n\approx \frac{1}{2}+\sqrt{\frac{1}{4}+2\times \ln (2)\times 365}=22.999943.$

Bu, Şablon:Math olasılığı olan bir olayın, eğer Şablon:Math kere tekrarlanırsa, en az bir kere gerçekleşme şansının Şablon:Sfrac olacağına dair iyi bir yaklaşımın sonucudur.

Olasılık tablosu

length of hex string	no. of bits (Şablon:Mvar)	hash space size (Şablon:Math)	Number of hashed elements such that probability of at least one hash collision ≥ Şablon:Mvar
			Şablon:Mvar = Şablon:Val	Şablon:Mvar = Şablon:Val	Şablon:Mvar = Şablon:Val	Şablon:Mvar = Şablon:Val	Şablon:Mvar = Şablon:Val	Şablon:Mvar = 0.001	Şablon:Mvar = 0.01	Şablon:Mvar = 0.25	Şablon:Mvar = 0.50	Şablon:Mvar = 0.75
8	32	Şablon:Val	2	2	2	2.9	93	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val
(10)	(40)	(Şablon:Val)	2	2	2	47	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val
(12)	(48)	(Şablon:Val)	2	2	24	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val
16	64	Şablon:Val	6.1	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val
(24)	(96)	(Şablon:Val)	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val
32	128	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val
(48)	(192)	(Şablon:Val)	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val
64	256	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val
(96)	(384)	(Şablon:Val)	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val
128	512	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val	Şablon:Val

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, Şablon:Val ile Şablon:Val, tipik bir sabit diskin bit olarak düzeltilemez hata oranıdır. Teorik olarak, MD5gibi 128-bit özet fonksiyonları, olası çıktıları çok daha fazla olsa bile, yaklaşık Şablon:Val 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. Şablon:Refn

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

$1-p(n)=\overline{p}(n)=\prod _{k=1}^{n-1}(1-\frac{k}{365}).$

Önceki paragraflardaki gibi, Şablon:Math’i sağlayan en küçük Şablon:Mvar değeri ile veya Şablon:Math’i sağlayan en küçük Şablon:Mvar değeri ile ilgilenilmektedir.

Şablon:Math eşitsizliği kullanılarak, yukarıdaki denklemde Şablon:Math yerine Şablon:Math yazıldığında

$\overline{p}(n)=\prod _{k=1}^{n-1}(1-\frac{k}{365})<\prod _{k=1}^{n-1}\left(e^{-k/365}\right)=e^{-n(n-1)/730}.$

Bu nedenle, yukarıdaki denklem yalnızca bir yaklaşım değil, aynı zamanda Şablon:Math için bir üst sınırdır. Eşitsizlik

$e^{-n(n-1)/730}<\frac{1}{2}$

Şablon:Matematik olduğunu gösterir. Şablon:Mvar için çözülürse

$n^2-n>730\ln 2.$

Bu durumda, Şablon:Math yaklaşık olarak 505.997’ye eşittir, ki bu 506’nın çok az altındadır, Şablon:Math değeri Şablon:Math iken elde edilir. Bu nedenle 23 kişi yeterlidir. Yeri gelmişken, Şablon:Math 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 Şablon:Mvar adet güne sahip bir yılda, genelleştirilmiş doğum günü problemi, rastgele seçilen Şablon:Mvar kişilik bir grupta bir doğum gününün örtüşme olasılığını en az %50 yapan minimum Şablon:Math sayısını sorar. Başka bir deyişle, Şablon:Math minimum Şablon:Mvar tam sayısıdır öyle ki,

$1-(1-\frac{1}{d})(1-\frac{2}{d})\cdots (1-\frac{n-1}{d})\ge \frac{1}{2}.$

Klasik doğum günü problemi bu nedenle, Şablon:Math’in belirlenmesine karşılık gelir. Şablon:Math’nin ilk 99 değeri burada verilmiştir Şablon:OEIS:

Şablon:Mvar	1–2	3–5	6–9	10–16	17–23	24–32	33–42	43–54	55–68	69–82	83–99
Şablon:Math	2	3	4	5	6	7	8	9	10	11	12

Benzer bir hesaplama, Şablon:Mvar 341-372 aralığında olduğunda Şablon:Math=23 olduğunu gösterir

Şablon:Math için bir dizi sınır ve formül yayınlanmıştır. Tüm Şablon:Math için Şablon:Math sayısı aşağıdaki eşitsizliği sağlar:

$\frac{3-2\ln 2}{6}<n(d)-\sqrt{2d\ln 2}\le 9-\sqrt{86\ln 2}.$

Bu limitler, Şablon:Math dizisinin aşağıdaki sayıya rastgele yakınlaşması açısından uygundur;

$\frac{3-2\ln 2}{6}\approx 0.27,$

aslında,

$9-\sqrt{86\ln 2}\approx 1.28$

Şablon:Math alındığında maksimumdadır.

Limitler, tüm olayların %99'unda Şablon:Math'nin tam değerini verecek kadar sıkıdır, örneğin Şablon:Math. Genel olarak, bu sınırlardan Şablon:Math'nin daima

$\lceil \sqrt{2d\ln 2}\rceil \text{veya}\lceil \sqrt{2d\ln 2}\rceil +1$

‘e eşit olduğu görülür; Şablon:Matematik tavan fonksiyonunu ifade eder. Formül

$n(d)=\lceil \sqrt{2d\ln 2}\rceil$

tüm tamsayı Şablon:Mvar'lerin %73'ü için geçerlidir. Formül

$n(d)=\lceil \sqrt{2d\ln 2}+\frac{3-2\ln 2}{6}\rceil$

neredeyse tüm Şablon:Mvar ’ler için, yani asimptotik yoğunluğu 1 olan tam sayı Şablon:Mvar kümesi için, geçerlidir.

Formül

$n(d)=\lceil \sqrt{2d\ln 2}+\frac{3-2\ln 2}{6}+\frac{9-4(\ln 2{)}^2}{72\sqrt{2d\ln 2}}\rceil$

Şablon:Math için geçerlidir, ancak bu formüle sonsuz sayıda karşı örnek olduğu tahmin edilir.

Formül

$n(d)=\lceil \sqrt{2d\ln 2}+\frac{3-2\ln 2}{6}+\frac{9-4(\ln 2{)}^2}{72\sqrt{2d\ln 2}}-\frac{2(\ln 2{)}^2}{135d}\rceil$

Şablon:Math için geçerlidir ve bu formülün tüm Şablon:Mvar 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.

Bir çarpışma problemi olarak tahmin

Doğum günü problemi aşağıdaki şekilde genelleştirilebilir:

Şablon:Matematik aralığındaki ayrı bir muntazam dağılımdan alınan Şablon:Mvar rastgele tam sayı verildiğinde, en az iki sayının aynı olma olasılığı, Şablon:Matematik nedir? ( Şablon:Matematik olağan doğum günü problemini verir. )

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

$\begin{array}{cc}p(n;d)& =\{\begin{array}{cc}1-\prod _{k=1}^{n-1}(1-\frac{k}{d})& n\le d\\ 1& n>d\end{array}\\ [8px]& \approx 1-e^{-\frac{n(n-1)}{2d}}\\ & \approx 1-{\left(\frac{d-1}{d}\right)}^{\frac{n(n-1)}{2}}\end{array}$

Diğer taraftan, eğer Şablon:Math en az iki sayının aynı olma olasılığını elde etmek için Şablon:Math’den alınan rastgele tamsayıların sayısını belirtirse,

$n(p;d)\approx \sqrt{2d\cdot \ln \left(\frac{1}{1-p}\right)}.$

Daha genel anlamdaki bu doğum günü problemi özet fonksiyonları için geçerlidir: çarpışma almadan önce oluşturulabilecek Şablon:Matematik - Bit özet sayısı Şablon:Matematik değil, sadece Şablon:Matematik'dir. Bu, kriptografik karma işlevlerine yapılan doğum günü saldırıları tarafından istismar edilir ve 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 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

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. En basit kapsamda, Şablon:Mvar erkek ve Şablon:Mvar 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ığı

$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$

Şablon:Math ve Şablon:Math ikinci dereceden Stirling sayılarıdır. Dolayısıyla, istenen olasılık Şablon:Math’dır.

Doğum günü probleminin bu değişimi ilginçtir çünkü toplam insan sayısı Şablon:Math 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.

Konuyla iligli yayınlar

• Şablon:Dergi kaynağı
• Şablon:Dergi kaynağı
• Kemeny, John G.; Snell, J. Laurie; Thompson, Gerald (1957). Introduction to Finite Mathematics (First ed.).
• Şablon:Dergi kaynağı
• Şablon:Dergi kaynağı
• Şablon:Kitap kaynağı
• Şablon:Kitap kaynağı