http://www.efgh.com/math/sitelogo.gif"

Парадокс "День народження"

Філіп Дж. Ердельскі

4 липня 2001 р

Улюблена проблема з елементарними ймовірностями та курсами статистики - проблема "День народження". Яка ймовірність того, що принаймні двома випадковим чином обраних людей мають один і той же день народження? (Той же місяць і день, але не обов'язково в тому ж році.)

Друга частина проблеми: наскільки великою має бути N, щоб ймовірність перевищувала 50 відсотків? Відповідь - 23, що вражає більшість людей як необґрунтовано малі. З цієї причини проблема часто називається Paradox Birthday. Деякі гострі предмети рекомендують робити ставки, навіть за гроші, що існує дубльовані дні народження серед будь-якої групи з 23 або більше людей. Мабуть, є погано поінформовані присоски, які приймуть ставку.

Проблема, як правило, спрощується шляхом прийняття двох речей:

1.     Ніхто не народився 29 лютого.

2.     Людські дні народження рівномірно розподілені протягом інших 365 днів року.

Одне з перших речей, про які слід звернути увагу на цю проблему, полягає в тому, що набагато легше вирішити додаткову проблему: якою є вірогідність того, що у випадково вибраних людей N різні дні народження? Ми можемо написати це як рекурсивну функцію:

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

Очевидно, для N = 1 ймовірність 1. Для N> 1 ймовірність є продуктом двох вірогідності:

1.     Що перші люди N-1 мають різні дні народження.

2.     Те, що N-й особі день народження відрізняється від будь-якого з перших N-1.

Програма для відображення ймовірностей виходить приблизно так:

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

Результат щось подібне:

  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
      ***

Імовірність того, що щонайменше два з N людей мають один і той же день народження, піднімається вище 0,5, коли N = 23.

АЛЕ, ЩО ПРО ЛЕГАЛЬНИЙ РІК?

Оригінальну проблему можна вирішити за допомогою правила слайдів, що саме я зробив, коли я почув це багато, багато років тому.

Якщо ми додамо 29 лютого до складу суміші, це стане значно складнішим. У цьому випадку ми робимо деякі додаткові припущення:

1.     Рівні числа людей народжуються в інші дні, ніж 29 лютого.

2.     Кількість людей, народжених 29 лютого, становить одну четверту частину числа народжених на будь-який інший день.

Отже, ймовірність того, що випадково вибрана особа народилася 29 лютого, становить 0,25 / 365,25, а ймовірність того, що випадково вибрана особа народилася в інший вказаний день, становить 1/365,25.

Ймовірність того, що N особи, можливо, включаючи одного, що народився 29 лютого, мають різні дні народження - це сума двох ймовірностей:

1.     Що N народи народились в N різних днів, крім 29 лютого.

2.     Те, що N народи народилися в N різних днів і включають одну особу, що народилася 29 лютого.

Імовірності додаються тому, що два випадки є взаємовиключними.

Тепер кожну ймовірність можна виразити рекурсивно:

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;
}

Програма для відображення ймовірностей виходить приблизно так:

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));
}

Результат щось подібне:

  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
      ***

Як і очікувалося, ймовірності дещо нижчі, оскільки існує менша ймовірність підбору денних днів народження, коли існує більше можливих днів народження. Але найменше число з ймовірністю більше 0,5 досі залишається 23.

Звичайно, математичний пурист може стверджувати, що високосні роки не завжди відбуваються кожні чотири роки, тому розрахунки потребують подальшої модифікації. Проте останній чотирирічний рік, який не був високосним, становив 1900, а наступний - 2100. Кількість людей, які зараз живуть, які народилися в 1900 році, настільки мала, що я вважаю, що наше наближення дійсно для всіх практичних цілей. Але ви можете внести необхідні зміни, якщо хочете.

Парадокс "День народження" має наслідки, що виходять за рамки пари. Стандартна методика зберігання даних полягає в тому, щоб присвоїти кожному елементу номер, який називається хеш-кодом. Потім елемент зберігається у скриньці, що відповідає його хеш-коду. Це прискорює пошук, оскільки потрібно шукати лише один контейнер. Парадокс "День народження" показує, що ймовірність того, що два або більше елементів в кінцевому підсумку будуть однаковими, є високою, навіть якщо кількість предметів значно нижча, ніж кількість бункерів. Тому в усіх випадках необхідна ефективна обробка смітників, що містять два або більше предметів.