Doğum günü problemi

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.

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

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 ( ) aynı doğum gününe sahip olamaz, üçüncü kişinin doğum günü ilk iki kişi ile () ve genel olarak n’inci doğum günü önceki hiçbir n-1 doğum günü ile aynı olamaz.

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, ile , 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 belgeye kadar bu aralıkta kalmalıdır.

Bu durumda, yaklaşık olarak 505.997’ye eşittir, ki bu 506’nın çok az altındadır, değeri iken elde edilir. Bu nedenle 23 kişi yeterlidir. Yeri gelmişken, 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.

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.

Daha genel anlamdaki bu doğum günü problemi özet fonksiyonları için geçerlidir: çarpışma almadan önce oluşturulabilecek - Bit özet sayısı değil, sadece '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.

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