مسئله تاریخ تولد

در تئوری احتمالات، مسئله تاریخ تولد یا پارادوکس تاریخ تولد به یافتن احتمال حضور بیش از دو نفر در مجموعه تصادفی n نفره که تاریخ تولد یکسانی داشته باشند، مربوط است. طبق اصل لانه کبوتری این احتمال وقتی که تعداد افراد حاضر برابر با ۳۶۶ (با فرض این که سال ۳۶۵ روز است، بدون در نظر سال کبیسه) شود، مساوی ۱۰۰٪ می‌شود. اگرچه احتمال ۹۹٪ وقتی که تعداد افراد تنها برابر ۵۷ نفر است حاصل می‌شود. همچنین با احتمال ۵۰٪ حداقل دو نفر تولد یکسانی بین ۲۳ نفر دارند. این نتایج با این فرض به دست می‌آید که سال دارای ۳۶۵ روز (یعنی با در نظر نگرفتن ۳۰ اسفند) و احتمال تولد افراد در آن‌ها برابر هم باشد.
محاسبات ریاضی پشت این مسئله باعث ایجاد یک حمله رمزنگاری معروف به اسم حمله روز تولد شده‌است. این حمله بر اساس مدل احتمالی مسئله تاریخ تولد، پیچیدگی توابع درهم‌سازی را کاهش می‌دهد و باعث ساده شدن شکستن آن می‌شود.
نموداری که به‌طور تقریبی احتمال حضور حداقل ۲ نفر را بین مجموعه تصادفی از افراد نشان می‌دهد.
فهم مسئله
مسئله روز تولد این سوال را مطرح می‌کند که آیا درون یک گروه معین هیچ فردی وجود دارد که با یکی دیگر از افراد گروه تاریخ تولد مشابهی داشته باشد - نه شخص خاصی به‌طور مشخص. (به قسمت «#هم تاریخ تولد با شما» در زیر نگاه کنید برای تحلیل این مسئله جایگزینی که کمتر جالب به نظر می‌رسد)
در مثالی که پیش از این مطرح شد، در لیستی شامل ۲۳ نفر، در مقایسه شانس اینکه تاریخ تولد نفر اول لیست با دیگران یکسان باشد ۲۲ است، برای نفر دوم لیست برابر با ۲۱، برای نفر سوم لیست برابر با ۲۰ و همین‌طور تا آخر. از این رو مجموع شانس‌ها برابر است با: ۲۲+۲۱+۲۱+… +۱ = ۲۵۳، بنابراین مقایسه هر فرد با تمام افراد دیگر ۲۵۳ شانس مجزا را به وجود می‌آورد (ترکیب): در یک گروه ۲۳ نفری (۲۳¦۲)= ۲۳٫۲۲/۲=۲۵۳جفت وجود دارد.
با فرض اینکه احتمال تمام روزهای تولد یکسان باشد، احتمال یک تاریخ تولد داده شده برای فردی که به‌طور تصادفی از بین جمع انتخاب شده ۱/۳۶۵ (با نادیده گرفتن روز کبیسه، ۳۰ اسفند) است. اگرچه زوج‌های یک گروه ۲۳ نفری از لحاظ آماری با ۲۵۳ زوجی که به‌طور مستقل انتخاب شده‌اند هم‌ارز نیستند، اگر یک گروه بر حسب تعداد زوج‌های آن سنجیده شود، پارادوکس تولد نسبت به زمانی که بر حسب افراد سنجیده شود، کم‌تر تعجب‌برانگیز خواهد بود.
محاسبه احتمالات
مسئله مورد نظر، محاسبه احتمال تقریبی حضور حداقل دو نفر در اتاقی با حضور n نفر، با تاریخ تولد یکسان است. برای سادگی، تفاوت‌ها در توزیع، مانند سال کبیسه، دوقلوها، تغییرات روزهای هفته و تغییرات فصلی را نادیده بگیرید و فرض کنید ۳۶۵ تاریخ تولدی که امکان پزیرند، احتمال برابری داشته باشند. توزیع تاریخ تولدها در واقعیت یکنواخت نیست، زیرا تمام تاریخ‌ها احتمال برابری ندارند.
اگر 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(3)=۳۶۳/۳۶۵.
این تحلیل تا رسیدن به فرد شماره ۲۳ ادامه پیدا می‌کند، فردی که احتمال آنکه تاریخ تولد یکسانی با افراد تحلیل شده قبلی نداشته باشد، یعنی P(23)، ۳۴۳/۳۶۵ است.
P(A’) برابر با ضرب این احتمالات مجزاست:
(1) P(A) = 365/365 × 364/365 × 363/365 × 362/365 × … × 343/365
می‌توان عبارات معادله ۱ را این‌گونه جمع‌بندی کرد:
(2) P(A) = (1/365)23 × (365 × 364 × 363 × … × 343)
با محاسبه معادله ۲ مقدار P(A’)=۰٫۴۹۲۷۰۳ بدست می‌آید؛ بنابراین P(A) = ۱ − ۰٫۴۹۲۷۰۳ = ۰٫۵۰۷۲۹۷ (۵۰٫۷۲۹۷٪)
این روند می‌تواند برای یک گروه n نفره تعمیم داده شود، به‌طوری‌که p(n) احتمال وجود حداقل دو نفر از این n نفر است که تاریخ تولد یکسانی دارند. ساده‌تر این است که ابتدا احتمال pˉ(n)، یعنی اینکه تمام n تاریخ تولدها متفاوت باشند محاسبه شود. با توجه به اصل لانه کبوتری اگر n˃۳۶۵ باشد، pˉ(n) صفر است. اگر n≤۳۶۵ باشد آنگاه:
که در اینجا ‘!’ عمل فاکتوریل و factorial operator and ضریب دو جمله‌ای را نشان می‌دهد.
این معادله این حقیقت را تشریح می‌کند که در نبود افرادی که تاریخ تولد یکسان داشته باشند، یک نفر دوم نمی‌تواند تاریخ تولد مشابهی با نفر اول داشته باشد (۳۶۴/۳۶۵)، سومی نمی‌تواند تاریخ تولد یکسانی با دو تای اول داشته باشد (۳۶۳/۳۶۵)، و در کل nامین تاریخ تولد نمی‌تواند با n-1 تاریخ تولد قبلی یکسان باشد.
این رویداد که حداقل دو نفر از n نفر تاریخ تولد یکسان داشته باشند، متمم این است که کل n تاریخ تولدها متفاوت باشند؛ بنابراین احتمال آن، یعنی p(n) برابر است با:
احتمال تقریبی این که هیچ دو نفری در یک گروه n نفری تاریخ تولد یکسان نداشته باشند. توجه کنید که مقیاس عمودی لگاریتمی است (به ازای هر واحد کم شونده ۱۰۲۰ مرتبه احتمال، کم ترمی شود).
این احتمال برای n=۲۳ از 1⁄2 بیشتر است (با مقداری در حدود ۵۰٫۷٪). جدول زیر این احتمال را برای برخی مقادیر دیگر n نشان می‌دهد (این جدول همان‌طور که در بالا شرح داده شد، از وجود سالهای کبیسه چشم پوشی می‌کند):
n
p(n)
۱۰
۱۱٫۷٪
۲۰
۴۱٫۱٪
۲۳
۵۰٫۷٪
۳۰
۷۰٫۶٪
۵۰
۹۷٫۰٪
۵۷
۹۹٫۰٪
۱۰۰
۹۹٫۹۹۹۹۷٪
۲۰۰
۹۹٫۹۹۹۹۹۹۹۹۹۹۹۹۹۹۹۹۹۹۹۹۹۹۹۹۹۹۹۸٪
۳۰۰
(۱۰۰ − (۶×10 −80 ))%
۳۵۰
(۱۰۰ − (۳×10 −129 ))%
۳۶۵
(۱۰۰ − (۱٫۴۵×10 −155 ))%
۳۶۶
۱۰۰٪
تقریب‌ها
نمودار نمایش صحت تقریب
بسط سری تیلور برای تابع نمایی به صورت زیر است:(ثابت e تقریبا برابر است با ۲٫۷۱۸۲۸۱۸۲۸):
که اولین نوع تقریب برای ex در x «۱ را به دست می‌دهد:
برای به کار بردن این تقریب در اولین عبارت به دست آمده برای p (n)، قرار دهید. آنگاه سپس برای هر عبارت در فرمول p (n) .
برای i=۱،
اولین عبارتی که برای p (n) بدست آمد، می‌تواند به صورت زیر تخمین زده شود:
\begin{align
\bar p(n) - \approx 1 \times e^{-1/365 \times e^{-2/365 \cdots e^{-(n-1)/365 \\
- = 1 \times e^{-(1+2+ \cdots +(n-۱))/۳۶۵ \\
- = e^{-(n(n-1)/2) / 365.
\end{align
در نتیجه:
یک تقریب غیر دقیق‌تر که معادل این عبارت است به صورت زیر است:
که همانگونه که نمودار نشان می‌دهد، تقریبا صحیح است.
درک این مطلب ساده است که یک روش مشابه برای هر تعداد از "نفرات" و "روزها می‌تواند به کار رود. اگر به جای ۳۶۵ روز، 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 مرتبه تکرار شود، برای حداقل یک بار اتفاق افتادن ۵۰٪ شانس دارد.
جدول احتمال
مقاله اصلی: حمله روز تولد
length ofhex string
#bits
hash spacesize(2 #bits )
Number of hashed elements such that (probability of at least one hash collision) = p
p = 10 −18
p = 10 −15
p = 10 −12
p = 10 −9
p = 10 −6
p = ۰٫۱٪
p = ۱٪
p = ۲۵٪
p = ۵۰٪
p = ۷۵٪
۸
۳۲
۴٫۳ × 10 9
۲
۲
۲
۲٫۹
۹۳
۲٫۹ × 10 3
۹٫۳ × 10 3
۵٫۰ × 10 4
۷٫۷ × 10 4
۱٫۱ × 10 5
۱۶
۶۴
۱٫۸ × 10 19
۶٫۱
۱٫۹ × 10 2
۶٫۱ × 10 3
۱٫۹ × 10 5
۶٫۱ × 10 6
۱٫۹ × 10 8
۶٫۱ × 10 8
۳٫۳ × 10 9
۵٫۱ × 10 9
۷٫۲ × 10 9
۳۲
۱۲۸
۳٫۴ × 10 38
۲٫۶ × 10 10
۸٫۲ × 10 11
۲٫۶ × 10 13
۸٫۲ × 10 14
۲٫۶ × 10 16
۸٫۳ × 10 17
۲٫۶ × 10 18
۱٫۴ × 10 19
۲٫۲ × 10 19
۳٫۱ × 10 19
۶۴
۲۵۶
۱٫۲ × 10 77
۴٫۸ × 10 29
۱٫۵ × 10 31
۴٫۸ × 10 32
۱٫۵ × 10 34
۴٫۸ × 10 35
۱٫۵ × 10 37
۴٫۸ × 10 37
۲٫۶ × 10 38
۴٫۰ × 10 38
۵٫۷ × 10 38
(۹۶)
(۳۸۴)
(۳٫۹ × 10 115 )
۸٫۹ × 10 48
۲٫۸ × 10 50
۸٫۹ × 10 51
۲٫۸ × 10 53
۸٫۹ × 10 54
۲٫۸ × 10 56
۸٫۹ × 10 56
۴٫۸ × 10 57
۷٫۴ × 10 57
۱٫۰ × 10 58
۱۲۸
۵۱۲
۱٫۳ × 10 154
۱٫۶ × 10 68
۵٫۲ × 10 69
۱٫۶ × 10 71
۵٫۲ × 10 72
۱٫۶ × 10 74
۵٫۲ × 10 75
۱٫۶ × 10 76
۸٫۸ × 10 76
۱٫۴ × 10 77
۱٫۹ × 10 77
مربع‌های سفید در این جدول تعداد هش‌های مورد نیاز برای رسیدن به احتمال رخداد تصادم (ستون) در یک فضای هش داده شده از یک اندازه معین به بیت (ردیف) را نشان می‌دهد.
(با استفاده از مقایسه تولدها: "اندازه فضای هش" (ردیف‌ها) "۳۶۵ روز" خواهند بود. "احتمال تصادم" (ستون‌ها) ۵۰٪ خواهند بود و "تعداد نفرات مورد نیاز" ۲۶ نفر خواهد بود (تقاطع ستون‌ها و ردیف‌ها). همچنین از این جدول می‌توان برای تعیین کوچک‌ترین hash size مورد نیاز استفاده کرد (کران‌های بالای معین روی hashها و احتمال خطا)، یا احتمال تصادم (برای تعداد ثابت hashها و احتمال خطا).
برای مقایسه، 10 −15 تا 10 −18 سرعت خطای بیت اصلاح نشدنی برای یک دیسک سخت نوعی است. در تئوری، MD5، ۱۲۸ بیت، باید تا تقریبا ۸۲۰ میلیارد سند در آن محدوده باقی بماند، حتی اگر این احتمال وجود داشته باشد که تعداد خروجی‌ها بسیار بیشتر باشد.