موضوع مقاله: مسئله تاریخ تولد | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله تاریخ تولد | مقدمه: در تئوری احتمالات، مسئله تاریخ تولد یا پارادوکس تاریخ تولد به یافتن احتمال حضور بیش از دو نفر در مجموعهٔ تصادفی n نفره که تاریخ تولد یکسانی داشته باشند، مربوط است. | ## بخش 1: مسئله تاریخ تولد | طبق اصل لانه کبوتری این احتمال وقتی که تعداد افراد حاضر برابر با ۳۶۶ (با فرض این که سال ۳۶۵ روز است، بدون در نظر سال کبیسه) شود، مساوی ۱۰۰٪ می‌شود. این نتایج با این فرض به دست می‌آید که سال دارای ۳۶۵ روز (یعنی با در نظر نگرفتن ۳۰ اسفند) و احتمال تولد افراد در آن‌ها برابر هم باشد. محاسبات ریاضی پشت این مسئله باعث ایجاد یک حمله رمزنگاری معروف به اسم حمله روز تولد شده‌است. این حمله بر اساس مدل احتمالی مسئله تاریخ تولد، پیچیدگی توابع درهم‌سازی را کاهش می‌دهد و باعث ساده شدن شکستن آن می‌شود. فهم مسئله مسئله روز تولد این سؤال را مطرح می‌کند که آیا درون یک گروه معین هیچ فردی وجود دارد که با یکی دیگر از افراد گروه تاریخ تولد مشابهی داشته باشد - نه شخص خاصی به‌طور مشخص. (به قسمت «#هم تاریخ تولد با شما» در زیر نگاه کنید برای تحلیل این مسئله جایگزینی که کمتر جالب به نظر می‌رسد) در مثالی که پیش از این مطرح شد، در لیستی شامل ۲۳ نفر، در مقایسه شانس اینکه تاریخ تولد نفر اول لیست با دیگران یکسان باشد ۲۲ است، برای نفر دوم لیست برابر با ۲۱، برای نفر سوم لیست برابر با ۲۰ و همین‌طور تا آخر. +۱ = ۲۵۳، بنابراین مقایسه هر فرد با تمام افراد دیگر ۲۵۳ شانس مجزا را به وجود می‌آورد (ترکیب): در یک گروه ۲۳ نفری (۲۳¦۲)= ۲۳٫۲۲/۲=۲۵۳جفت وجود دارد. با فرض اینکه احتمال تمام روزهای تولد یکسان باشد، احتمال یک تاریخ تولد داده شده برای فردی که به‌طور تصادفی از بین جمع انتخاب شده ۱/۳۶۵ (با نادیده گرفتن روز کبیسه، ۳۰ اسفند) است. اگرچه زوج‌های یک گروه ۲۳ نفری از لحاظ آماری با ۲۵۳ زوجی که به‌طور مستقل انتخاب شده‌اند هم‌ارز نیستند، اگر یک گروه بر حسب تعداد زوج‌های آن سنجیده شود، پارادوکس تولد نسبت به زمانی که بر حسب افراد سنجیده شود، کم‌تر تعجب‌برانگیز خواهد بود. محاسبه احتمالات مسئله مورد نظر، محاسبه احتمال تقریبی حضور حداقل دو نفر در اتاقی با حضور n نفر، با تاریخ تولد یکسان است. برای سادگی، تفاوت‌ها در توزیع، مانند سال کبیسه، دوقلوها، تغییرات روزهای هفته و تغییرات فصلی را نادیده بگیرید و فرض کنید ۳۶۵ تاریخ تولدی که امکان پزیرند، احتمال برابری داشته باشند. توزیع تاریخ تولدها در واقعیت یکنواخت نیست، زیرا تمام تاریخ‌ها احتمال برابری ندارند. | ## بخش 2: مسئله تاریخ تولد | اگر P(A) احتمال حضور حداقل ۲ نفر در یک اتاق با تاریخ تولدهای یکسان باشد، محاسبه P(A’)، یعنی احتمال نبود هیچ دو نفری که تولد یکسان داشته باشند می‌تواند آسان تر باشد؛ بنابراین، به این دلیل که P(A) و P(A') تنها احتمالات ممکن و دو به دو ناسازگار هستند، P(A') = ۱ − P(A . برای احترام به راه حل‌های منتشر شدهٔ زیادی که نتیجه گرفته‌اند برای داشتن P(A) بیشتر از ۵۰٪ حضور ۲۳ نفر ضروری است، در زیر، برای محاسبه P(A)، ۲۳ نفر به عنوان مثال در نظر گرفته می‌شود. وقتی رویدادها مستقل از یکدیگر باشند، احتمال کل رویدادهایی که اتفاق می‌افتند برابر است با ضرب احتمالات هر کدام از رویدادها؛ بنابراین اگر P(A') به عنوان ۲۳ رویداد مستقل تعریف شود، می‌توان به این صورت آن را محاسبه کرد: P(1) × P(2) × P(3) × … × P(23) این ۲۳ رویداد مستقل، متناظر با این ۲۳ نفر هستند و می‌توانند به ترتیب تعریف شوند. هر رویداد می‌تواند با فرد متناظر با آن که با هیچ‌یک از افراد تحلیل شده قبلی، تاریخ تولد یکسانی ندارد مشخص شود. برای رویداد ۱، هیچ فرد تحلیل شدهٔ قبلی وجود ندارد؛ بنابراین احتمال P(1) یعنی اینکه تاریخ تولد فرد شماره ۱ با هیچ‌یک از افراد تحلیل شدهٔ قبلی یکسان نباشد، ۱ یا ۱۰۰٪ است. بدون در نظر گرفتن سال‌های کبیسه برای این تحلیل، به دلایلی که در زیر به روشنی خواهد آمد، احتمال برابر با یک می‌تواند به صورت ۳۶۵/۳۶۵ نوشته شود. با فرض اینکه تاریخ تولدها احتمال برابری برای اتفاق افتادن در هریک از ۳۶۵ روز سال را داشته باشند، احتمال P(2)، اینکه فرد شماره ۲ تاریخ تولد متفاوتی با فرد شماره ۱ داشته باشد، ۳۶۴/۳۶۵ است. این به این دلیل است که اگر فرد شماره ۲ در هر کدام از ۳۶۴ روز دیگر سال متولد شده باشد، فرد شماره ۱ و ۲ تاریخ تولد یکسانی نخواهند داشت. به‌طور مشابه اگر فرد شماره ۳ در هریک از ۳۶۳ روز دیگر سال غیر از تاریخ تولد فرد شماره ۱ و ۲ متولد شده باشد، فرد شماره ۳ تاریخ تولد یکسانی با آن‌ها نخواهد داشت. این تحلیل تا رسیدن به فرد شماره ۲۳ ادامه پیدا می‌کند، فردی که احتمال آنکه تاریخ تولد یکسانی با افراد تحلیل شدهٔ قبلی نداشته باشد، یعنی P(23)، ۳۴۳/۳۶۵ است. P(A’) برابر با ضرب این احتمالات مجزاست: (1) P(A') = 365/365 × 364/365 × 363/365 × 362/365 × … × 343/365 می‌توان عبارات معادله ۱ را این‌گونه جمع‌بندی کرد: (2) P(A') = (1/365)²³ × (365 × 364 × 363 × … × 343) با محاسبه معادله ۲ مقدار P(A’)=۰٫۴۹۲۷۰۳ بدست می‌آید؛ بنابراین P(A) = ۱ − ۰٫۴۹۲۷۰۳ = ۰٫۵۰۷۲۹۷ (۵۰٫۷۲۹۷٪) این روند می‌تواند برای یک گروه n نفره تعمیم داده شود، به‌طوری‌که p(n) احتمال وجود حداقل دو نفر از این n نفر است که تاریخ تولد یکسانی دارند. ساده‌تر این است که ابتدا احتمال pˉ(n)، یعنی اینکه تمام n تاریخ تولدها متفاوت باشند محاسبه شود. | ## بخش 3: مسئله تاریخ تولد | اگر n≤۳۶۵ باشد آنگاه: که در اینجا ‘!’ عمل فاکتوریل و ضریب دو جمله‌ای را نشان می‌دهد. این معادله این حقیقت را تشریح می‌کند که در نبود افرادی که تاریخ تولد یکسان داشته باشند، یک نفر دوم نمی‌تواند تاریخ تولد مشابهی با نفر اول داشته باشد (۳۶۴/۳۶۵)، سومی نمی‌تواند تاریخ تولد یکسانی با دو تای اول داشته باشد (۳۶۳/۳۶۵)، و در کل nامین تاریخ تولد نمی‌تواند با n-1 تاریخ تولد قبلی یکسان باشد. توجه کنید که مقیاس عمودی لگاریتمی است (به ازای هر واحد کم شونده ۱۰۲۰ مرتبه احتمال، کم ترمی شود). برای i=۱، اولین عبارتی که برایp(n) بدست آمد، می‌تواند به صورت زیر تخمین زده شود: در نتیجه: یک تقریب غیر دقیق تر که معادل این عبارت است به صورت زیر است: که همانگونه که نمودار نشان می‌دهد، تقریباً صحیح است. درک این مطلب ساده است که یک روش مشابه برای هر تعداد از "نفرات" و "روزهاً می‌تواند به کار رود. اگر به جای ۳۶۵ روز، n روز را در نظر بگیریم و m نفر وجود داشته باشند و m ≤ n باشد، آنگاه با استفاده از روش بالا به این نتیجه می‌رسیم که اگر Pr n, m احتمال حضور حداقل دو نفر خارج از m نفر که از میان یک مجموعه n روزه تاریخ تولد یکسان دارند باشد، آنگاه: یک توان ساده احتمال حضور هر دو نفری که تاریخ تولد یکسان نداشته باشند ۳۶۴/۳۶۵ است. در یک اتاق شامل n نفر،C(n, 2)=n(n-1)/2 تعداد زوج از نفرات حضور دارند، یعنی C(n, 2)رویداد. احتمال عدم حضور دو نفر که تاریخ تولد یکسانی داشته باشند، می‌تواند با این فرض که این رویدادها مستقل اند و بنابراین با ضرب احتمالات آن‌ها در یکدیگر تخمین زده شود. مختصراً ۳۶۴/۳۶۵ می‌تواندC(n, 2) بار در خودش ضرب شود که در این صورت خواهیم داشت: و اگر این، احتمال عدم حضور فردی با تولد یکسان باشد، آنگاه احتمال اینکه برخی نفرات تاریخ تولد یکسان داشته باشند به صورت زیر است: تقریب پوواسون با استفاده از تقریب پوواسون برای این دوجمله‌ای داریم: که باز هم این بالای ۵۰٪ است. تقریب تعداد افراد این مسئله نیز می‌تواند به وسیله فرمول زیر برای تعداد نفراتی که حضورشان برای داشتن حداقل ۵۰٪ شانس برای تطبیق ضروری است تخمین زده شود: این، نتیجه‌ای برای این تخمین مناسب است که اگر یک رویداد با احتمال ۱ در k، k ln 2 مرتبه تکرار شود، برای حداقل یک بار اتفاق افتادن ۵۰٪ شانس دارد. "احتمال تصادم" (ستون‌ها) ۵۰٪ خواهند بود و "تعداد نفرات مورد نیاز" ۲۶ نفر خواهد بود (تقاطع ستون‌ها و ردیف‌ها). برای مقایسه، 10−15 تا 10−18 سرعت خطای بیت اصلاح نشدنی برای یک دیسک سخت نوعی است. | ## جمع‌بندی | در تئوری، MD5، ۱۲۸ بیت، باید تا تقریباً ۸۲۰ میلیارد سند در آن محدوده باقی بماند، حتی اگر این احتمال وجود داشته باشد که تعداد خروجی‌ها بسیار بیشتر باشد.