Membalikkan masalah ulang tahun dengan banyak tabrakan

9

Asumsikan Anda memiliki tahun alien dengan panjang yang tidak diketahui N. Jika Anda memiliki sampel acak alien tersebut dan beberapa dari mereka berbagi ulang tahun, dapatkah Anda menggunakan data ini untuk memperkirakan panjang tahun?

Misalnya, dalam sampel 100, Anda dapat memiliki dua kembar tiga (mis. Dua ulang tahun masing-masing dibagi oleh tiga alien) dan lima pasang dan delapan puluh empat lajang. Dalam memperkirakan N, minimum absolut adalah 91 dan maksimum tidak terikat, tetapi bagaimana saya akan menemukan nilai yang diharapkan masuk akal?

Asumsi termasuk hal-hal seperti "semua ulang tahun kemungkinan sama".

Tidak seperti pertanyaan lain yang dijawab di sini, ada tabrakan yang dikenal di ruangan itu. Setiap tahun yang cukup panjang akan memiliki kemungkinan kuat tidak ada tabrakan untuk ruang alien. Tetapi tahun-tahun yang sangat panjang akan memiliki peluang rendah dari setiap tabrakan, dan tahun-tahun pendek akan memiliki peluang rendah dari beberapa tabrakan, sehingga memberikan kisaran (teoretis) untuk panjang tahun yang paling mungkin.

Techhead
sumber
3
Jawaban saya untuk versi khusus dari pertanyaan ini siap digeneralisasi (menggunakan distribusi multinomial): lihat stats.stackexchange.com/questions/252813 .
whuber
@ Techhead Dengan berbagai cara! Pendekatan yang jelas untuk estimasi parameter untuk menyebutkan kemungkinan maksimum.
Glen_b -Reinstate Monica
1
@whuber Saya melihat pertanyaan itu dan komentar Anda, tapi saya tidak melihat bagaimana menerapkan sebagian besar ke sampel dengan tabrakan yang dikenal. Tidak sulit untuk menemukan formulir yang diperluas, tetapi saya tidak tahu bagaimana saya akan menemukan jumlah logaritmik.
Techhead
1
Saya setuju bahwa versi Anda cukup rumit sehingga tidak boleh ditutup sebagai duplikat.
whuber

Jawaban:

2

Nilai ekspektasi dari distribusi dihitung sebagai . Untuk masalah ini, kita ingin menghitung distribusi N diberikan beberapa kriteria tabrakan, atau menemukan E ( N ) = Σ n = 0 p n n diberikan beberapa kriteria tabrakan, di mana p n = P ( N = n ) .E(X)=pixiNE(N)=n=0pnnpn=P(N=n).

Misalkan Anda memiliki beberapa kriteria tumbukan seperti yang disebutkan di atas, dan biarkan menjadi probabilitas bahwa kriteria tumbukan terpenuhi mengingat panjang tahun adalah n . Kemudian q n dapat ditemukan dengan hanya membagi jumlah cara kriteria tabrakan dapat dipenuhi dengan jumlah cara ulang tahun dapat diatur secara umum. Setelah q n ditemukan untuk setiap kemungkinan n , maka satu-satunya bagian yang hilang adalah menerjemahkan q n ke p n .qnn.qnqnnqnpn.

Jika kita mengasumsikan bahwa sebanding dengan q n , maka p n = α q n . Karena n = 0 p n = 1 , α n = 0 q n = 1 dan α = 1pnqnpn=αqn.n=0pn=1αn=0qn=1Karena itu, kita hanya perlu formula untukqnuntuk menyelesaikan masalah ini.α=1n=0qn.qn

Sebagai contoh Anda, pertama mari kita temukan sejumlah cara kriteria tabrakan dapat terjadi mengingat Singleton alien pertama dapat mendarat kapan saja, jadi ada n kemungkinan. Singleton berikutnya dapat mendarat pada hari apa saja kecuali hari ulang tahun alien pertama, jadi ada n - 1 kemungkinan. Melengkapi ini untuk 84 lajang pertama, kita mendapatkan n ( n - 1 ) ( n - 2 ) . . . ( n - 83 )N=n.nn1n(n1)(n2)...(n83)kemungkinan cara ini bisa terjadi. Perhatikan bahwa kita juga memiliki 5 pasang dan 2 kembar tiga, sehingga alien "pertama" untuk setiap kelompok juga tidak boleh mendarat pada pasangan singleton. Ini mengarah ke cara alien ini tidak bertabrakan (sintaks kikuk adalah untuk generalisasi lebih mudah nanti).n(n1)(n2)...(n8452+1)

Berikutnya, alien kedua untuk pasangan atau triplet tertentu memiliki 91 pilihan, berikutnya memiliki 90, dll., Jumlah total cara ini dapat terjadi mengingat ulang tahun dari 91 alien pertama adalah . Anggota yang tersisa dari si kembar tiga harus jatuh pada hari ulang tahun pasangan, dan probabilitas yang terjadi adalah 7 6 . Kami melipatgandakan probabilitas untuk semua ini bersama-sama untuk mendapatkan jumlah total cara yang mungkin untuk memenuhi kriteria tabrakan sebagai:91(911)(912)...(917+1)76

rn=n(n1)...(n8452+1)(84+5+2)(84+5+21)...(84+1)(5+2)(5+1)

Pada titik ini pola yang jelas, jika kita memiliki lajang, b pasang, dan c kembar tiga, kita ganti 84 dengan sebuah , 5 dengan b , dan 2 dengan c untuk mendapatkan formula umum. Saya pikir juga jelas bahwa jumlah cara yang mungkin untuk ulang tahun yang akan diatur secara umum adalah n m , di mana m adalah jumlah total alien dalam masalah. Oleh karena itu, probabilitas memenuhi kriteria tumbukan adalah jumlah cara untuk memenuhi kriteria tumbukan dibagi dengan jumlah cara alien bisa dilahirkan, atau q n = r nabca,b,cnm .qn=rnnm

Hal menarik lainnya muncul dalam rumus . Biarkan y n = n ( n - 1 ) . . . ( n - ( a + b + c ) + 1 ) = n !rn, dan biarkanznmenjadi bagian yang tersisa darirnsehinggarn=ynzn. Perhatikan bahwazntidak tergantung pada n, jadi kita cukup menuliszn=zsebagai konstanta! Sejakpn=qn/Σi = 0 qi, danqn=yn=n(n1)...(n(a+b+c)+1)=n!(n(a+b+c))!znrnrn=ynznznzn=zpn=qn/i=0qi , kita bisa benar-benar faktorzdari jumlah penyebut. Pada titik ini, ia membatalkan dengan bagian dari pembilang untuk mendapatkanpn=ynqn=zynnmz. Kita dapat menyederhanakanynlebih jauh jika kita membiarkans=a+b+c(atau ini dapat dianggap sebagai jumlah ulang tahun unik dalam kelompok alien), sehingga kita mendapatkan:pn=ynnm/i=0(yiim)yns=a+b+c

pn=n!(ns)!nm/i=0(i!(is)!im)

Sekarang kita memiliki rumus sederhana (cukup) untuk , dan oleh karena itu rumus sederhana (cukup) untuk E ( N ) , di mana satu-satunya asumsi yang dibuat adalah bahwa P ( N = n ) sebanding dengan q n (probabilitas pertemuan kriteria tabrakan diberikan bahwa N = n ). Saya pikir ini adalah asumsi yang adil untuk dibuat, dan seseorang yang lebih pintar dari saya bahkan mungkin dapat membuktikan bahwa asumsi ini dikaitkan dengan P ( N = n ) setelah distribusi multinomial. Pada titik ini kita dapat menghitung EpnE(N)P(N=n)qnN=nP(N=n) menggunakan metode numerik atau membuat beberapa asumsi aproksimasi, karena p n akan mendekati 0 ketika n mendekati .E(N)pnn

Cody Maughan
sumber
Sepertinya Anda mengusulkan untuk menghitung nilai harapan berdasarkan fungsi kemungkinan daripada fungsi massa probabilitas. Apakah itu disengaja?
Sextus Empiricus
2

NN

Dalam jawaban ini saya ingin menuliskannya dengan lebih ringkas dan juga menyediakan cara untuk menghitung maksimum fungsi kemungkinan ini (daripada nilai yang diharapkan yang jauh lebih sulit untuk dihitung).


Fungsi kemungkinan untuk N

a+2b+3cnabc

rn=(na+b+c)number of ways topick m unique birthdaysout of n days(a+b+c)!a!b!c!number of ways todistribute m birthdaysamong groups of size ab and c(a+2b+3c)!1!a2!b3!cnumber of ordered ways toarrange specific single, duplicate, and triplicatesamong the aliens =n!(nabc)!×(a+2b+3c)a!b!c!1!a2!b3!c

n

L(n|a,b,c)=n(a+2b+3c)n!(nabc)!=nmn!(ns)!P(a,b,c|n)

ms


Estimasi kemungkinan maksimum untuk N

N

Catat itu

L(n)=L(n1)(n1n)mnns

n

(n1n)mnns=1

atau

s=n(1(11/n)m)

nx=1/nxx=0

sk=0l(mk)(n)k+O(n(l+1))

smm(m1)2n

n1(m2)ms

smm(m1)2n+m(m1)(m2)6n2

n2(m2)+(m2)24(ms)(m3)2(ms)

m=100s=91n1550n2515.1215n=516.82n=516

membandingkan perkiraan dengan MLE sejati

Sextus Empiricus
sumber