Masalah ulang tahun terbalik: tidak ada pasangan dari 1 juta alien berbagi ulang tahun; berapa panjang tahun mereka?

Asumsikan sebuah planet dengan tahun sangat panjang . Ada 1 juta orang asing di sebuah pesta di sebuah ruangan, dan tidak ada seorang pun yang berbagi ulang tahun. Apa yang bisa disimpulkan tentang ukuran ? $N$ $N$

(Pertanyaan yang lebih ringkas ini menggantikan yang diucapkan dengan buruk ini. )

probability birthday-paradox Paul Uszak
sumber

Masalah ulang tahun memberi tahu Anda nilai N di mana probabilitas setidaknya satu kecocokan lebih besar dari nilai yang ditentukan. Ketika p = 1/2 itu mengejutkan untuk intuisi bahwa ini memberi n = 23 .. Ini mengasumsikan bahwa setiap ulang tahun memiliki probabilitas seragam yang sama (1/365). Nonuniformity hanya membuat n lebih kecil. Sekarang dalam masalah Anda tampaknya N mengganti 365 dan saya menganggap asumsi keseragaman dipertahankan.

Michael R. Chernick

Jika N <= 1.000.000 maka setidaknya 1 kecocokan memiliki probabilitas = 1 dan 0 kecocokan memiliki probabilitas = 0.

Michael R. Chernick

Jadi ketika N> 1.000.000 probabilitas setidaknya 1 kecocokan memiliki probabilitas <1 dan karenanya probabilitas kecocokan nol mulai meningkat.

Michael R. Chernick

@Michael Harap pesan komentar untuk permintaan klarifikasi dan diskusi insidental lainnya, dan cobalah memposting satu per satu: ada alasan bagus untuk batasan karakter. Jika Anda menemukan diri Anda mendiskusikan sesuatu yang substansial yang membutuhkan banyak komentar, Anda mungkin mencoba menjawab pertanyaan itu, jadi sebaiknya Anda mengirim jawaban.

whuber

Dengan asumsi semua ulang tahun sama-sama mungkin dan ulang tahun itu independen, kemungkinan alien tidak berbagi hari ulang tahun adalah $k+1$

p (k; N) = 1 (1 - \frac{1}{N}) (1 - \frac{2}{N}) \dots (1 - \frac{k}{N}) .

$p(k;N) = 1\left(1-\frac{1}{N}\right)\left(1-\frac{2}{N}\right)\cdots\left(1-\frac{k}{N}\right).$

Logaritma dapat disimpulkan asimtotik asalkan jauh lebih kecil dari : $k$ $N$

\begin{matrix} (1) & \log (p (k; N)) = - \frac{k (k + 1)}{2 N} - \frac{k + 3 k^{2} + 2 k^{3}}{12 N^{2}} - O (k^{4} N^{- 3}) . \end{matrix}

$\log(p(k;N)) = -\frac{k(k+1)}{2N} - \frac{k + 3k^2 + 2k^3}{12N^2} - O(k^4 N^{-3}).\tag{1}$

Untuk menjadi yakin bahwa adalah tidak kurang dari beberapa nilai , kita perlu lebih besar dari . Small memastikan jauh lebih besar dari , di mana kita dapat memperkirakan secara akurat sebagai . Ini menghasilkan $100-100\alpha\%$ $N$ $N^{*}$ $(1)$ $\log(1-\alpha)$ $\alpha$ $N$ $k$ $(1)$ $-k^2/(2N)$

- \frac{k^{2}}{2 N} > \log (1 - α),

$-\frac{k^2}{2N} \gt \log(1-\alpha),$

menyiratkan

\begin{matrix} (2) & N > \frac{- k^{2}}{2 \log (1 - α)} \approx \frac{k^{2}}{2 α} = N^{*} \end{matrix}

$N \gt\frac{-k^2}{2\log(1-\alpha)} \approx \frac{k^2}{2\alpha}=N^{*}\tag{2}$

untuk kecil . $\alpha$

Misalnya, dengan seperti dalam pertanyaan dan (nilai konvensional yang sesuai dengan kepercayaan), memberikan . $k=10^6-1$ $\alpha=0.05$ $95\%$ $(2)$ $N \gt 10^{13}$

Berikut adalah interpretasi yang lebih luas tentang hasil ini. Tanpa mendekati dalam rumus , kita memperoleh . Untuk ini kemungkinan tidak ada tabrakan dalam sejuta ulang tahun adalah (dihitung tanpa perkiraan), pada dasarnya sama dengan ambang batas kami . Jadi untuk setiap besar atau lebih besar ini atau lebih mungkin tidak akan ada tabrakan, yang konsisten dengan apa yang kita ketahui, tetapi untuk setiap lebih kecil kemungkinan tabrakan mencapai di atas , yang mulai membuat kita takut kita mungkin telah meremehkan . $(2)$ $N=9.74786\times 10^{12}$ $N$ $p(10^6-1, 9.74786\times 10^{12})=95.0000\ldots\%$ $95\%$ $N$ $95\%$ $N$ $100 - 95= 5\%$ $N$

Sebagai contoh lain, dalam masalah Ulang Tahun tradisional ada peluang dari tidak ada tabrakan di orang dan peluang dari tidak ada tabrakan di orang. Angka-angka ini menyarankan harus masing-masing melebihi dan , tepat di kisaran nilai yang benar . Ini menunjukkan seberapa akurat perkiraan ini, hasil asimptotik dapat bahkan untuk sangat kecil (asalkan kita tetap pada kecil ). $4\%$ $k=6$ $5.6\%$ $k=7$ $N$ $360$ $490$ $366$ $k$ $\alpha$

whuber
sumber

Saya tidak siap untuk memberikan jawaban seperti ini. Dengan angka, perkiraan besar ini mungkin lebih mudah untuk dihitung. Wikipedia memberikan masalah ulang tahun umum yang menunjukkan perkiraan dan batasan pada N dengan k orang (alien). Saya memiliki rumus yang sama dengan persamaan pertama Anda.

Michael R. Chernick

Pertanyaan saya adalah seberapa besar N harus mencapai tingkat kepercayaan 100%. Saya pikir ini kira-kira 10 ^ 18.

Michael R. Chernick

@MichaelChernick Untuk kepercayaan 100%, N menjadi tak terhingga. Untuk setiap tahun yang terbatas dan untuk pihak mana pun dengan 2 atau lebih alien, probabilitas dua alien dengan ulang tahun yang sama selalu lebih besar dari 0.

Pere

@Pere Ya, terima kasih sudah melihatnya. Saya akan segera memperbaikinya. Tidak ada bedanya dengan sisa posting.

Whuber

@ Paul Uszak Saya pikir komentar Anda tentang jawaban Pere (sekarang dihapus) terlalu keras. Saya pikir jawabannya diberikan dengan itikad baik. Dia berusaha membantu Anda dengan memberikan perkiraan yang berguna. Dia kemudian melihat jawaban whuber dan memutuskan bahwa itu lebih lengkap dan setuju untuk menghapus jawabannya. Komentarnya tentang tidak mengharapkan jawaban terperinci tidak berarti cara Anda menafsirkannya. Ini masalah yang sulit. Anda bahkan harus menulis ulang posting agar dapat dimengerti. Saya yakin dia tidak menganggap pemecahan masalah seperti ini sebagai lelucon.

Michael R. Chernick

Masalah ulang tahun terbalik: tidak ada pasangan dari 1 juta alien berbagi ulang tahun; berapa panjang tahun mereka?

Jawaban: