Memperluas paradoks ulang tahun menjadi lebih dari 2 orang

Dalam Paradox Ulang Tahun tradisional, pertanyaannya adalah "apa peluang dua atau lebih orang dalam sekelompok $n$ orang berbagi ulang tahun". Saya terjebak pada masalah yang merupakan perpanjangan dari ini.

Daripada mengetahui probabilitas bahwa dua orang berbagi ulang tahun, saya perlu memperluas pertanyaan untuk mengetahui berapa probabilitas $x$ atau lebih banyak orang berbagi ulang tahun. Dengan $x=2$ Anda dapat melakukan ini dengan menghitung probabilitas bahwa tidak ada dua orang yang berbagi ulang tahun dan mengurangi dari $1$ , tapi saya tidak berpikir saya dapat memperluas logika ini ke jumlah lebih besar $x$.

Untuk lebih menyulitkan ini saya juga membutuhkan solusi yang akan bekerja untuk jumlah yang sangat besar untuk $n$ (jutaan) dan $x$ (ribuan).

Ini adalah masalah penghitungan: ada mungkin penugasan b ulang tahun ke n orang. Dari jumlah tersebut, misalkan q ( k ; n , b ) adalah jumlah penugasan di mana tidak ada ulang tahun yang dibagi lebih dari k orang, tetapi setidaknya satu ulang tahun sebenarnya dibagi oleh k orang. Probabilitas yang kita cari dapat ditemukan dengan menjumlahkan q ( k ; n $b^n$$b$$n$$q(k; n, b)$$k$$k$ untuk nilai k yang sesuaidan mengalikan hasilnya dengan b - n .$q(k;n,b)$$k$$b^{-n}$

Hitungan ini dapat ditemukan dengan tepat untuk nilai kurang dari beberapa ratus. Namun, mereka tidak akan mengikuti formula langsung: kita harus mempertimbangkan pola cara di mana ulang tahun dapat ditetapkan . Saya akan mengilustrasikan ini sebagai pengganti memberikan demonstrasi umum. Misalkan n = 4 (ini adalah situasi menarik terkecil). Kemungkinannya adalah:$n$$n = 4$

• Setiap orang memiliki hari ulang tahun yang unik; kodenya adalah {4}.
• Tepatnya dua orang berbagi ulang tahun; kodenya adalah {2,1}.
• Dua orang memiliki satu hari ulang tahun dan dua lainnya memiliki yang lainnya; kodenya adalah {0,2}.
• Tiga orang berbagi ulang tahun; kodenya adalah {1,0,1}.
• Empat orang berbagi ulang tahun; kodenya adalah {0,0,0,1}.

Secara umum, kode adalah tupel hitungan yang $\{a[1], a[2], \ldots\}$elemen nya menentukan berapa banyak tanggal lahir berbeda yang dibagikan olehorang-orang k . Jadi, khususnya,$k^\text{th}$$k$

Perhatikan, bahkan dalam kasus sederhana ini, bahwa ada dua cara untuk mencapai maksimum dua orang per ulang tahun: satu dengan kode dan satu lagi dengan kode$\{0,2\}$ .$\{2,1\}$

Kami dapat langsung menghitung jumlah kemungkinan tugas ulang tahun yang sesuai dengan kode yang diberikan. Nomor ini adalah produk dari tiga istilah. Salah satunya adalah koefisien multinomial; ia menghitung jumlah cara partisi orang ke sebuah [ 1 ] kelompok 1 , sebuah [ 2 ] kelompok 2 , dan seterusnya. Karena urutan kelompok tidak masalah, kita harus membagi koefisien multinomial ini dengan sebuah [ 1 ] ! a [ 2 ] ! $n$$a[1]$$1$$a[2]$$2$$a[1]!a[2]!\cdots$; kebalikannya adalah masa jabatan kedua. Terakhir, susun grup dan berikan mereka masing-masing ulang tahun: ada kandidat untuk grup pertama, ⋯ ( b - m + $b$ untuk yang kedua, dan seterusnya. Nilai-nilai ini harus dikalikan bersama, membentuk istilah ketiga. Ini sama dengan "produk faktorial" b ( a [ 1 ] + a [ 2 ] + ⋯ ) di mana b ( m ) berarti b ( b - 1 $b-1$$b^{(a[1]+a[2]+\cdots)}$$b^{(m)}$ .$b(b-1)\cdots(b-m+1)$

Ada rekursi yang jelas dan cukup sederhana yang menghubungkan hitungan untuk suatu pola dengan hitungan untuk pola { a [ 1 ] , ... , a [ k - 1 ] } . Ini memungkinkan penghitungan cepat penghitungan untuk nilai n sederhana . Secara khusus, sebuah [ k ] merupakan suatu [ orang masing-masing. Setelah ini sebuah [ k $\{a[1], \ldots, a[k]\}$$\{a[1], \ldots, a[k-1]\}$$n$$a[k]$ tanggal lahir bersama oleh persis$a[k]$$k$$a[k]$kelompok orang telah diambil dari n orang, yang dapat dilakukan dalam x cara yang berbeda (katakanlah), masih menghitung jumlah cara untuk mencapai pola { a [ 1 ] , ... , a [ k - 1 $k$$n$$x$ antara orang-orang yang tersisa. Mengalikan ini dengan x memberikan rekursi.$\{a[1], \ldots, a[k-1]\}$$x$

Saya ragu ada rumus bentuk tertutup untuk , yang diperoleh dengan menjumlahkan jumlah untuk semua partisi$q(k; n, b)$ yang istilah maksimumnya sama dengan k . Izinkan saya menawarkan beberapa contoh:$n$$k$

Dengan (lima kemungkinan ulang tahun) dan n $b=5$ (empat orang), kami memperoleh$n=4$

Di mana, misalnya, kesempatan bahwa tiga orang atau lebih dari empat orang berbagi "ulang tahun" yang sama (dari tanggal yang mungkin) sama dengan ( 80 + 5 ) $5$ .$(80 + 5)/625 = 0.136$

Sebagai contoh lain, ambil dan n = 23 . Berikut adalah nilai-nilai q ( k ; 23 , 365 ) untuk k yang terkecil$b = 365$$n = 23$$q( k;23,365)$$k$ (hanya untuk enam sig ara):

Dengan menggunakan teknik ini, kita dapat dengan mudah menghitung bahwa ada sekitar 50% kemungkinan (setidaknya) tabrakan ulang tahun tiga arah di antara 87 orang, 50% kemungkinan tabrakan empat arah di antara 187, dan kemungkinan 50% dari tabrakan lima arah di antara 310 orang. Perhitungan terakhir itu mulai memakan waktu beberapa detik (dalam Mathematica, bagaimanapun) karena jumlah partisi yang dipertimbangkan mulai bertambah besar. Untuk secara substansial lebih besar kita membutuhkan perkiraan.$n$

Satu pendekatan diperoleh dengan cara distribusi Poisson dengan harapan , karena kita dapat melihat penugasan ulang tahun yang timbul dari b hampir (tetapi tidak cukup) variabel Poisson independen masing-masing dengan harapan n / b : variabel untuk setiap kemungkinan ulang tahun yang diberikan menjelaskan berapa banyak dari n orang memiliki ulang tahun itu. Distribusi maksimum karena itu kira-kira F ( k ) b di mana F adalah CDF Poisson. Ini bukan argumen yang keras, jadi mari kita lakukan sedikit pengujian. Perkiraan untuk n = 23 , $n/b$$b$$n/b$$n$$F(k)^b$$F$$n = 23$ memberi$b = 365$

Dengan membandingkan dengan yang sebelumnya Anda dapat melihat bahwa probabilitas relatif bisa menjadi buruk ketika mereka kecil, tetapi probabilitas absolut diperkirakan cukup baik sekitar 0,5%. Pengujian dengan berbagai dan b menunjukkan perkiraan biasanya tentang kebaikan ini.$n$$b$

Untuk menyelesaikannya, mari kita pertimbangkan pertanyaan awal: ambil (jumlah pengamatan) dan b = $n = 10,000$ (jumlah kemungkinan "struktur," sekitar). Perkiraan distribusi untuk jumlah maksimum "ulang tahun bersama" adalah$b = 1\,000\,000$

(Ini adalah perhitungan cepat.) Jelas, mengamati satu struktur 10 kali dari 10.000 akan sangat signifikan. Karena dan b keduanya besar, saya berharap perkiraannya bekerja dengan cukup baik di sini.$n$$b$

Kebetulan, seperti yang Shane katakan, simulasi dapat memberikan pemeriksaan yang bermanfaat. Simulasi Mathematica dibuat dengan fungsi seperti

simulate[n_, b_] := Max[Last[Transpose[Tally[RandomInteger[{0, b - 1}, n]]]]];

yang kemudian diulang dan diringkas, seperti dalam contoh ini yang menjalankan 10.000 iterasi dari , b = $n = 10000$ kasus:$b = 1\,000\,000$

Tally[Table[simulate[10000, 1000000], {n, 1, 10000}]] // TableForm

Outputnya adalah

2 8503

3 1493

4 4

Frekuensi-frekuensi ini sangat sesuai dengan yang diprediksi oleh perkiraan Poisson.

Selalu mungkin untuk menyelesaikan masalah ini dengan solusi monte-carlo, meskipun itu jauh dari yang paling efisien. Berikut adalah contoh sederhana masalah 2 orang dalam R (dari presentasi yang saya berikan tahun lalu ; Saya menggunakan ini sebagai contoh kode yang tidak efisien), yang dapat dengan mudah disesuaikan dengan akun lebih dari 2:

birthday.paradox <- function(n.people, n.trials) {
    matches <- 0
    for (trial in 1:n.trials) {
        birthdays <- cbind(as.matrix(1:365), rep(0, 365))
        for (person in 1:n.people) {
            day <- sample(1:365, 1, replace = TRUE)
            if (birthdays[birthdays[, 1] == day, 2] == 1) {
                matches <- matches + 1
                break
            }
            birthdays[birthdays[, 1] == day, 2] <- 1
        }
        birthdays <- NULL
    }
    print(paste("Probability of birthday matches = ", matches/n.trials))
}

This is an attempt at a general solution. There may be some mistakes so use with caution!

First some notation:

$P(x,n)$ be the probability that $x$ or more people share a birthday among $n$ people,

$P(y|n)$ be the probability that exactly $y$ people share a birthday among $n$ people.

Notes:

1. Abuse of notation as $P(.)$ is being used in two different ways.

2. By definition $y$ cannot take the value of 1 as it does not make any sense and $y$ = 0 can be interpreted to mean that no one shares a common birthday.

Then the required probability is given by:

$P(x,n) = 1 - P(0|n) - P(2|n) - P(3|n) .... - P(x-1|n)$

Now,

$P(y|n) = {n \choose y} (\frac{365}{365})^y \ \prod_{k=1}^{k=n-y}(1 -\frac{k}{365})$

Here is the logic: You need the probability that exactly $y$ people share a birthday.

Step 1: You can pick $y$ people in ${n \choose y}$ ways.

Step 2: Since they share a birthday it can be any of the 365 days in a year. So, we basically have 365 choices which gives us $(\frac{365}{365})^y$.

Step 3: The remaining $n-y$ people should not share a birthday with the first $y$ people or with each other. This reasoning gives us $\prod_{k=1}^{k=n-y}(1 -\frac{k}{365})$.

You can check that for $x$ = 2 the above collapses to the standard birthday paradox solution.