Doğum günü sorunu - Birthday problem

Bir doğum gününü paylaşan en az iki kişinin hesaplanan olasılığına karşı kişi sayısı

İçinde olasılık teorisi, doğum günü problemi veya doğum günü paradoksu ile ilgilidir olasılık bir dizi $n$ rastgele seçilmiş insanlar, bazı çiftleri aynı olacak doğum günü. Tarafından güvercin deliği ilkesi, kişi sayısı 367'ye ulaştığında olasılık% 100'e ulaşır (çünkü dahil olmak üzere yalnızca 366 olası doğum günü vardır 29 Şubat ). Ancak sadece 70 kişi ile% 99.9, 23 kişi ile% 50 olasılığa ulaşılır. Bu sonuçlar, yılın her gününün (29 Şubat hariç) bir doğum günü için eşit derecede olası olduğu varsayımına dayanmaktadır.

Gerçek doğum kayıtları, farklı günlerde farklı sayıda insanın doğduğunu göstermektedir. Bu durumda% 50 eşiğine ulaşmak için gereken kişi sayısının 23 olduğu gösterilebilir. veya daha az.^[1] Örneğin, insanların yarısı bir günde, diğer yarısı başka bir günde doğduysa, iki insanların doğum gününü paylaşma şansı% 50 olacaktır.

Sadece 23 kişilik bir grubun, gruptaki en az iki kişinin aynı doğum gününe sahip olma olasılığının% 50'ye ulaşması şaşırtıcı görünebilir: Bu sonuç belki de doğum günü karşılaştırmalarının aslında daha makul olacağı düşünüldüğünde daha makul hale getirilebilir. olası her bir çift arasında yapılmalı = 23 × 22/2 = 253 karşılaştırma, bu bir yıldaki gün sayısının yarısından fazlasıdır (en fazla 183), tek bir kişiye sabitlemek ve doğum gününü karşılaştırmak yerine herkesin. Doğum günü sorunu bir "paradoks "kendisiyle çelişen gerçek mantık anlamında, ancak ilk bakışta sadece sezgisel değil.

Doğum günü problemi için gerçek dünya uygulamaları, adı verilen bir kriptografik saldırı içerir. doğum günü saldırısı, bu olasılık modelini bir bulmanın karmaşıklığını azaltmak için kullanan çarpışma için Özet fonksiyonu ayrıca, belirli bir popülasyon boyutunun hash değerleri içinde var olan bir hash çarpışmasının yaklaşık riskini hesaplamak.

Sorunun geçmişi belirsizdir. Sonuç atfedildi Harold Davenport;^[2] ancak, bugün doğum günü sorunu olarak kabul edilen şeyin bir versiyonu daha önce önerilmişti Richard von Mises.^[3]

Olasılığın hesaplanması

Sorun, bir gruptaki yaklaşık bir olasılığı hesaplamaktır. $n$ en az iki kişi aynı doğum gününe sahiptir. Basit olması için dağıtımdaki varyasyonlar, örneğin artık yıllar, ikizler, mevsimsel veya hafta içi değişimler göz ardı edilir ve 365 olası doğum gününün hepsinin eşit derecede olası olduğu varsayılır. (Gerçek hayattaki doğum günü dağılımları tek tip değildir, çünkü tüm tarihler eşit derecede olası değildir, ancak bu düzensizliklerin analiz üzerinde çok az etkisi vardır.^{[nb 1]} Aslında, doğum tarihlerinin tek tip dağılımı en kötü durumdur.^[5])

Amaç hesaplamaktır $P (Bir)$ , odadaki en az iki kişinin aynı doğum gününe sahip olma olasılığı. Ancak hesaplamak daha kolaydır $P (Bir')$ , odadaki iki kişinin aynı doğum gününe sahip olmama olasılığı. Sonra çünkü $Bir$ ve $Bir'$ sadece iki olasılık ve aynı zamanda birbirini dışlayan, $P (Bir) = 1 - P (Bir').$

Yaygın olarak yayınlanan çözümlere saygı göstererek^{[hangi? ]} 23 kişinin sahip olmak için gerekli asgari insan sayısı olduğu sonucuna vararak $P (Bir)$ % 50'den büyük olan aşağıdaki hesaplama $P (Bir)$ 23 kişiyi örnek olarak kullanacak. 23 kişi 1'den 23'e kadar sayılırsa, Etkinlik 23 kişinin tümünün farklı doğum günlerine sahip olması, 2. kişinin 1. kişi ile aynı doğum gününe sahip olmaması ve 3. kişinin 1. kişi veya 2. kişi ile aynı doğum gününe sahip olmamasıyla aynıdır ve son olarak bu kişi 23, 1'den 22'ye kadar olan kişilerle aynı doğum gününe sahip değildir. Bu olayların sırasıyla "Olay 2", "Olay 3" olarak adlandırılmasına izin verin. Kişi 1'in doğum gününe sahip olması olayına karşılık gelen ve 1 olasılıkla meydana gelen bir "Olay 1" de eklenebilir. Olayların bu birleşimi, kullanılarak hesaplanabilir. şartlı olasılık: 2. kişi, 1. kişinin doğum günü dışında herhangi bir doğum gününe sahip olabileceğinden 2. olayın olasılığı 364/365 dir. Benzer şekilde, 3. kişinin herhangi birine sahip olabileceği için 2. olayın meydana gelmesi durumunda 3. olayın olasılığı 363/365 dir. 1. ve 2. kişiler tarafından henüz alınmamış doğum günleri. Bu, önceki tüm olayların meydana geldiği göz önüne alındığında, 23. olayın olasılığı en sonunda 343/365 olana kadar devam eder. Son olarak, koşullu olasılık ilkesi şunu ima eder: $P (Bir')$ bu bireysel olasılıkların ürününe eşittir:

{ displaystyle P (A ') = { frac {365} {365}} times { frac {364} {365}} times { frac {363} {365}} times { frac {362 } {365}} times cdots times { frac {343} {365}}}

(1)

Denklem terimleri (1) ulaşmak için toplanabilir:

{ displaystyle P (A ') = sol ({ frac {1} {365}} sağ) ^ {23} times (365 times 364 times 363 times cdots times 343)}

(2)

Denklemin değerlendirilmesi (2) verir $P (Bir') \approx 0.492703$

Bu nedenle, $P (Bir) \approx 1 - 0.492703 = 0.507297$ (50.7297%).

Bu süreç bir grup olarak genelleştirilebilir $n$ insanlar, nerede $p (n)$ en az ikisinin olasılığı $n$ insanlar doğum gününü paylaşıyor. İlk önce olasılığı hesaplamak daha kolay $p (n)$ hepsi bu $n$ doğum günleri farklı. Göre güvercin deliği ilkesi, $p (n)$ sıfır olduğunda $n > 365$ . Ne zaman $n \leq 365$ :

{ displaystyle { başlar {hizalı} { bar {p}} (n) & = 1 times left (1 - { frac {1} {365}} sağ) times sol (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 {hizalı}}}

nerede $!$ ... faktöryel Şebeke, $(365 n)$ ... binom katsayısı ve $k P r$ gösterir permütasyon.

Denklem, birinci kişinin doğum gününü paylaşacak kimsesi olmadığı, ikinci kişinin de birinciyle aynı doğum gününe sahip olamayacağı gerçeğini ifade eder (364/365), üçüncüsü ilk ikisinden biriyle aynı doğum gününe sahip olamaz (363/365) ve genel olarak $n$ doğum günü herhangi biriyle aynı olamaz $n - 1$ önceki doğum günleri.

Etkinlik en az ikisinin $n$ aynı doğum gününe sahip kişiler tamamlayıcı herkese $n$ doğum günleri farklı. Bu nedenle, olasılığı $p (n)$ dır-dir

{ displaystyle p (n) = 1 - { çubuğu {p}} (n).}

Aşağıdaki tablo, diğer bazı değerlerin olasılığını gösterir. $n$ (bu tablo için, artık yılların varlığı göz ardı edilir ve her doğum gününün eşit olasılık olduğu varsayılır):

İki kişinin bir grupta doğum gününü paylaşmama olasılığı

n

insanlar. Dikey ölçeğin logaritmik olduğuna dikkat edin (her aşağı adım 10²⁰ kat daha az olası).

$n$	$p (n)$
1	00.0%
5	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	99.99997%
200	99.9999999999999999999999999998%
300	(100 − 6×10⁻⁸⁰)%
350	(100 − 3×10⁻¹²⁹)%
365	(100 − 1.45×10⁻¹⁵⁵)%
≥ 366	100%

Artık yıllar. Formülde 365 yerine 366 koyarsak ${ displaystyle { bar {p}} (n)}$ Benzer bir hesaplama, artık yıllar için, bir maçın olasılığının% 50'den fazla olması için gereken kişi sayısının da 23 olduğunu göstermektedir; bu durumda bir eşleşme olasılığı% 50.6'dır.

Yaklaşımlar

Bir doğum gününü paylaşan en az iki kişinin yaklaşık olasılıklarını gösteren grafikler (kırmızı) ve tamamlayıcı olayı (mavi)

Yaklaşımın doğruluğunu gösteren bir grafik

1 - e -​ n 2 ⁄ 730

(kırmızı)

Taylor serisi genişlemesi üstel fonksiyon (sabit $e \approx 2.718 281828$ )

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

birinci dereceden bir yaklaşım sağlar $e x$ için ${ displaystyle | x | ll 1}$ :

{ displaystyle e ^ {x} yaklaşık 1 + x.}

Bu yaklaşımı, türetilen ilk ifadeye uygulamak için $p (n)$ , Ayarlamak $x = - a / 365$ . Böylece,

{ displaystyle e ^ {- a / 365} yaklaşık 1 - { frac {a} {365}}.}

Ardından, değiştirin $a$ formülündeki her terim için negatif olmayan tamsayılarla $p (n)$ a kadar $a = n - 1$ örneğin ne zaman $a = 1$ ,

{ displaystyle e ^ {- 1/365} yaklaşık 1 - { frac {1} {365}}.}

Türetilen ilk ifade $p (n)$ olarak tahmin edilebilir

{ displaystyle { begin {align} { bar {p}} (n) & yaklaşık 1 cdot e ^ {- 1/365} cdot e ^ {- 2/365} cdots e ^ {- ( n-1) / 365} [6pt] & = e ^ {- left. { big (} 1 + 2 + , cdots , + (n-1) { büyük)} sağ / 365} [6pt] & = e ^ {- (n (n-1) / 2) / 365} = e ^ {- n (n-1) / 730}. End {hizalı}}}

Bu nedenle,

{ displaystyle p (n) = 1 - { bar {p}} (n) yaklaşık 1-e ^ {- n (n-1) / 730}.}

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

{ displaystyle p (n) yaklaşık 1-e ^ {- n ^ {2} / 730},}

Bu, grafiğin gösterdiği gibi, hala oldukça doğrudur.

Yaklaşıma göre, aynı yaklaşım herhangi bir sayıda "insan" ve "gün" için uygulanabilir. 365 gün yerine $d$ , Eğer varsa $n$ kişiler ve eğer $n ≪ d$ , daha sonra yukarıdaki ile aynı yaklaşımı kullanarak şu sonucu elde ederiz: $p (n, d)$ en az ikisinin $n$ insanlar aynı doğum gününü bir dizi $d$ uygun günler, ardından:

{ displaystyle { başlar {hizalı} p (n, d) & yaklaşık 1-e ^ {- n (n-1) / (2d)} [6pt] ve yaklaşık 1-e ^ {- n ^ {2} / (2d)}. End {hizalı}}}

Basit bir üs alma

Herhangi iki kişinin aynı doğum gününe sahip olmama olasılığı 364/365. İçeren bir odada n insanlar var $(n 2) = n (n - 1) / 2$ insan çiftleri, yani $(n 2)$ Etkinlikler. Aynı doğum gününü paylaşmayan iki kişinin olasılığı, bu olayların bağımsız olduğunu varsayarak ve dolayısıyla olasılıklarını birlikte çarparak tahmin edilebilir. Kısacası 364/365 kendi başına çarpılabilir $(n 2)$ bize veren zamanlar

{ displaystyle { bar {p}} (n) yaklaşık sol ({ frac {364} {365}} sağ) ^ { binom {n} {2}}.}

Bu, hiç kimsenin aynı doğum gününe sahip olmaması olasılığı olduğundan, birinin doğum gününü paylaşma olasılığı

{ displaystyle p (n) yaklaşık 1- sol ({ frac {364} {365}} sağ) ^ { binom {n} {2}}.}

Poisson yaklaşımı

Uygulama Poisson 23 kişilik grup için iki terimli için yaklaşım,

{ displaystyle operatorname {Poi} sol ({ frac { binom {23} {2}} {365}} sağ) = operatorname {Poi} sol ({ frac {253} {365}} sağ) yaklaşık operatorname {Poi} (0,6932)}

yani

{ displaystyle Pr (X> 0) = 1- Pr (X = 0) yaklaşık 1-e ^ {- 0.6932} yaklaşık 1-0.499998 = 0.500002.}

Sonuç, önceki açıklamalara göre% 50'nin üzerindedir. Bu yaklaşım, kullanılan Taylor genişlemesine dayanan yukarıdaki ile aynıdır. ${ displaystyle e ^ {x} yaklaşık 1 + x}$ .

Kare yaklaşımı

İyi temel kural hangisi için kullanılabilir zihinsel hesaplama ilişki

{ displaystyle p (n) yaklaşık { frac {n ^ {2}} {2m}}}

olarak da yazılabilir

{ displaystyle n yaklaşık { sqrt {2m times p (n)}}}

şundan küçük veya eşit olasılıklar için iyi çalışan 1/2. Bu denklemlerde, $m$ bir yıldaki gün sayısıdır.

Örneğin, bir program için gereken kişi sayısını tahmin etmek için 1/2 ortak bir doğum günü şansı, alırız

{ displaystyle n yaklaşık { sqrt {2 times 365 times { tfrac {1} {2}}}} = { sqrt {365}} yaklaşık 19}

23'ün doğru cevabından çok uzak değil.

Kişi sayısının tahmini

Bu, aşağıdaki formül kullanılarak da tahmin edilebilir: numara en az bir 1/2 eşleşme şansı:

{ displaystyle n yaklaşık { tfrac {1} {2}} + { sqrt {{ tfrac {1} {4}} + 2 times ln (2) times 365}} = 22.999943.}

Bu, iyi bir kestirimin sonucudur. $1 / k$ olasılık bir 1/2 tekrarlanırsa en az bir kez olma şansı $k 2'de$ zamanlar.^[6]

Olasılık tablosu

uzunluğu onaltılık dizi	Hayır. nın-nin bitler ( $b$ )	karma boşluk boyut ( $2 b$ )	En az bir karma çarpışma olasılığı olacak şekilde karma oluşturulmuş öğelerin sayısı ≥ $p$
uzunluğu onaltılık dizi	Hayır. nın-nin bitler ( $b$ )	karma boşluk boyut ( $2 b$ )	$p$ = 10⁻¹⁸	$p$ = 10⁻¹⁵	$p$ = 10⁻¹²	$p$ = 10⁻⁹	$p$ = 10⁻⁶	$p$ = 0.001	$p$ = 0.01	$p$ = 0.25	$p$ = 0.50	$p$ = 0.75
8	32	4.3×10⁹	2	2	2	2.9	93	2.9×10³	9.3×10³	5.0×10⁴	7.7×10⁴	1.1×10⁵
(10)	(40)	(1.1×10¹²)	2	2	2	47	1.5×10³	4.7×10⁴	1.5×10⁵	8.0×10⁵	1.2×10⁶	1.7×10⁶
(12)	(48)	(2.8×10¹⁴)	2	2	24	7.5×10²	2.4×10⁴	7.5×10⁵	2.4×10⁶	1.3×10⁷	2.0×10⁷	2.8×10⁷
16	64	1.8×10¹⁹	6.1	1.9×10²	6.1×10³	1.9×10⁵	6.1×10⁶	1.9×10⁸	6.1×10⁸	3.3×10⁹	5.1×10⁹	7.2×10⁹
(24)	(96)	(7.9×10²⁸)	4.0×10⁵	1.3×10⁷	4.0×10⁸	1.3×10¹⁰	4.0×10¹¹	1.3×10¹³	4.0×10¹³	2.1×10¹⁴	3.3×10¹⁴	4.7×10¹⁴
32	128	3.4×10³⁸	2.6×10¹⁰	8.2×10¹¹	2.6×10¹³	8.2×10¹⁴	2.6×10¹⁶	8.3×10¹⁷	2.6×10¹⁸	1.4×10¹⁹	2.2×10¹⁹	3.1×10¹⁹
(48)	(192)	(6.3×10⁵⁷)	1.1×10²⁰	3.5×10²¹	1.1×10²³	3.5×10²⁴	1.1×10²⁶	3.5×10²⁷	1.1×10²⁸	6.0×10²⁸	9.3×10²⁸	1.3×10²⁹
64	256	1.2×10⁷⁷	4.8×10²⁹	1.5×10³¹	4.8×10³²	1.5×10³⁴	4.8×10³⁵	1.5×10³⁷	4.8×10³⁷	2.6×10³⁸	4.0×10³⁸	5.7×10³⁸
(96)	(384)	(3.9×10¹¹⁵)	8.9×10⁴⁸	2.8×10⁵⁰	8.9×10⁵¹	2.8×10⁵³	8.9×10⁵⁴	2.8×10⁵⁶	8.9×10⁵⁶	4.8×10⁵⁷	7.4×10⁵⁷	1.0×10⁵⁸
128	512	1.3×10¹⁵⁴	1.6×10⁶⁸	5.2×10⁶⁹	1.6×10⁷¹	5.2×10⁷²	1.6×10⁷⁴	5.2×10⁷⁵	1.6×10⁷⁶	8.8×10⁷⁶	1.4×10⁷⁷	1.9×10⁷⁷

Bu tablodaki daha açık alanlar, bit (satır) cinsinden belirli bir boyutta bir karma uzay verildiğinde verilen çarpışma olasılığını (sütun) elde etmek için gereken karma sayısını gösterir. Doğum günü benzetmesini kullanırsak: "hash space size" "mevcut günler" e, "çakışma olasılığı" "paylaşılan doğum günü olasılığı" na ve "gerekli hashing uygulanmış öğe sayısı" da "gerekli sayıda kişi" ye benzer. bir grup". Bu çizelge, gerekli minimum hash boyutunu (hashler ve hata olasılıkları üzerindeki üst sınırlar verildiğinde) veya çarpışma olasılığını (sabit sayıda hash ve hata olasılığı için) belirlemek için de kullanılabilir.

Karşılaştırma için, 10⁻¹⁸ -e 10⁻¹⁵ tipik bir sabit diskin düzeltilemez bit hata oranıdır.^[7] Teorik olarak 128 bitlik hash fonksiyonları, örneğin MD5, yaklaşık olana kadar bu aralık içinde kalmalı 8.2×10¹¹ belgeler, olası çıktıları çok daha fazla olsa bile.

Olasılık için bir üst sınır ve insan sayısı için bir alt sınır

Aşağıdaki argüman şu argümandan uyarlanmıştır: Paul Halmos.^{[nb 2]}

Yukarıda belirtildiği gibi, iki doğum gününün çakışmama olasılığı

{ displaystyle 1-p (n) = { bar {p}} (n) = prod _ {k = 1} ^ {n-1} sol (1 - { frac {k} {365}} sağ).}

Önceki paragraflarda olduğu gibi, ilgi en küçük olanda yatar $n$ öyle ki $p (n) > 1 / 2$ ; veya eşdeğer olarak, en küçük $n$ öyle ki $p (n) < 1 / 2$ .

Eşitsizliği kullanmak $1 - x < e - x$ yukarıdaki ifadede değiştiriyoruz $1 - k / 365$ ile $e - k ⁄ 365$ . Bu verir

{ displaystyle { bar {p}} (n) = prod _ {k = 1} ^ {n-1} sol (1 - { frac {k} {365}} sağ) < prod _ {k = 1} ^ {n-1} left (e ^ {- k / 365} sağ) = e ^ {- n (n-1) / 730}.}

Bu nedenle, yukarıdaki ifade yalnızca bir tahmin değil, aynı zamanda bir üst sınır nın-nin $p (n)$ . Eşitsizlik

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

ima eder $p (n) < 1 / 2$ . İçin çözme $n$ verir

{ displaystyle n ^ {2} -n> 730 ln 2.}

Şimdi, $730 ln 2$ yaklaşık 505,997'dir, bu da 506'nın hemen hemen altındadır, $n 2 - n$ ne zaman ulaşıldı $n = 23$ . Bu nedenle 23 kişi yeterlidir. Bu arada, çözme $n 2 - n = 730 ln 2$ için n Yukarıda bahsedilen Frank H. Mathis'in yaklaşık formülünü verir.

Bu türetme sadece şunu gösterir: en çok Eşit şansa sahip bir doğum günü maçı sağlamak için 23 kişiye ihtiyaç vardır; olasılığını açık bırakır $n$ 22 veya daha azı da işe yarayabilir.

Genellemeler

Genelleştirilmiş doğum günü sorunu

İle bir yıl verildi $d$ günler genelleştirilmiş doğum günü problemi asgari sayıyı sorar $n (d)$ öyle ki, bir dizi $n$ rastgele seçilen insanlar, doğum günü tesadüf olasılığı en az% 50'dir. Diğer bir deyişle, $n (d)$ minimum tam sayıdır $n$ öyle ki

{ displaystyle 1- sol (1 - { frac {1} {d}} sağ) sol (1 - { frac {2} {d}} sağ) cdots sol (1 - { frac {n-1} {d}} sağ) geq { frac {1} {2}}.}

Klasik doğum günü problemi bu nedenle belirlemeye karşılık gelir $n (365)$ . İlk 99 değeri $n (d)$ burada verilmiştir (sıra A033810 içinde OEIS ):

$d$	1–2	3–5	6–9	10–16	17–23	24–32	33–42	43–54	55–68	69–82	83–99
$n (d)$	2	3	4	5	6	7	8	9	10	11	12

Benzer bir hesaplama şunu göstermektedir: $n (d)$ = 23 ne zaman $d$ 341–372 aralığındadır.

İçin bir dizi sınır ve formül $n (d)$ yayınlandı.^[8]Herhangi $d \geq 1$ , numara $n (d)$ tatmin eder^[9]

{ displaystyle { frac {3-2 ln 2} {6}}

Bu sınırlar, dizinin $n (d) - \sqrt 2 d 2'de$ keyfi olarak yaklaşıyor

{ displaystyle { frac {3-2 ln 2} {6}} yaklaşık 0,27,}

varken

{ displaystyle 9 - { sqrt {86 ln 2}} yaklaşık 1,28}

maksimum olarak $d = 43$ .

Sınırlar, tam değerini verecek kadar sıkıdır. $n (d)$ örneğin tüm vakaların% 99'unda $n (365) = 23$ . Genel olarak, bu sınırlardan şu sonuç çıkar: $n (d)$ her zaman ikisine de eşittir

{ displaystyle sol lceil { sqrt {2d ln 2}} , sağ rceil quad { text {veya}} quad left lceil { sqrt {2d ln 2}} , doğru rceil +1}

nerede $⌈ \cdot ⌉$ gösterir tavan işlevi.Formül

{ displaystyle n (d) = sol lceil { sqrt {2d ln 2}} , sağ rceil}

tüm tam sayıların% 73'ü için tutar $d$ .^[10] Formül

{ displaystyle n (d) = sol lceil { sqrt {2d ln 2}} + { frac {3-2 ln 2} {6}} sağ rceil}

için tutar Neredeyse hepsi $d$ yani bir tam sayılar kümesi için $d$ ile asimptotik yoğunluk 1.^[10]

Formül

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

herkes için geçerli $d \leq 1018$ , ancak bu formül için sonsuz sayıda karşı örnek olduğu varsayılmaktadır.^[11]

Formül

{ displaystyle n (d) = sol 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}} sağ rceil}

herkes için geçerli $d \leq 1018$ ve bu formülün herkes için geçerli olduğu varsayılır. $d$ .^[11]

2 kişiden fazla

En az 3/4/5 / vb gibi bir olasılığın% 50'den fazla olması için bir grupta kaç kişinin gerekli olduğunu sorarak sorunu genişletmek mümkündür. grubun aynı doğum gününü paylaşıyor.

İlk birkaç değer aşağıdaki gibidir: 3 kişinin doğum gününü paylaşma olasılığı>% 50 - 88 kişi; 4 kişinin doğum gününü paylaşma olasılığı>% 50 - 187 kişi. Tam liste, Çevrimiçi Tamsayı Dizileri Ansiklopedisi'nin A014088 dizisi olarak bulunabilir.^[12]

Çarpışma sorunu olarak yayınlayın

Doğum günü problemi şu şekilde genelleştirilebilir:

Verilen

n

a'dan alınan rastgele tamsayılar ayrık düzgün dağılım menzil ile

[1, d]

, olasılık nedir

p (n; d)

en az iki sayı aynı mı? (

d = 365

olağan doğum günü problemini verir.)^[13]

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

{ displaystyle { begin {align} p (n; d) & = { begin {case} 1- displaystyle prod _ {k = 1} ^ {n-1} left (1 - { frac { k} {d}} sağ) & n leq d 1 & n> d end {vakalar}} [8px] & yaklaşık 1-e ^ {- { frac {n (n-1)} { 2d}}} & yaklaşık 1- sol ({ frac {d-1} {d}} sağ) ^ { frac {n (n-1)} {2}} end {hizalı} }}

Tersine, eğer $n (p; d)$ gelen rastgele tamsayıların sayısını gösterir $[1, d]$ bir olasılık elde etmek $p$ en az iki sayının aynı olduğunu

{ displaystyle n (p; d) yaklaşık { sqrt {2d cdot ln sol ({ frac {1} {1-p}} sağ)}}.}

Bu daha genel anlamda doğum günü sorunu şunlara uygulanır: karma işlevler: beklenen sayı $N$ -bit Bir çarpışmadan önce oluşturulabilen hash'ler, $2 N$ , daha ziyade sadece $2 N ⁄ 2$ . Bu, tarafından istismar edilmektedir doğum günü saldırıları açık kriptografik hash fonksiyonları ve neden az sayıda çarpışmanın bir karma tablo tüm pratik amaçlar için kaçınılmazdır.

Doğum günü sorununun arkasındaki teori Zoe Schnabel tarafından kullanıldı^[14] adı altında yakalama-yeniden yakalama göllerdeki balık popülasyonunun büyüklüğünü tahmin etmek için istatistikler.

Birden çok türe genelleme

En az bir erkek ve bir kadın arasında en az bir ortak doğum günü olma olasılığının grafiği

Temel problem, tüm denemelerin tek bir "tip" olduğunu düşünür. Doğum günü sorunu, keyfi sayıda türü dikkate alacak şekilde genelleştirilmiştir.^[15] En basit uzantıda iki tür insan vardır: $m$ adam ve $n$ kadın ve sorun, en az bir erkek ve bir kadın arasında paylaşılan bir doğum günü olasılığını karakterize etmeye başlar. (İki erkek veya iki kadın arasında paylaşılan doğum günleri sayılmaz.) Burada doğum günlerinin paylaşılmama olasılığı:

{ displaystyle p_ {0} = { frac {1} {d ^ {m + n}}} toplamı _ {i = 1} ^ {m} toplamı _ {j = 1} ^ {n} S_ { 2} (m, i) S_ {2} (n, j) prod _ {k = 0} ^ {i + j-1} dk}

nerede $d = 365$ ve $S 2$ vardır İkinci türden Stirling sayıları. Sonuç olarak, istenen olasılık $1 - p 0$ .

Doğum günü sorununun bu varyasyonu ilginç çünkü toplam insan sayısı için benzersiz bir çözüm yok $m + n$ . Örneğin, normal% 50 olasılık değeri hem 16 erkek ve 16 kadın 32 üyeli bir grup hem de 43 kadın ve 6 erkekten oluşan 49 üyeli bir grup için gerçekleştirilmiştir.

Diğer doğum günü sorunları

İlk maç

Bununla ilgili bir soru, insanlar birer birer odaya girdiklerinde, hangisinin daha önce odada bulunan biriyle aynı doğum gününe sahip olma olasılığı en yüksek olanıdır? Yani ne için $n$ dır-dir $p (n) - p (n - 1)$ maksimum? Cevap 20'dir - ilk maç için bir ödül varsa, sıradaki en iyi sıra 20. sıradadır.^{[kaynak belirtilmeli ]}

Seninle aynı doğum günü

Karşılaştırma

p (n)

= doğum günü maç olasılığı

q (n)

= eşleşme olasılığı sizin doğum günü

Doğum günü probleminde iki kişi de önceden seçilmemiştir. Aksine, olasılık $q (n)$ şu odadaki biri $n$ diğer insanların doğum günüyle aynı belirli kişi (örneğin, siz) tarafından verilir

{ displaystyle q (n) = 1- sol ({ frac {365-1} {365}} sağ) ^ {n}}

ve genel olarak $d$ tarafından

{ displaystyle q (n; d) = 1- sol ({ frac {d-1} {d}} sağ) ^ {n}.}

Standart durumda $d = 365$ , ikame $n = 23$ yaklaşık% 6,1 verir, bu da 16'da 1'den az şanstır.% 50'den fazla bir şans için bir odadaki bir kişinin $n$ insanlar aynı doğum gününe sahip sen, $n$ en az 253 olması gerekir. Bu sayı, $365 / 2 = 182.5$ : nedeni, odadaki diğer insanlar arasında bazı doğum günü maçlarının olması muhtemeldir.

Yakın maçlar

Diğer bir genelleme, bir grupta en az bir çift bulma olasılığını sormaktır. $n$ içinde doğum günleri olan insanlar $k$ birbirinin takvim günleri, varsa $d$ eşit olasılıkla doğum günleri.^[16]

{ displaystyle { başlar {hizalı} p (n, k, d) & = 1 - { frac {(d-nk-1)!} {d ^ {n-1} { bigl (} dn (k +1) { bigr)}!}} End {hizalı}}}

Bazı çiftlerin bir doğum gününe sahip olma olasılığının ile ayrılmış olan kişi sayısı $k$ gün veya daha az günlerin% 50'den fazla olacağı aşağıdaki tabloda verilmiştir:

$k$	$n$ için $d = 365$
0	23
1	14
2	11
3	9
4	8
5	8
6	7
7	7

Bu nedenle, rastgele yedi kişiden oluşan bir grupta, bir hafta arayla ikisinin doğum gününe sahip olmaması daha olasıdır.^[16]

Çarpışma sayımı

Olasılık $k$ rastgele seçilen tamsayı $[1, d]$ en az bir önceki seçim eşittir $q (k - 1; d)$ yukarıda. Bir seçimin bir önceki seçimi şu şekilde tekrarlayacağı beklenen toplam sayı: $n$ bu tür tam sayılar eşit olarak seçilir^[17]

{ displaystyle toplamı _ {k = 1} ^ {n} q (k-1; d) = n-d + d sol ({ frac {d-1} {d}} sağ) ^ {n }.}

Ortalama kişi sayısı

Doğum günü probleminin alternatif bir formülasyonunda, kişi şu soruyu sorar: ortalama aynı doğum gününe sahip bir çift bulmak için gereken kişi sayısı. Olasılık fonksiyonunu düşünürsek Pr [ $n$ kişinin en az bir paylaşılan doğum günü var], bu ortalama belirleniyor anlamına gelmek dağıtımın, alışılmış formülasyonun aksine, medyan. Sorun birkaçıyla ilgili karma algoritmalar tarafından analiz edildi Donald Knuth kitabında Bilgisayar Programlama Sanatı. Gösterilebilir^[18]^[19] büyüklükteki bir popülasyondan ikame ile tekdüze numuneler varsa $M$ , ilk tekrarlanan örnekleme için gerekli deneme sayısı biraz bireysel var beklenen değer $n = 1 + Q (M)$ , nerede

{ displaystyle Q (M) = toplam _ {k = 1} ^ {M} { frac {M!} {(M-k)! M ^ {k}}}.}

İşlev

{ displaystyle Q (M) = 1 + { frac {M-1} {M}} + { frac {(M-1) (M-2)} {M ^ {2}}} + cdots + { frac {(M-1) (M-2) cdots 1} {M ^ {M-1}}}}

tarafından incelendi Srinivasa Ramanujan ve sahip asimptotik genişleme:

{ displaystyle Q (M) sim { sqrt { frac { pi M} {2}}} - { frac {1} {3}} + { frac {1} {12}} { sqrt { frac { pi} {2M}}} - { frac {4} {135M}} + cdots.}

İle $M = 365$ aynı doğum gününe sahip bir çift bulmak için gereken ortalama kişi sayısı $n = 1 + Q (M) \approx 24.61659$ % 50 şans için gereken sayı 23'ten biraz fazla. En iyi durumda, iki kişi yeterli olacaktır; en kötüsü, mümkün olan maksimum sayı $M + 1 = 366$ insanlara ihtiyaç var; ancak ortalama olarak sadece 25 kişi gereklidir

Gösterge rastgele değişkenleri kullanan bir analiz, bu sorunun daha basit ancak yaklaşık bir analizini sağlayabilir.^[20] Bir odadaki k kişi için her bir çift (i, j) için, indikatör rastgele değişken X'i tanımlarız._ij, için ${ displaystyle 1 leq i leq j leq k}$ , tarafından

${ displaystyle { begin {alignat} {2} X_ {ij} & = I {{ text {kişi}} i { text {ve kişi}} j { text {aynı doğum gününe sahip}} } & = { başla {vakalar} 1 ve { text {eğer kişi}} i { text {ve kişi}} j { text {aynı doğum gününe sahipler;}} 0 ve { text {aksi halde.}} end {vakalar}} end {alignat}}}$

${ displaystyle { begin {alignat} {2} E [X_ {ij}] & = Pr {{ text {kişi}} i { text {ve kişi}} j { text {aynı doğum gününe sahip }} } & = 1 / n end {hizalı}}}$

X, aynı doğum gününe sahip bireylerin çiftlerini sayan rastgele bir değişken olsun.

${ displaystyle X = toplam _ {i = 1} ^ {k} toplam _ {j = i + 1} ^ {k} X_ {ij}}$

${ displaystyle { begin {alignat} {3} E [X] & = sum _ {i = 1} ^ {k} sum _ {j = i + 1} ^ {k} E [X_ {ij} ] & = { binom {k} {2}} { frac {1} {n}} & = { frac {k (k-1)} {2n}} end {alignat }}}$

İçin $n = 365$ , Eğer $k = 28$ , aynı doğum gününe sahip beklenen sayı: ${ displaystyle (28 cdot 27) / (2 cdot 365) yaklaşık 1.0356.}$ Bu nedenle, en az 28 kişiden oluşan en az bir eşleşen çift bekleyebiliriz.

Sorunun resmi olmayan bir gösterimi, Avustralya başbakanları listesi 2017 yılı itibarıyla 29'u olan^{[Güncelleme]}içinde Paul Keating, 24. başbakan ve Edmund Barton, ilk başbakan, aynı doğum gününü paylaşıyor, 18 Ocak.

İçinde 2014 FIFA Dünya Kupası 32 takımın her birinin 23 oyuncusu vardı. Resmi kadro listelerinin analizi, 16 takımın doğum günlerini paylaşan çift oyuncuları olduğunu ve bu 5 takımın iki çifti olduğunu gösterdi: Arjantin, Fransa, İran, Güney Kore ve İsviçre'nin her birinin iki çifti ve Avustralya, Bosna Hersek, Brezilya , Kamerun, Kolombiya, Honduras, Hollanda, Nijerya, Rusya, İspanya ve ABD'nin her biri bir çift ile.^[21]

Voracek, Tran ve Formann insanların çoğunluğunun, belirli bir doğum gününe sahip olma olasılığını elde etmek için gerekli olan kişi sayısını belirgin şekilde fazla tahmin ettiğini ve belirli bir örneklem büyüklüğü verildiğinde aynı doğum gününe sahip olma olasılığını önemli ölçüde küçümsediğini gösterdi.^[22] Diğer sonuçlar, psikoloji öğrencilerinin ve kadınların görevde kumarhane ziyaretçilerinden / personelinden veya erkeklerden daha iyi performans gösterdiği, ancak tahminlerinden daha az emin olduklarıydı.

Ters problem

Tersi problem, sabit bir olasılık için bulmaktır $p$ ,en iyisi $n$ olasılık için $p (n)$ verilenden daha küçük $p$ veya en küçüğü $n$ olasılık için $p (n)$ verilenden daha büyük $p$ .^{[kaynak belirtilmeli ]}

Yukarıdaki formülü almak $d = 365$ , birinde var

{ displaystyle n (p; 365) yaklaşık { sqrt {730 ln left ({ frac {1} {1-p}} sağ)}}.}

Aşağıdaki tablo bazı örnek hesaplamalar vermektedir.

$p$	$n$	$n ↓$	$p (n ↓)$	$n ↑$	$p (n ↑)$
0.01	0.14178√365 = 2.70864	2	0.00274	3	0.00820
0.05	0.32029√365 = 6.11916	6	0.04046	7	0.05624
0.1	0.45904√365 = 8.77002	8	0.07434	9	0.09462
0.2	0.66805√365 = 12.76302	12	0.16702	13	0.19441
0.3	0.84460√365 = 16.13607	16	0.28360	17	0.31501
0.5	1.17741√365 = 22.49439	22	0.47570	23	0.50730
0.7	1.55176√365 = 29.64625	29	0.68097	30	0.70632
0.8	1.79412√365 = 34.27666	34	0.79532	35	0.81438
0.9	2.14597√365 = 40.99862	40	0.89123	41	0.90315
0.95	2.44775√365 = 46.76414	46	0.94825	47	0.95477
0.99	3.03485√365 = 57.98081	57	0.99012	58	0.99166

Sınırların dışında kalan bazı değerler renkli yaklaşıklığın her zaman kesin olmadığını göstermek için.

Bölme sorunu

İlgili bir sorun da bölüm sorunu, bir çeşidi sırt çantası sorunu yöneylem araştırmasından. Bazı ağırlıklar bir denge ölçeği; her ağırlık, bir gram ile bir milyon gram (bir gram) arasında rastgele seçilen bir gram tamsayıdır. ton ). Soru, tartıyı dengelemek için kişinin genellikle (yani 1'e yakın olasılıkla) ağırlıkları sol ve sağ kollar arasında transfer edip edemeyeceğidir. (Tüm ağırlıkların toplamının tek sayıda gram olması durumunda, bir gramlık farklılığa izin verilir.) Yalnızca iki veya üç ağırlık varsa, cevap açıkça hayırdır; işe yarayan bazı kombinasyonlar olmasına rağmen, rastgele seçilen üç ağırlığın çoğu kombinasyonunda çalışmaz. Çok fazla ağırlık varsa, cevap açıkça evettir. Soru şu ki, kaç tane yeterlidir? Yani, imkansız olduğu için onları dengelemenin eşit derecede mümkün olduğu ağırlıkların sayısı nedir?

Çoğu zaman, insanların sezgileri cevabın yukarıda olduğudur. 100000. Çoğu insanın sezgisi, bunun binlerce veya onbinlerce olduğu yönündeyken, diğerleri bunun en azından yüzlerce olması gerektiğini düşünüyor. Doğru cevap 23'tür.^{[kaynak belirtilmeli ]}

Bunun nedeni, doğru karşılaştırmanın ağırlıkların sola ve sağa bölüm sayısı ile olmasıdır. Var $2 N - 1$ için farklı bölümler $N$ ağırlıklar ve sol toplam eksi sağ toplam, her bölüm için yeni bir rastgele miktar olarak düşünülebilir. Ağırlıkların toplamının dağılımı yaklaşık olarak Gauss zirvede $1000000 N$ ve genişlik $1000000 \sqrt N$ , böylece ne zaman $2 N - 1$ yaklaşık olarak eşittir $1000000 \sqrt N$ geçiş gerçekleşir. 2^{23 − 1} yaklaşık 4 milyon, dağıtımın genişliği ise sadece 5 milyon.^[23]

Kurguda

Arthur C. Clarke romanı Ay Çöküşü 1961'de yayınlanan, belirsiz bir süre boyunca yeraltında mahsur kalan ana karakterlerin bir doğum gününü kutladıkları ve kendilerini doğum günü sorununun geçerliliğini tartışırken buldukları bir bölüm içeriyor. Bir fizikçi yolcunun belirttiği gibi: "Yirmi dört kişiden fazla bir grubunuz varsa, olasılıklar ikisinin aynı doğum gününe sahip olmasından bile daha iyidir." Sonunda, mevcut 22 kişiden iki karakterin aynı doğum gününü paylaştığı ortaya çıktı, 23 Mayıs.

Notlar

^
Gerçekte, doğum günleri yıl boyunca eşit olarak dağıtılmaz; bazı mevsimlerde diğerlerine göre günde daha fazla doğum olur, ancak bu sorunun amaçları doğrultusunda dağılım tek tip olarak ele alınır. Özellikle yaz aylarında, özellikle Ağustos ve Eylül aylarında (kuzey yarımküre için) birçok çocuk doğar. [1] ve ABD'de pek çok çocuğun tatillerinde gebe kaldığı kaydedildi. Noel ve Yeni Yıl Günü.^[1] Ayrıca, hastaneler nadiren sezaryen bölümleri ve indüklenmiş emek hafta sonu, hafta sonlarına göre Salı ve Cuma günleri arasında daha fazla insan doğar;^[1] İnsanların çoğunun bir doğum yılını paylaştığı durumlarda (örneğin, bir okuldaki sınıf), bu belirli tarihlere doğru bir eğilim yaratır. İsveç'te nüfusun% 9,3'ü Mart'ta ve% 7,3'ü Kasım'da, tekdüze bir dağılımın% 8,3 vereceği Kasım'da doğar İsveç istatistik kurulu. Ayrıca bakınız:
- Murphy, Ron. "Bir Takvim Yılındaki Doğum Günlerinin Dağılımının Analizi". Alındı 2011-12-27.
- Mathers, C D; RS Harris (1983). "Avustralya'daki Doğumların Mevsimsel Dağılımı". Uluslararası Epidemiyoloji Dergisi. 12 (3): 326–331. doi:10.1093 / ije / 12.3.326. PMID 6629621. Alındı 2011-12-27.
Bu faktörler, daha yoğun bir alt kümenin daha olası çiftlere sahip olması nedeniyle aynı doğum tarihlerinin olasılığını artırma eğilimindedir (herkesin üç günde doğduğu aşırı durumda, açıkça birçok aynı doğum günü olacaktır). Yılın her gününde meydana gelen tek tip olmayan doğum sayısı sorunu ilk olarak Murray Klamkin 1967'de.^[4] Bloom tarafından doğum günlerinin tekdüze bir dağılımı için iki doğum günü olasılığının en az olduğuna dair resmi bir kanıt verildi (Bloom 1973 ).
^ Otobiyografisinde Halmos, doğum günü paradoksunun sıklıkla sunulduğu biçimi sayısal hesaplama açısından eleştirdi. Daha soyut matematiksel kavramların kullanımında örnek olarak kullanılması gerektiğine inanıyordu. O yazdı:
Muhakeme, tüm matematik öğrencilerinin kolayca erişebilmesi gereken önemli araçlara dayanmaktadır. Doğum günü problemi, saf düşüncenin mekanik manipülasyona göre avantajlarının muhteşem bir örneğiydi; eşitsizlikler bir veya iki dakika içinde elde edilebilir, oysa çarpımlar çok daha uzun sürer ve enstrüman ister kalem ister eski moda bir masaüstü bilgisayar olsun, çok daha fazla hataya maruz kalır. Ne hesap makineleri Verme anlayış, matematiksel kolaylık veya daha gelişmiş, genelleştirilmiş teoriler için sağlam bir temeldir.

Referanslar

^ ^a ^b ^c Mario Cortina Borja; John Haigh (Eylül 2007). "Doğum Günü Problemi". Önem. Kraliyet İstatistik Derneği. 4 (3): 124–127. doi:10.1111 / j.1740-9713.2007.00246.x.
^ W. W. Rouse Ball ve H.S.M. Coxeter, "Matematiksel Rekreasyonlar ve Denemeler, 13. baskı", Dover Yayınları, New York, 1987, s 45.
^ Frank, P .; Goldstein, S .; Kac, M .; Prager, W .; Szegö, G .; Birkhoff, G., eds. (1964). Richard von Mises'in Seçilmiş Makaleleri. 2. Providence, Rhode Island: Amer. Matematik. Soc. sayfa 313–334.
^ Klamkin ve Newman 1967.
^ Steele, J. Michael (2004). Cauchy ‑ Schwarz Master Sınıfı. Cambridge: Cambridge University Press. pp.206, 277. ISBN 9780521546775.
^ Mathis, Frank H. (Haziran 1991). "Genelleştirilmiş Bir Doğum Günü Problemi". SIAM İncelemesi. 33 (2): 265–270. doi:10.1137/1033051. ISSN 0036-1445. JSTOR 2031144. OCLC 37699182.
^ Jim Gray, Catharine van Ingen. Disk Arıza Oranlarının ve Hata Oranlarının Ampirik Ölçümleri
^ D. Brink, Doğum Günü Problemine (muhtemelen) kesin bir çözüm, Ramanujan Journal, 2012, [2].
^ Brink2012, Teorem 2
^ ^a ^b Brink2012, Teorem 3
^ ^a ^b Brink2012, Tablo 3, Varsayım 1
^ "Bir yılda en az n tane rastlantısal doğum gününe sahip olma olasılığını% 50 verecek minimum insan sayısı". Tam Sayı Dizilerinin Çevrimiçi Ansiklopedisi. OEIS. Alındı 17 Şubat 2020.
^ Suzuki, K .; Tonien, D .; et al. (2006). "Çoklu çarpışmalar için Doğum Günü Paradoksu". Rhee M.S., Lee B. (ed.). Bilgisayar Bilimi Ders Notları, cilt 4296. Berlin: Springer. doi:10.1007/11927587_5. Bilgi Güvenliği ve Kriptoloji - ICISC 2006.
^ Z.E. Schnabel (1938) Bir Gölün Toplam Balık Popülasyonunun Tahmini, American Mathematical Monthly 45, 348–352.
^ M. C. Wendl (2003) Rastgele Değişken Kümeleri Arasında Çarpışma Olasılığı, İstatistik ve Olasılık Mektupları 64(3), 249–254.
^ ^a ^b M. Abramson ve W. O. J. Moser (1970) Daha Fazla Doğum Günü Sürprizi, American Mathematical Monthly 77, 856–858
^ Olabilir Matt. "Doğum günü paradoksu ile çarpışma hash çarpışmaları". Matt Might'ın blogu. Alındı 17 Temmuz 2015.
^ Knuth, D. E. (1973). Bilgisayar Programlama Sanatı. Cilt 3, Sıralama ve Arama. Okuma, Massachusetts: Addison-Wesley. ISBN 978-0-201-03803-3.
^ Flajolet, P .; Grabner, P. J .; Kirschenhofer, P .; Prodinger, H. (1995). "Ramanujan'ın Q-Fonksiyonu Üzerine". Hesaplamalı ve Uygulamalı Matematik Dergisi. 58: 103–116. doi:10.1016 / 0377-0427 (93) E0258-N.
^ Cormen; et al. Algoritmalara Giriş.
^ Fletcher, James (16 Haziran 2014). "Dünya Kupası'ndaki doğum günü paradoksu". bbc.com. BBC. Alındı 27 Ağustos 2015.
^ Voracek, M .; Tran, U. S .; Formann, A. K. (2008). "Doğum günü ve doğum sorunları: Psikoloji lisans öğrencileri ve kumarhane ziyaretçileri ve personeli arasında olasılık yanılgıları". Algısal ve Motor Beceriler. 106 (1): 91–103. doi:10.2466 / pms.106.1.91-103. PMID 18459359. S2CID 22046399.
^ Borgs, C .; Chayes, J .; Pittel, B. (2001). "Tamsayı Bölme Probleminde Faz Geçişi ve Sonlu Boyut Ölçeklendirme". Rastgele Yapılar ve Algoritmalar. 19 (3–4): 247–288. doi:10.1002 / rsa.10004. S2CID 6819493.

Kaynakça

Abramson, M .; Moser, W. O. J. (1970). "Daha Fazla Doğum Günü Sürprizi". American Mathematical Monthly. 77 (8): 856–858. doi:10.2307/2317022. JSTOR 2317022.
Bloom, D. (1973). "Bir Doğum Günü Problemi". American Mathematical Monthly. 80 (10): 1141–1142. doi:10.2307/2318556. JSTOR 2318556.
Kemeny, John G .; Snell, J. Laurie; Thompson, Gerald (1957). Sonlu Matematiğe Giriş (İlk baskı).
Klamkin, M .; Newman, D. (1967). "Doğum Günü Sürprizinin Uzantıları". Kombinatoryal Teori Dergisi. 3 (3): 279–282. doi:10.1016 / s0021-9800 (67) 80075-9.
McKinney, E.H. (1966). "Genelleştirilmiş Doğum Günü Problemi". American Mathematical Monthly. 73 (4): 385–387. doi:10.2307/2315408. JSTOR 2315408.
Schneps, Leila; Colmez, Coralie (2013). "Matematik hatası 5. Diana Sylvester vakası: soğuk vuruş analizi". Denemede Matematik. Mahkeme Salonunda Sayılar Nasıl Kullanılır ve Kötüye Kullanılır?. Temel Kitaplar. ISBN 978-0-465-03292-1.
Sy M. Blinder (2013). Temel Matematik Rehberi: Fizik, Kimya ve Mühendislik Öğrencileri İçin Bir İnceleme. Elsevier. s. 5–6. ISBN 978-0-12-407163-6.

Dış bağlantılar

Artık yıl doğum günleri için Doğum Günü Paradoksu muhasebesi
Weisstein, Eric W. "Doğum Günü Problemi". MathWorld.
Paradoksu açıklayan mizahi bir makale
SOCR EduMaterials etkinlikleri doğum günü deneyi
Doğum Günü Problemini Anlamak (Daha İyi Açıklanmış)
Eurobirthdays 2012. Doğum günü problemi. Doğum günü paradoksunun pratik bir futbol örneği.
Grime, James. "23: Doğum Günü Olasılığı". Numberphile. Brady Haran. Arşivlenen orijinal 2017-02-25 tarihinde. Alındı 2013-04-02.
WolframAlpha'da Doğum Günü Probleminin olasılıklarının hesaplanması

[nonuniform_birthdays-5] Gerçekte, doğum günleri yıl boyunca eşit olarak dağıtılmaz; bazı mevsimlerde diğerlerine göre günde daha fazla doğum olur, ancak bu sorunun amaçları doğrultusunda dağılım tek tip olarak ele alınır. Özellikle yaz aylarında, özellikle Ağustos ve Eylül aylarında (kuzey yarımküre için) birçok çocuk doğar. [1] ve ABD'de pek çok çocuğun tatillerinde gebe kaldığı kaydedildi. Noel ve Yeni Yıl Günü.^[1] Ayrıca, hastaneler nadiren sezaryen bölümleri ve indüklenmiş emek hafta sonu, hafta sonlarına göre Salı ve Cuma günleri arasında daha fazla insan doğar;^[1] İnsanların çoğunun bir doğum yılını paylaştığı durumlarda (örneğin, bir okuldaki sınıf), bu belirli tarihlere doğru bir eğilim yaratır. İsveç'te nüfusun% 9,3'ü Mart'ta ve% 7,3'ü Kasım'da, tekdüze bir dağılımın% 8,3 vereceği Kasım'da doğar İsveç istatistik kurulu. Ayrıca bakınız:
Murphy, Ron. "Bir Takvim Yılındaki Doğum Günlerinin Dağılımının Analizi". Alındı 2011-12-27.
Mathers, C D; RS Harris (1983). "Avustralya'daki Doğumların Mevsimsel Dağılımı". Uluslararası Epidemiyoloji Dergisi. 12 (3): 326–331. doi:10.1093 / ije / 12.3.326. PMID 6629621. Alındı 2011-12-27.
Bu faktörler, daha yoğun bir alt kümenin daha olası çiftlere sahip olması nedeniyle aynı doğum tarihlerinin olasılığını artırma eğilimindedir (herkesin üç günde doğduğu aşırı durumda, açıkça birçok aynı doğum günü olacaktır). Yılın her gününde meydana gelen tek tip olmayan doğum sayısı sorunu ilk olarak Murray Klamkin 1967'de.^[4] Bloom tarafından doğum günlerinin tekdüze bir dağılımı için iki doğum günü olasılığının en az olduğuna dair resmi bir kanıt verildi (Bloom 1973 ).

[2] Murphy, Ron. "Bir Takvim Yılındaki Doğum Günlerinin Dağılımının Analizi". Alındı 2011-12-27.

[3] Mathers, C D; RS Harris (1983). "Avustralya'daki Doğumların Mevsimsel Dağılımı". Uluslararası Epidemiyoloji Dergisi. 12 (3): 326–331. doi:10.1093 / ije / 12.3.326. PMID 6629621. Alındı 2011-12-27.

[9] Otobiyografisinde Halmos, doğum günü paradoksunun sıklıkla sunulduğu biçimi sayısal hesaplama açısından eleştirdi. Daha soyut matematiksel kavramların kullanımında örnek olarak kullanılması gerektiğine inanıyordu. O yazdı:
Muhakeme, tüm matematik öğrencilerinin kolayca erişebilmesi gereken önemli araçlara dayanmaktadır. Doğum günü problemi, saf düşüncenin mekanik manipülasyona göre avantajlarının muhteşem bir örneğiydi; eşitsizlikler bir veya iki dakika içinde elde edilebilir, oysa çarpımlar çok daha uzun sürer ve enstrüman ister kalem ister eski moda bir masaüstü bilgisayar olsun, çok daha fazla hataya maruz kalır. Ne hesap makineleri Verme anlayış, matematiksel kolaylık veya daha gelişmiş, genelleştirilmiş teoriler için sağlam bir temeldir.

[Borja-1] Mario Cortina Borja; John Haigh (Eylül 2007). "Doğum Günü Problemi". Önem. Kraliyet İstatistik Derneği. 4 (3): 124–127. doi:10.1111 / j.1740-9713.2007.00246.x.

[2] W. W. Rouse Ball ve H.S.M. Coxeter, "Matematiksel Rekreasyonlar ve Denemeler, 13. baskı", Dover Yayınları, New York, 1987, s 45.

[3] Frank, P .; Goldstein, S .; Kac, M .; Prager, W .; Szegö, G .; Birkhoff, G., eds. (1964). Richard von Mises'in Seçilmiş Makaleleri. 2. Providence, Rhode Island: Amer. Matematik. Soc. sayfa 313–334.

[FOOTNOTEKlamkinNewman1967-4] Klamkin ve Newman 1967.

[6] Steele, J. Michael (2004). Cauchy ‑ Schwarz Master Sınıfı. Cambridge: Cambridge University Press. pp.206, 277. ISBN 9780521546775.

[7] Mathis, Frank H. (Haziran 1991). "Genelleştirilmiş Bir Doğum Günü Problemi". SIAM İncelemesi. 33 (2): 265–270. doi:10.1137/1033051. ISSN 0036-1445. JSTOR 2031144. OCLC 37699182.

[8] Jim Gray, Catharine van Ingen. Disk Arıza Oranlarının ve Hata Oranlarının Ampirik Ölçümleri

[10] D. Brink, Doğum Günü Problemine (muhtemelen) kesin bir çözüm, Ramanujan Journal, 2012, [2].

[11] Brink2012, Teorem 2

[Brink-12] Brink2012, Teorem 3

[ReferenceA-13] Brink2012, Tablo 3, Varsayım 1

[14] "Bir yılda en az n tane rastlantısal doğum gününe sahip olma olasılığını% 50 verecek minimum insan sayısı". Tam Sayı Dizilerinin Çevrimiçi Ansiklopedisi. OEIS. Alındı 17 Şubat 2020.

[15] Suzuki, K .; Tonien, D .; et al. (2006). "Çoklu çarpışmalar için Doğum Günü Paradoksu". Rhee M.S., Lee B. (ed.). Bilgisayar Bilimi Ders Notları, cilt 4296. Berlin: Springer. doi:10.1007/11927587_5. Bilgi Güvenliği ve Kriptoloji - ICISC 2006.

[16] Z.E. Schnabel (1938) Bir Gölün Toplam Balık Popülasyonunun Tahmini, American Mathematical Monthly 45, 348–352.

[17] M. C. Wendl (2003) Rastgele Değişken Kümeleri Arasında Çarpışma Olasılığı, İstatistik ve Olasılık Mektupları 64(3), 249–254.

[abramson-18] M. Abramson ve W. O. J. Moser (1970) Daha Fazla Doğum Günü Sürprizi, American Mathematical Monthly 77, 856–858

[19] Olabilir Matt. "Doğum günü paradoksu ile çarpışma hash çarpışmaları". Matt Might'ın blogu. Alındı 17 Temmuz 2015.

[knuth73-20] Knuth, D. E. (1973). Bilgisayar Programlama Sanatı. Cilt 3, Sıralama ve Arama. Okuma, Massachusetts: Addison-Wesley. ISBN 978-0-201-03803-3.

[flajolet95-21] Flajolet, P .; Grabner, P. J .; Kirschenhofer, P .; Prodinger, H. (1995). "Ramanujan'ın Q-Fonksiyonu Üzerine". Hesaplamalı ve Uygulamalı Matematik Dergisi. 58: 103–116. doi:10.1016 / 0377-0427 (93) E0258-N.

[22] Cormen; et al. Algoritmalara Giriş.

[23] Fletcher, James (16 Haziran 2014). "Dünya Kupası'ndaki doğum günü paradoksu". bbc.com. BBC. Alındı 27 Ağustos 2015.

[24] Voracek, M .; Tran, U. S .; Formann, A. K. (2008). "Doğum günü ve doğum sorunları: Psikoloji lisans öğrencileri ve kumarhane ziyaretçileri ve personeli arasında olasılık yanılgıları". Algısal ve Motor Beceriler. 106 (1): 91–103. doi:10.2466 / pms.106.1.91-103. PMID 18459359. S2CID 22046399.

[25] Borgs, C .; Chayes, J .; Pittel, B. (2001). "Tamsayı Bölme Probleminde Faz Geçişi ve Sonlu Boyut Ölçeklendirme". Rastgele Yapılar ve Algoritmalar. 19 (3–4): 247–288. doi:10.1002 / rsa.10004. S2CID 6819493.

[1]

[2]

[3]

[nb 1]

[5]

[6]

[7]

[nb 2]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[4]