Филип Дж. Ерделски
4 юли 2001 г.
Моля, изпратете коментари, корекции и допълнения към уеб администратора на адрес [email protected].
Един от любимите проблеми в курсовете за елементарни вероятности и статистика е проблема за рождения ден: Каква е вероятността поне двама от случайно избраните хора да имат същия рожден ден? (Същият месец и ден, но не непременно същата година.)
Втората част на проблема: Колко голяма трябва да бъде N, така че вероятността да е по-голяма от 50%? Отговорът е 23, който удря повечето хора като необосновано малка. Поради тази причина проблемът често се нарича Парадокс на рождените дни. Някои остри умове препоръчват да залагате на равностойни пари, че има дублирани рождени дни сред всяка група от 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, вероятността е продукт на две вероятности:
Това, че първите хора от 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 г., е толкова малък, че мисля, че нашето сближаване е валидно за всички практически цели. Но вие сте добре дошли да направите необходимите модификации, ако желаете.
Парадоксът на рождените дни има последици отвъд света на залаганията. Стандартна техника за съхранение на данни е да присвоите на всеки елемент номер, наречен хеш-код. След това елементът се съхранява в контейнер, съответстващ на неговия хеш-код. Това ускорява извличането, защото трябва да се търси само един контейнер. Парадоксът на рождените дни показва, че вероятността две или повече елементи да завършат в същия контейнер е висока дори ако броят на елементите е значително по-малък от броя на контейнерите. Следователно във всички случаи е необходимо ефективно боравене с контейнери, съдържащи два или повече елемента.
Translation from English by Cvetomira Mikovska
