پارادوکس تولد

فیلیپ جی. اردلسکی

4 جولای 2001

لطفاً نظرات، اصلاحات و اضافات را از طریق ایمیل به مدیر وب سایت به آدرس [email protected] ارسال کنید.

یک مسئله مورد علاقه در دوره های احتمال و آمار مقدماتی، مسئله تولد است: احتمال اینکه حداقل دو نفر از N فردی که به طور تصادفی انتخاب شده اند، تولد یکسانی داشته باشند چقدر است؟ (ماه و روز یکسان، اما لزوماً سال یکسان نیست.)

بخش دوم مسئله: N چقدر باید بزرگ باشد تا احتمال آن بیشتر از 50 درصد باشد؟ پاسخ 23 است، که برای اکثر مردم به طور غیرمنطقی کوچک به نظر می رسد. به همین دلیل، این مسئله اغلب پارادوکس تولد نامیده می شود. برخی از افراد زرنگ توصیه می کنند با شرط بندی با پول برابر، شرط ببندید که در بین هر گروه 23 نفره یا بیشتر، تولدهای تکراری وجود دارد. ظاهراً، برخی از افراد ساده لوح ناآگاه وجود دارند که این شرط را می پذیرند.

این مسئله معمولاً با فرض دو چیز ساده می شود:

اولین چیزی که در مورد این مسئله باید به آن توجه کرد این است که حل مسئله مکمل بسیار آسان تر است: احتمال اینکه 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، احتمال حاصل ضرب دو احتمال است:

برنامه ای برای نمایش احتمالات به این صورت است:

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 نفر تولد یکسانی داشته باشند، زمانی که N=23 باشد، از 0.5 فراتر می رود.

اما در مورد سال کبیسه چطور؟

مسئله اصلی را می توان با یک خط کش محاسبه حل کرد، که دقیقاً همان کاری است که من برای اولین بار که آن را شنیدم، سال های بسیار دور انجام دادم.

اگر 29 فوریه را به این ترکیب اضافه کنیم، بسیار پیچیده تر می شود. در این حالت، ما فرضیات دیگری را مطرح می کنیم:

از این رو احتمال اینکه فردی که به طور تصادفی انتخاب شده در 29 فوریه متولد شده باشد 0.25/365.25 است و احتمال اینکه فردی که به طور تصادفی انتخاب شده در یک روز مشخص دیگر متولد شده باشد 1/365.25 است.

احتمال اینکه 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 متولد شده اند آنقدر کم است که فکر می کنم تقریب ما برای همه اهداف عملی معتبر است. اما اگر مایل باشید، می توانید اصلاحات مورد نیاز را انجام دهید.

پارادوکس تولد پیامدهایی فراتر از دنیای شرط بندی سالن دارد. یک تکنیک استاندارد در ذخیره سازی داده ها این است که به هر مورد یک عدد به نام کد هش اختصاص داده شود. سپس مورد در یک سطل مربوط به کد هش آن ذخیره می شود. این کار بازیابی را سرعت می بخشد زیرا فقط یک سطل باید جستجو شود. پارادوکس تولد نشان می دهد که احتمال اینکه دو یا چند مورد در یک سطل قرار بگیرند، حتی اگر تعداد موارد به طور قابل توجهی کمتر از تعداد سطل ها باشد، زیاد است. از این رو، مدیریت کارآمد سطل های حاوی دو یا چند مورد در همه موارد مورد نیاز است.