Doğum günü problemi

bullvar_katip · 28 Mayıs 2024

Olasılık teorisinde, doğum günü problemi veya doğum günü paradoksu, n adet rastgele seçilmiş kişiden oluşan bir grup içindeki bazı çiftlerin doğum gününün aynı olma olasılığını inceler. Güvercin deliği ilkesine göre, kişi sayısı 367’ye ulaştığında (29 Şubat dahil, 366 adet olası doğum günü olduğu için) olasılık %100’e ulaşır fakat, %99,9 olasılığa sadece 70 kişi ile ve %50 olasılığa 23 kişi ile ulaşılır. Bu sonuçlar, yılın her gününün (29 Şubat hariç) eşit derecede olası bir doğum günü olduğu varsayımına dayanır. Mevcut doğum kayıtları farklı günlerde farklı sayıda insanın doğduğunu gösterir. Bu durumda, %50 eşiğine ulaşmak için gereken insan sayısının 23 veya daha az olduğu söylenebilir. Örneğin, insanların yarısı bir günde ve diğer yarısı başka bir günde doğmuş olsaydı, bu durumda herhangi iki kişinin doğum gününü paylaşma şansı %50 olurdu. Gruptaki en az iki kişinin aynı doğum gününe sahip olma olasılığının %50’ye ulaşılması için sadece 23 kişilik bir grubun gerektiği şaşırtıcı görünebilir: bu sonuç, bir bireye sabitlenmenin ve onun doğum gününü diğerleriyle karşılaştırmanın aksine doğum günü karşılaştırmasının aslında, olası her bir çift arasında = 23 x 22/2 = 253 karşılaştırma -bir yıl içindeki gün sayısının yarısından (en fazla 183) daha çok- yapılmasıyla daha makul olabilir. Doğum günü problemi kendisiyle mantıksal çelişkili olma anlamda bir “paradoks” değildir, ancak ilk bakışta anlaşılamaz. Doğum günü probleminin gerçek hayattaki uygulamaları arasında doğum günü saldırısı isimli bir kriptografik saldırı vardır; bu saldırı bu olasılık modelini kullanarak bir özet fonksiyonu için çarpışma bulma karmaşıklığını azaltır ve büyüklüğü belirli bir popülasyonun özetleri arasında bulunan bir özet çarpışmasının yaklaşık riskini hesaplar. Problemin tarihi bilinmemektedir. W. W. Rouse Ball, bunun ilk olarak Harold Davenport tarafından ele alındığını belirtmiştir (alıntı yok). Ancak, Richard von Mises, bugün doğum günü problemi olarak bilinen şeyin daha eski bir versiyonunu sunmuştur. alt=|küçükresim|En az iki kişinin doğum günü paylaşma olasılığına karşı kişi sayısı Olasılığın hesaplanması Problem, n kişiden oluşan bir grup içindeki en az iki kişinin doğum gününün aynı olma olasılığını yaklaşık olarak hesaplamaktır. Basitlik adına, artık yıllar, ikizler, sezonluk veya iş günü değişiklikleri gibi dağılımdaki değişimler göz ardı edilmiştir ve 365 olası doğum gününün hepsinin eşit derecede olası olduğu varsayılmıştır. (Gerçekte doğum günü dağılımları düzenli değildir çünkü tüm tarihler eşit derecede olası değildir, fakat bu düzensizliklerin analiz üzerinde çok az etkisi vardır. Aslında, doğum günlerinin düzenli dağılımı en kötü durumdur.) Amaç, P(A) ile ifade edilen, odadaki en az iki kişinin doğum gününün aynı olma olasılığını hesaplamaktır. Ancak, P(A’) ile ifade edilen, odadaki hiç kimsenin doğum gününün aynı olmama olasılığını hesaplamak daha kolaydır. Bu durumda, sadece A ve A’ olasılık dahilinde ve ayrık olaylar olduğu için, P(A)=1-P(A’). P(A)’nın %50’den fazla olması için gereken kişi sayısının en az 23 olduğunu belirten yaygın çözümleri dikkate alarak, aşağıdaki P(A) hesaplamasında örnek olarak 23 kişi kullanılacaktır. Eğer 23 kişi 1’den 23’e kadar numaralandırılırsa, 23 kişinin hepsinin farklı doğum günlerine sahip olması olayı, 2. kişinin 1. kişi ile aynı doğum gününe sahip olmama olayı ile, ve 3. kişinin 1. ve 2. kişiyle aynı doğum gününe sahip olmama olayı, vb.; ve son olarak 23. kişinin 1’den 22’ye kadar olan kişilerin hiçbiri ile aynı doğum günü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. kişinin doğum gününe sahip olma olayı, ki bu olayın olasılığı 1’dir, eklenebilir. Bu olayların birleşimi koşullu olasılık kullanılarak hesaplanabilir: Olay 2’nin olasılığı 364/365’tir, çünkü 2. kişinin doğum günü, 1. kişinin doğum günü dışındaki herhangi bir günde olabilir. Benzer şekilde, Olay 2’nin gerçekleştiği göz önüne alındığında, Olay 3’ün olasılığı 363/365’tir, çünkü 3. kişinin doğum günü 1. ve 2. kişinin doğum günleri dışında her gün olabilir. Bu, önceki tüm olayların gerçekleştiği göz önüne alındığında, Olay 23’ün olasılığı 343/365 olana kadar devam eder. Son olarak, koşullu olasılık prensibi, P(A’)’nın bu ayrı olasılıkların çarpımına eşit olduğunu belirtir: Denklem ( )’in terimleri tek tarafta toplanırsa: Denklem ( ) çözümü 'ü verir. Bu nedenle, (50,7297%). Bu yöntem n kişiden oluşan bir grup için genelleştirilebilir, p

n kişiden en az iki kişinin bir doğum günü paylaşması olasılığıdır. Öncelikle, tüm n doğum günlerinin farklı olma olasılığını, p

, hesaplamak daha kolaydır. Güvercin yuvası prensibine göre, n>365 ise p

sıfırdır. n ≤ 365 ise: ! faktöriyel operatörü, binom katsayısı ve permütasyonu ifade eder. Bu denklem, ilk kişinin kimseyle doğum günü paylaşmadığı gerçeğini ifade eder, bununla birlikte, ikinci kişi ilk kişi ile ( ) aynı doğum gününe sahip olamaz, üçüncü kişinin doğum günü ilk iki kişi ile ve genel olarak n’inci doğum günü önceki hiçbir n-1 doğum günü ile aynı olamaz. n kişiden en az ikisinin aynı doğum gününe sahip olma olayı, tüm n doğum günlerinin farklı olması ile tamamlayıcıdır. Bu nedenle, olasılığı Aşağıdaki tablo ’in diğer bazı değerleri için olasılıkları göstermektedir (bu tabloda artık yılların varlığı göz ardı edilmiştir ve her doğum gününün eşit derecede olası olduğu varsayılmıştır): sağ|küçükresim| n kişilik bir grupta herhangi iki kişinin doğum günü paylaşmama olasılığı. Düşey ölçek logaritmiktir (aşağı doğru her adım 10 kat daha az olasıdır) Artık yıllar. Eğer formülünde 365 yerine 366 yazarsak, benzer bir hesaplama ile artık yıllar için, bir eşleşme olasılığının %50’den fazla olması için gerekli kişi sayısının 23 olduğunu gösterir; bu durumda eşleşme olasılığı %50.6’dır sağ|küçükresim| Doğum gününü ( ) ve tamamlayıcı etkinliğini ( ) paylaşan en az iki kişinin yaklaşık olasılıklarını gösteren grafikler sağ|küçükresim| bir yaklaşım doğruluğunu gösteren bir grafiktir Üstel fonksiyonun Taylor serisi açılımı (sabit ) değerleri için, için birinci dereceden yaklaşım sağlar. Bu yaklaşımı için türetilmiş ilk denkleme uygulamak için, . Böylece, Bu durumda, olana kadar formülündeki negatif olmayan tam sayılarla değiştirilirse, örneğin, ne iken, için türetilmiş ilk denklem, şu şekilde yaklaşık olarak bulunabilir: Bu nedenle, Daha kaba bir yaklaşım şu şekilde verilir ki, grafikte görüldüğü üzere, hala oldukça doğrudur. Yaklaşıma göre, aynı yöntem herhangi bir sayıda “insan” ve “gün” için de uygulanabilir. Eğer 365 gün yerine varsa, kişi varsa ve ise, o zaman yukarıdaki yaklaşımı kullanarak, kişiden en az iki kişinin, uygun gün içerisinden aynı doğum gününü paylaşma olasılığını belirtiyor ise, ulaşacağımız sonuç: Basit üssalma Herhangi iki kişinin aynı doğum gününe sahip olmama olasılığı ’tir. n kişinin olduğu bir odada çift insan, bir başka deyişle olay vardır. Hiçbir iki kişinin aynı doğum gününü paylaşmama olasılığı, bu olayların bağımsız olduğunu varsaymak ve olasılıklarını beraber çarpmak ile yaklaşık olarak bulunabilir. Kısaca kendisi ile kere çarpılır, bu da: Bu kimsenin aynı doğum gününe sahip olmama olasılığı olduğu için, birinin bir doğum günü paylaşma olasılığı: Poisson yaklaşımı Binom için Poisson yaklaşımının 23 kişilik gruba uygulanmasıyla, bu yüzden, Sonuç, önceki açıklamalar gibi %50’nin üzerindedir. Bu yaklaşım yukarıdaki kullanan Taylor açılımı yaklaşımıyla aynıdır. Kare yaklaşımı Zihinsel hesaplama için kullanılabilecek iyi bir kural, ayrıca şu şekilde de yazılabilir ’den küçük veya ’ye eşit olasılıklar için etkilidir. Bu denklemlerde, bir yıldaki gün sayısıdır. Örneğin, ortak bir doğum günü şansının olması için gereken kişi sayısını tahmin etmek için Bu da doğru cevap olan 23’ten çok uzak değildir. Kişi sayısı yaklaşımı Bu aynı zamanda, eşleşme şansın en az olması için gereken kişi sayısı, aşağıdaki formül kullanılarak yaklaşık olarak hesaplanabilir: Bu, olasılığı olan bir olayın, eğer kere tekrarlanırsa, en az bir kere gerçekleşme şansının olacağına dair iyi bir yaklaşımın sonucudur. Olasılık tablosu Bu tabloda açık renkli alanlar, belli bir bit boyutunda verilen özet alanı (satır) belirli çarpışma olasılığını (sütun) başarmak için gereken özet sayısını göstermektedir. Doğum günü benzetmesi kullanılarak: “özet alan boyutu” “uygun günler”e, “çarpışma olasılığı” “ortak doğum günü olasılığı”na ve “gerekli özet elementi sayısı” “bir grup içerisinden gerekli kişi sayısı”na benzemektedir. Bu grafik ayrıca gerekli minimum özet boyutunu (özet üst sınırları ve hata olasılığı verildiğinde) veya çarpışma olasılığını (sabit sayıda özet ve hata olasılığı için) belirlemek için de kullanılabilir. Karşılaştırma yapılırsa, ile , tipik bir sabit diskin bit olarak düzeltilemez hata oranıdır. Teorik olarak, gibi 128-bit özet fonksiyonları, olası çıktıları çok daha fazla olsa bile, yaklaşık belgeye kadar bu aralıkta kalmalıdır. Olasılık üst sınırı ve kişi sayısı alt sınırı Aşağıdaki argüman Paul Halmos'un bir görüşünden uyarlanmıştır. Yukarıda belirtildiği gibi, hiçbir iki doğum gününün örtüşmeme olasılığı Önceki paragraflardaki gibi, ’i sağlayan en küçük değeri ile veya ’i sağlayan en küçük değeri ile ilgilenilmektedir. eşitsizliği kullanılarak, yukarıdaki denklemde yerine yazıldığında Bu nedenle, yukarıdaki denklem yalnızca bir yaklaşım değil, aynı zamanda için bir üst sınırdır. Eşitsizlik olduğunu gösterir. için çözülürse Bu durumda, yaklaşık olarak 505.997’ye eşittir, ki bu 506’nın çok az altındadır, değeri iken elde edilir. Bu nedenle 23 kişi yeterlidir. Yeri gelmişken, denkleminin n için çözülmesi, yukarıda bahsedilen Frank H. Mathis’in formülünü yaklaşık olarak verir. Bu derivasyon sadece, eşit şansa sahip bir doğum günü eşleşmesi sağlamak için en fazla 23 kişiye ihtiyaç duyulduğunu göstermektedir; n’in 22 veya daha az olmasının işe yarama olasılığının ucunu açık bırakmaktadır. Genelleştirmeler Genelleştirilmiş doğum günü problemi Verilen adet güne sahip bir yılda, genelleştirilmiş doğum günü problemi, rastgele seçilen kişilik bir grupta bir doğum gününün örtüşme olasılığını en az %50 yapan minimum sayısını sorar. Başka bir deyişle, minimum tam sayısıdır öyle ki, Klasik doğum günü problemi bu nedenle, ’in belirlenmesine karşılık gelir. ’nin ilk 99 değeri burada verilmiştir : Benzer bir hesaplama, 341-372 aralığında olduğunda =23 olduğunu gösterir için bir dizi sınır ve formül yayınlanmıştır. Tüm için sayısı aşağıdaki eşitsizliği sağlar: Bu limitler, dizisinin aşağıdaki sayıya rastgele yakınlaşması açısından uygundur; aslında, alındığında maksimumdadır. Limitler, tüm olayların %99’unda ’nin tam değerini verecek kadar sıkıdır, örneğin . Genel olarak, bu sınırlardan ’nin daima ‘e eşit olduğu görülür; tavan fonksiyonunu ifade eder. Formül tüm tamsayı ’lerin %73’ü için geçerlidir. Formül neredeyse tüm ’ler için, yani asimptotik yoğunluğu 1 olan tam sayı kümesi için, geçerlidir. Formül için geçerlidir, ancak bu formüle sonsuz sayıda karşı örnek olduğu tahmin edilir. Formül için geçerlidir ve bu formülün tüm değerleri için geçerli olduğu tahmin edilir. 2 kişiden fazla Problem, gruptan en az 3/4/5 vb. kişinin aynı doğum gününü paylaşma olasılığının %50’den fazla olması için kaç kişilik bir grubun gerektiğini sormak için genişletilebilir. İlk birkaç değer şöyledir: 3 kişinin bir doğum günü paylaşma olasılığı>50% - 88 kişi; 4 kişinin bir doğum günü paylaşma olasılığı>50% - 187 kişi. Tüm liste Tam sayı Dizilerinin Çevrimiçi Ansiklopedisi’nin A014088 dizisinde bulunabilir. Bir çarpışma problemi olarak tahmin Doğum günü problemi aşağıdaki şekilde genelleştirilebilir: aralığındaki ayrı bir muntazam dağılımdan alınan rastgele tam sayı verildiğinde, en az iki sayının aynı olma olasılığı, nedir? ( olağan doğum günü problemini verir. ) Genel sonuçlar yukarıda verilen aynı argümanlar kullanılarak türetilebilir. Diğer taraftan, eğer en az iki sayının aynı olma olasılığını elde etmek için ’den alınan rastgele tamsayıların sayısını belirtirse, Daha genel anlamdaki bu doğum günü problemi özet fonksiyonları için geçerlidir: çarpışma almadan önce oluşturulabilecek - Bit özet sayısı değil, sadece 'dir. Bu, kriptografik karma işlevlerine yapılan doğum günü saldırıları tarafından istismar edilir ve doğum günü saldırıları az sayıda çarpışmanın, tüm pratik amaçlar için, kaçınılmaz olmasının nedenidir. Doğum günü probleminin arkasında yatan teori Zoe Schnabel Mark and recapture istatistikleri adı altında, göllerdeki balık popülasyonunun büyüklüğünü tahmin etmek için kullanılmıştır. Çoklu tip için genelleştirme küçükresim|En az bir erkek ve bir kadın arasındaki en az bir ortak doğum günü olasılığının grafiği Temel problem, tüm denemelerin tek bir “tip” olduğunu kabul eder. Doğum günü problemi, rastgele tip sayısını hesaba katmak için genelleştirilebilir. En basit kapsamda, erkek ve kadın olmak üzere iki tip insan vardır ve problem, en az bir erkek ve bir kadın arasındaki ortak doğum günü olasılığını simgeler. (İki erkek veya iki kadın arasındaki ortak doğum günleri sayılmaz.) Burada paylaşılan doğum günlerinin olmama olasılığı ve ikinci dereceden Stirling sayılarıdır. Dolayısıyla, istenen olasılık ’dır. Doğum günü probleminin bu değişimi ilginçtir çünkü toplam insan sayısı için tek özgün çözüm yoktur. Örneğin, olağan %50 olasılık değeri, hem 16 erkek ve 16 kadından oluşan 32 üyeli grup için hem de 43 kadın ve 6 erkekten oluşan 49 üyeli grup için gerçekleştirilir. Notlar Kaynakça Konuyla iligli yayınlar Kemeny, John G.; Snell, J. Laurie; Thompson, Gerald (1957). Introduction to Finite Mathematics (First ed.). Kategori:Matematiksel problemler Kategori

oğum günleri Kategori:Uygulamalı olasılık

Ara

Ara

Foruma hoş geldin 👋, Ziyaretçi

Doğum günü problemi

bullvar_katip

Administrator

Benzer konular

Tema özelleştirme sistemi

Tam ekran yada dar ekran

Izgara yada normal mod

Forum arkaplan resimleri

Sidebar blogunu kapat/aç

Yapışkan sidebar kapat/aç

Radius aç/kapat

Foruma hoş geldin 👋, Ziyaretçi