پارادوکس روز تولد (۲)

در "بخش اول مقاله" صورت مسئله "پارادوکس روز تولد" را شرح دادیم. داستان از این قرار بود: می‌خواهیم بدانیم دست کم چند نفر دور هم جمع شوند تا احتمال وجود حداقل یک جفت آدم با تاریخ تولد (ماه، روز) مشترک بر احتمال عدم وجود آن بچربد؛ یعنی احتمال وجود دست کم ۵۰ درصد باشد. در این بخش، جواب مسئله را گام به گام پیدا خواهیم کرد.

خیلی خوب. حالا بیایید مسئله را سر و ته نگاه کنیم. فرض کنید یک جمع n نفری داریم. به نظر شما احتمال اینکه هیچ دو نفری از این جمع، تاریخ تولد مشترک نداشته باشند، چقدر است؟ یک نفر از جمع انتخاب می‌کنیم. تا اینجا که به اشتراکی برنخورده‌ایم! نفر دوم را انتخاب می‌کنیم. چقدر احتمال دارد که تاریخ تولدش متمایز از اولی باشد؟ این نفر دوم باید تاریخ تولدی به غیر از تاریخ تولد اولی (که یک حالت از ۳۶۵ حالت ممکن است) داشته باشد. ۳۶۴ حالت آزاد باقی می‌ماند. پس با احتمال ۳۶۵/(۱-۳۶۵) تاریخ تولد دومی از اولی متمایز خواهد بود. حالا سراغ نفر سوم می‌رویم: چقدر احتمال دارد که تاریخ تولدش با قبلی‌ها یکی نباشد؟ ۳۶۳ حالت آزاد باقی مانده و جواب ۳۶۵/(۲-۳۶۵) است. نوبت نفر چهارم است. با چه احتمالی تاریخ تولدش با قبلی‌ها فرق دارد؟ ... بله! ۳۶۵/(۳-۳۶۵). به همین ترتیب احتمال‌های بعدی حساب می‌شوند. بنابراین با توجه به استقلال پیشامدهای مذکور و بنا بر اصل ضرب در احتمالات داریم:

در رابطه بالا، منظور از (P(n احتمال متمایز بودن تاریخ تولد آن n نفر است. ملاحظه می‌کنید که مطلوب ما دقیقا حالت مکمل متمایز بودن تاریخ تولد همه n نفر است. اگر لازم است برگردید و صورت اصلی مسئله را یک بار دیگر بخوانید. واضح است که احتمال مطلوب برابر تفاضل این احتمال از عدد یک است. اگر (Q(n احتمال بروز حداقل یک اشتراک در تاریخ تولد جمع n-نفره و در واقع همان احتمال مطلوب ما باشد، مجموع (Q(n و (P(n برابر یک می‌شود.

با عقل جور در می‌آید که هر چه تعداد نفرات (n) بیشتر شود، احتمال متمایز بودن تاریخ‌های تولد، یعنی (P(n، کمتر می‌شود. این نکته هم با شهود ما سازگار است و هم اینکه در رابطه (P(n که در بالا مشاهده می‌کنید، مستتر است: افزایش مقدار n به معنای افزایش کسرهای ضرب‌شونده در رابطه (P(n است. روشن است که صورت کسرها از مخرج‌شان کوچک‌تر و در نتجیه مقدار کسرها کوچک‌تر از یک هستند. به این ترتیب افزایش n مترادف است با کاهش مقدار (P(n و در نتیجه افزایش (Q(n.

همان‌طور که در بخش قبلی گفتیم، اگر ۳۶۶=n باشد، بنا بر "اصل لانه کبوتری" احتمال بروز اشتراک در تاریخ‌های تولد برابر یک (۱۰۰ درصد) خواهد بود. اگر کمی حوصله به خرج دهید و ۳۶۶ را به جای n در رابطه (P(n قرار دهید، معلوم می‌شود که ۰=(۳۶۶)P. پس ۱=(۳۶۶)Q خواهد شد که با نتیجه‌گیری پیشین‌مان سازگار است.

هدف را گم نکنیم؛ قرار بود حداقل تعداد نفراتی را پیدا کنیم که احتمال بروز اشتراک میان تاریخ‌های تولد آنها دست کم ۵۰ درصد باشد. به زبان ریاضی، کوچک‌ترین مقدار n را می‌خواهیم که حاصل  (Q(n به ازای آن n، بزرگ‌تر یا مساوی ۰/۵ شود. اگر یک برنامه کامپیوتری کوچک بنویسد یا اگر بلد نیستید، حوصله به خرج دهید و دست به ماشین‌حساب شوید، می‌توانید مقدار (Q(n را به ازای nهای مختلف محاسبه کرده و جواب را پیدا کنید. اگر هم کلا حوصله این بازی‌ها را ندارید، جواب همین کنار حی و حاضر است.

همان‌طور که در بالا مشاهده می‌کنید، اولین مقدار n که (Q(n بزرگ‌تر از ۰/۵ می‌شود، عدد ۲۳ است. نتیجه اینکه اگر ۲۳ نفر دور هم جمع شوند، احتمال اینکه بین تاریخ تولد آنها اشتراک پیدا شود بیش از احتمال این است که پیدا نشود. به بیان فنی‌تر، اگر تاریخ تولد افراد برآمده از یک توزیع یکنواخت در فضای گسسته ۳۶۵ نقطه‌ای از (ماه، روز) باشد، احتمال بروز اشتراک در یک مجموعه از ۲۳ نمونه تصادفی از این توزیع، بیشتر از ۵۰ درصد خواهد بود.

جواب به دست آمد: ۲۳ نفر! اما یک نقطه ابهام کماکان باقی است. چرا نام این مسئله "پارادوکس" تولد است؟ چرا پارادوکس؟ تناقض کار در کجاست؟ در بخش سوم این مقاله به این پرسش پاسخ می‌دهیم و با معرفی کاربرد این پارادوکس در علم رمزنگاری، به این سه‌گانه پایان می‌دهیم.