Hari Ulang Tahun Paradoks

Philip J. Erdelsky

4 Juli 2001

Silakan e-mail komentar, koreksi dan penambahan pada webmaster di pje@efgh.com

 

Masalah favorit di SD probabilitas dan statistik program adalah Ulang Tahun Soal: Berapa probabilitas bahwa setidaknya dua dari N orang yang dipilih secara acak memiliki ulang tahun yang sama? (Bulan yang sama dan hari, tetapi belum tentu tahun yang sama.)

Bagian kedua dari masalah: Berapa besar N harus sehingga probabilitas lebih besar dari 50 persen? Jawabannya adalah 23, yang menyerang kebanyakan orang sebagai tidak masuk akal kecil. Untuk alasan ini, masalah ini sering disebut Ulang Tahun Paradox. Beberapa sharpies merekomendasikan taruhan, di bahkan uang, yang ada duplikat ulang tahun di antara setiap kelompok 23 orang atau lebih. Agaknya, ada beberapa pengisap kurang informasi yang akan menerima taruhan.

Masalahnya biasanya disederhanakan dengan asumsi dua hal:

  1. Tidak ada yang lahir pada tanggal 29 Februari.
  2. ulang tahun orang yang merata selama 365 hari lainnya tahun.

Salah satu hal pertama yang pemberitahuan tentang masalah ini adalah bahwa hal itu jauh lebih mudah untuk memecahkan masalah yang saling melengkapi: Berapa probabilitas bahwa N orang yang dipilih secara acak memiliki semua ulang tahun yang berbeda? Kita bisa menulis ini sebagai fungsi rekursif:

double different_birthdays(int n)
{
  return n == 1 ? 1.0 : different_birthdays(n-1) * (365.0-(n-1))/365.0;
}

Jelas, untuk N = 1 probabilitasnya adalah 1. Untuk N> 1, probabilitas adalah produk dari dua probabilitas:

  1. Yang pertama N-1 orang memiliki ulang tahun semua berbeda.
  2. Bahwa orang N-th memiliki ulang tahun yang berbeda dari salah satu yang pertama N-1.

Sebuah program untuk menampilkan probabilitas berlangsung seperti ini:

void main(void)
{
  int n;
  for (n = 1; n <= 365; n++)
    printf("%3d: %e\n", n, 1.0-different_birthdays(n));
}

Hasilnya adalah sesuatu seperti ini:

1: 0.000000e+00
  2: 2.739726e-03
  3: 8.204166e-03
  4: 1.635591e-02
  5: 2.713557e-02
      ***
 20: 4.114384e-01
 21: 4.436883e-01
 22: 4.756953e-01
 23: 5.072972e-01
 24: 5.383443e-01
 25: 5.686997e-01
      ***

probabilitas bahwa setidaknya dua orang N memiliki kenaikan ulang tahun yang sama di atas 0,5 ketika N = 23.

TAPI APA TENTANG LEAP YEAR?

Masalah asli dapat diselesaikan dengan slide rule, yang adalah apa yang saya lakukan ketika saya pertama kali mendengar itu bertahun-tahun yang lalu.

Jika kita menambahkan 29 Februari ke dalam campuran, itu akan jauh lebih rumit. Dalam hal ini, kami membuat beberapa asumsi tambahan:

  1. jumlah yang sama dari orang yang lahir pada hari selain 29 Februari.
  2. Jumlah orang yang lahir pada 29 Februari adalah seperempat dari jumlah orang yang lahir pada hari lain.

Maka probabilitas bahwa orang yang dipilih secara acak lahir pada tanggal 29 Februari adalah 0,25 / 365,25, dan probabilitas bahwa orang yang dipilih secara acak lahir pada hari yang ditentukan lain adalah 1 / 365,25.

Probabilitas bahwa N orang, mungkin termasuk satu lahir pada 29 Februari, memiliki ulang tahun yang berbeda adalah jumlah dari dua probabilitas:

  1. Bahwa N orang yang lahir pada N hari yang berbeda selain 29 Februari.
  2. Bahwa N orang yang lahir pada N hari yang berbeda, dan termasuk satu orang yang lahir pada tanggal 29 Februari.

Probabilitas menambahkan karena dua kasus saling eksklusif.

Sekarang setiap probabilitas dapat dinyatakan secara rekursif:

double different_birthdays_excluding_Feb_29(int n)
{
  return n == 1 ? 365.0/365.25  :
    different_birthdays_excluding_Feb_29(n-1) * (365.0-(n-1)) / 365.25;
}

double different_birthdays_including_Feb_29(int n)
{
  return n == 1 ? 0.25 / 365.25 :
    different_birthdays_including_Feb_29(n-1) * (365.0-(n-2)) / 365.25 +
    different_birthdays_excluding_Feb_29(n-1) * 0.25 / 365.25;
}

Sebuah program untuk menampilkan probabilitas berlangsung seperti ini:

void main(void)
{
  int n;
  for (n = 1; n <= 366; n++)
    printf("%3d: %e\n", n, 1.0-different_birthdays_excluding_Feb_29(n) -
      different_birthdays_including_Feb_29(n));
}

Hasilnya adalah sesuatu seperti ini:

1: -8.348357e-18
  2: 2.736445e-03
  3: 8.194354e-03
  4: 1.633640e-02
  5: 2.710333e-02
      ***
 20: 4.110536e-01
 21: 4.432853e-01
 22: 4.752764e-01
 23: 5.068650e-01
 24: 5.379013e-01
 25: 5.682487e-01
      ***

Seperti yang diharapkan, probabilitas yang sedikit lebih rendah, karena ada kemungkinan lebih rendah dari ulang tahun yang cocok ketika ada lebih mungkin ulang tahun. Namun jumlah terkecil dengan probabilitas yang lebih besar dari 0,5 masih 23.

Tentu saja, murni matematika mungkin berpendapat bahwa tahun kabisat tidak selalu datang setiap empat tahun, sehingga perhitungan perlu modifikasi lebih lanjut. Namun, tahun empat tahunan lalu itu bukan tahun kabisat adalah tahun 1900, dan yang berikutnya akan 2100. Jumlah orang yang kini hidup yang lahir pada tahun 1900 sangat kecil sehingga saya pikir pendekatan kami berlaku untuk semua tujuan praktis. Tapi Anda dipersilakan untuk membuat modifikasi yang diperlukan jika Anda inginkan.

Hari Ulang Tahun Paradoks memiliki implikasi luar dunia salon taruhan. Sebuah teknik standar dalam penyimpanan data adalah untuk menetapkan setiap item nomor disebut kode hash. Item ini kemudian disimpan dalam bin sesuai dengan kode hash-nya. Ini mempercepat pengambilan karena hanya bin tunggal harus dicari. Hari Ulang Tahun Paradoks menunjukkan bahwa probabilitas bahwa dua atau lebih item akan berakhir di tempat sampah yang sama tinggi bahkan jika jumlah item jauh lebih kecil dari jumlah sampah. Oleh karena itu penanganan yang efisien dari sampah yang mengandung dua atau lebih item diperlukan dalam semua kasus.