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

مسئله روز تولد این سؤال را مطرح می‌کند که آیا درون یک گروه معین هیچ فردی وجود دارد که با یکی دیگر از افراد گروه تاریخ تولد مشابهی داشته باشد - نه شخص خاصی به‌طور مشخص. (به قسمت «#هم تاریخ تولد با شما» در زیر نگاه کنید برای تحلیل این مسئله جایگزینی که کمتر جالب به نظر می‌رسد) در مثالی که پیش از این مطرح شد، در لیستی شامل ۲۳ نفر، در مقایسه شانس اینکه تاریخ تولد نفر اول لیست با دیگران یکسان باشد ۲۲ است، برای نفر دوم لیست برابر با ۲۱، برای نفر سوم لیست برابر با ۲۰ و همین‌طور تا آخر. از این رو مجموع شانس‌ها برابر است با: ۲۲+۲۱+۲۱+... +۱ = ۲۵۳، بنابراین مقایسه هر فرد با تمام افراد دیگر ۲۵۳ شانس مجزا را به وجود می‌آورد (ترکیب): در یک گروه ۲۳ نفری (۲۳¦۲)= ۲۳٫۲۲/۲=۲۵۳جفت وجود دارد. با فرض اینکه احتمال تمام روزهای تولد یکسان باشد، احتمال یک تاریخ تولد داده شده برای فردی که به‌طور تصادفی از بین جمع انتخاب شده ۱/۳۶۵ (با نادیده گرفتن روز کبیسه، ۳۰ اسفند) است. اگرچه زوج‌های یک گروه ۲۳ نفری از لحاظ آماری با ۲۵۳ زوجی که به‌طور مستقل انتخاب شده‌اند هم‌ارز نیستند، اگر یک گروه بر حسب تعداد زوج‌های آن سنجیده شود، پارادوکس تولد نسبت به زمانی که بر حسب افراد سنجیده شود، کم‌تر تعجب‌برانگیز خواهد بود.

مسئله مورد نظر، محاسبه احتمال تقریبی حضور حداقل دو نفر در اتاقی با حضور 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’) برابر با ضرب این احتمالات مجزاست:

می‌توان عبارات معادله ۱ را این‌گونه جمع‌بندی کرد:

با محاسبه معادله ۲ مقدار P(A’)=۰٫۴۹۲۷۰۳ بدست می‌آید؛ بنابراین P(A) = ۱ − ۰٫۴۹۲۷۰۳ = ۰٫۵۰۷۲۹۷ (۵۰٫۷۲۹۷٪) این روند می‌تواند برای یک گروه n نفره تعمیم داده شود، به‌طوری‌که p(n) احتمال وجود حداقل دو نفر از این n نفر است که تاریخ تولد یکسانی دارند. ساده‌تر این است که ابتدا احتمال pˉ(n)، یعنی اینکه تمام n تاریخ تولدها متفاوت باشند محاسبه شود. با توجه به اصل لانه کبوتری اگر n˃۳۶۵ باشد، pˉ(n) صفر است. اگر n≤۳۶۵ باشد آنگاه:

که در اینجا ‘!’ عمل فاکتوریل و${\displaystyle (\genfrac{}{}{0ex}{}{365}{n})}$

این احتمال برای n=۲۳ از ½ بیشتر است (با مقداری در حدود ۵۰٫۷٪). جدول زیر این احتمال را برای برخی مقادیر دیگر n نشان می‌دهد (این جدول همان‌طور که در بالا شرح داده شد، از وجود سالهای کبیسه چشم پوشی می‌کند):

بسط سری تیلور برای تابع نمایی به صورت زیر است:(ثابت e تقریباً برابر است با ۲٫۷۱۸۲۸۱۸۲۸):

${\displaystyle e^x=1+x+\frac{x^2}{2!}+\cdots }$

که تقریب مرتبه اول برای e در ${\displaystyle |x|\ll 1}$

${\displaystyle e^x\approx 1+x.}$

برای به کار بردن این تقریب در اولین عبارت به دست آمده برای p(n)، ${\displaystyle x=-i/365}$

برای i=۱، ${\displaystyle 1-1/365\approx e^{-1/365}}$

اولین عبارتی که برایp(n) بدست آمد، می‌تواند به صورت زیر تخمین زده شود:

در نتیجه:

${\displaystyle p(n)=1-\overline{p}(n)\approx 1-e^{-n(n-1)/(2\times 365)}.}$

یک تقریب غیر دقیق تر که معادل این عبارت است به صورت زیر است:

${\displaystyle p(n)\approx 1-e^{-n^2/(2\times 365)},}$

که همانگونه که نمودار نشان می‌دهد، تقریباً صحیح است. درک این مطلب ساده است که یک روش مشابه برای هر تعداد از "نفرات" و "روزهاً می‌تواند به کار رود. اگر به جای ۳۶۵ روز، n روز را در نظر بگیریم و m نفر وجود داشته باشند و m ≤ n باشد، آنگاه با استفاده از روش بالا به این نتیجه می‌رسیم که اگر Pr[(n, m)] احتمال حضور حداقل دو نفر خارج از m نفر که از میان یک مجموعه n روزه تاریخ تولد یکسان دارند باشد، آنگاه: ${\displaystyle Pr[(n,m)]\approx 1-e^{-m^2/2n}.}$

احتمال حضور هر دو نفری که تاریخ تولد یکسان نداشته باشند ۳۶۴/۳۶۵ است. در یک اتاق شامل n نفر،C(n, 2)=n(n-1)/2 تعداد زوج از نفرات حضور دارند، یعنی C(n, 2)رویداد. احتمال عدم حضور دو نفر که تاریخ تولد یکسانی داشته باشند، می‌تواند با این فرض که این رویدادها مستقل اند و بنابراین با ضرب احتمالات آن‌ها در یکدیگر تخمین زده شود. مختصراً ۳۶۴/۳۶۵ می‌تواندC(n, 2) بار در خودش ضرب شود که در این صورت خواهیم داشت:

${\displaystyle {\left(\frac{364}{365}\right)}^{C(n,2)}.}$

و اگر این، احتمال عدم حضور فردی با تولد یکسان باشد، آنگاه احتمال اینکه برخی نفرات تاریخ تولد یکسان داشته باشند به صورت زیر است:

${\displaystyle p(n)\approx 1-{\left(\frac{364}{365}\right)}^{C(n,2)}.}$

با استفاده از تقریب پوواسون برای این دوجمله‌ای داریم:

${\displaystyle \mathrm{P}\mathrm{o}\mathrm{i}\left(\frac{C(23,2)}{365}\right)=\mathrm{P}\mathrm{o}\mathrm{i}\left(\frac{253}{365}\right)\approx \mathrm{P}\mathrm{o}\mathrm{i}(0.6932)}$

${\displaystyle Pr(X>0)=1-Pr(X=0)=1-e^{-0.6932}=1-0.499998=\mathrm{0.500002.}}$

که باز هم این بالای ۵۰٪ است.

این مسئله نیز می‌تواند به وسیله فرمول زیر برای تعداد نفراتی که حضورشان برای داشتن حداقل ۵۰٪ شانس برای تطبیق ضروری است تخمین زده شود:

${\displaystyle n\approx \frac{1}{2}+\sqrt{\frac{1}{4}-2\times 365\times \ln (0.5)}=\mathrm{22.999943.}}$

این، نتیجه‌ای برای این تخمین مناسب است که اگر یک رویداد با احتمال ۱ در k، k ln 2 مرتبه تکرار شود، برای حداقل یک بار اتفاق افتادن ۵۰٪ شانس دارد.

length of hex string	#bits	hash space size (2)	Number of hashed elements such that (probability of at least one hash collision) = p
			p = 10	p = 10	p = 10	p = 10	p = 10	p = ۰٫۱٪	p = ۱٪	p = ۲۵٪	p = ۵۰٪	p = ۷۵٪
۸	۳۲	۴٫۳ × 10	۲	۲	۲	۲٫۹	۹۳	۲٫۹ × 10	۹٫۳ × 10	۵٫۰ × 10	۷٫۷ × 10	۱٫۱ × 10
۱۶	۶۴	۱٫۸ × 10	۶٫۱	۱٫۹ × 10	۶٫۱ × 10	۱٫۹ × 10	۶٫۱ × 10	۱٫۹ × 10	۶٫۱ × 10	۳٫۳ × 10	۵٫۱ × 10	۷٫۲ × 10
۳۲	۱۲۸	۳٫۴ × 10	۲٫۶ × 10	۸٫۲ × 10	۲٫۶ × 10	۸٫۲ × 10	۲٫۶ × 10	۸٫۳ × 10	۲٫۶ × 10	۱٫۴ × 10	۲٫۲ × 10	۳٫۱ × 10
۶۴	۲۵۶	۱٫۲ × 10	۴٫۸ × 10	۱٫۵ × 10	۴٫۸ × 10	۱٫۵ × 10	۴٫۸ × 10	۱٫۵ × 10	۴٫۸ × 10	۲٫۶ × 10	۴٫۰ × 10	۵٫۷ × 10
(۹۶)	(۳۸۴)	(۳٫۹ × 10)	۸٫۹ × 10	۲٫۸ × 10	۸٫۹ × 10	۲٫۸ × 10	۸٫۹ × 10	۲٫۸ × 10	۸٫۹ × 10	۴٫۸ × 10	۷٫۴ × 10	۱٫۰ × 10
۱۲۸	۵۱۲	۱٫۳ × 10	۱٫۶ × 10	۵٫۲ × 10	۱٫۶ × 10	۵٫۲ × 10	۱٫۶ × 10	۵٫۲ × 10	۱٫۶ × 10	۸٫۸ × 10	۱٫۴ × 10	۱٫۹ × 10

مربع‌های سفید در این جدول تعداد هش‌های مورد نیاز برای رسیدن به احتمال رخداد تصادم (ستون) در یک فضای هش داده شده از یک اندازه معین به بیت (ردیف) را نشان می‌دهد.

(با استفاده از مقایسه تولدها: "اندازه فضای هش" (ردیف‌ها) "۳۶۵ روز" خواهند بود. "احتمال تصادم" (ستون‌ها) ۵۰٪ خواهند بود و "تعداد نفرات مورد نیاز" ۲۶ نفر خواهد بود (تقاطع ستون‌ها و ردیف‌ها). همچنین از این جدول می‌توان برای تعیین کوچک‌ترین hash size مورد نیاز استفاده کرد (کران‌های بالای معین روی hashها و احتمال خطا)، یا احتمال تصادم (برای تعداد ثابت hashها و احتمال خطا).

برای مقایسه،

تا

سرعت خطای بیت اصلاح نشدنی برای یک دیسک سخت نوعی است. در تئوری، MD5، ۱۲۸ بیت، باید تا تقریباً ۸۲۰ میلیارد سند در آن محدوده باقی بماند، حتی اگر این احتمال وجود داشته باشد که تعداد خروجی‌ها بسیار بیشتر باشد.

هم تاریخ تولد با شما

در مسئلهٔ اصلی هیچ‌کدام از دو نفر از قبل تعیین شده نبودند ولی در حالتی که هم تاریخ تولد بودن با شخصی که از پیش مشخص شده مثلاً خود شما (در اتاقی که در آن n نفر دیگر حضور دارند) مد منظر مسئله باشد احتمال به وسیلهٔ رابطهٔ زیر به دست می‌آید:

${\displaystyle q(n)=1-{\left(\frac{365-1}{365}\right)}^n}$

و برای حالت عمومی d:

${\displaystyle q(n;d)=1-{\left(\frac{d-1}{d}\right)}^n.}$

• Coincidences: the truth is out there Experimental test of the Birthday Paradox and other coincidences
• http://www.efgh.com/math/birthday.htm
• http://planetmath.org/encyclopedia/BirthdayProblem.html بایگانی‌شده در ۱۰ اوت ۲۰۱۱ توسط Wayback Machine
• Weisstein, Eric W. "Birthday Problem". MathWorld.
• A humorous article explaining the paradox
• SOCR EduMaterials activities birthday experiment
• Understanding the Birthday Problem (Better Explained)