طبق وعدهی پیشین قرار بود مهلت آخر ارسال جوابها دیشب باشد و البته یک روز هم مهلت اضافی درنظر گرفته شد تا دوستانی که اظهار تمایل و علاقه به حل این مسأله داشتند فرصت کافی برای ارسال جولب داشته باشند که تعدادی از دانشجویان نیز جواب را ارسال کرده اند
اما بعد:
اولا برای دریافت فایل PDF جواب مفصل این سوال حتما اینجا را کیک کنید.
همانطور که در متن مساله (این پست را ببینید) اشاره کرده بودم برای حل این مسأله باید سیستمی را در نظر میگرفتیم که داراری ۸ حالت است و گذار بین حالتها مطابق با آنچه که در کلاس نیز شرح دادم به صورت زیر است:
در این سیستم، زمانی که در وضعیت k هستیم بدان معنی است که روز تولد افراد مورد بررسی k روز هفته را تشکیل داده است. به این ترتیب ماتریس احتمالات گذار بین حالتها قابل محاسبه است
به این ترتیب وقتی که n بار روی این زنجیره – با شروع از صفر- حرکت کنیم. آرایه ردیف ۰ و ستون ۷ نشان دهنده آن است که چقدر احتمال دارد روزهای تولد n نفر هفت روز هفته را پوشش دهد (چرا؟؟؟؟). بنابراین جواب مسأله عبارت خواهد بود از یافتن nای که
اما چگونه این n را بیابیم؟؟؟؟؟؟؟؟؟
۱- روش ضرب متوالی ماتریسها: که قریب به اتفاق جوابها از این کلک رشتی؟؟؟ استفاده کردهاند و جواب را پیدا کردهاند. بنابراین به این بخش از دوستان نیز نمرهای تعلق خواهد گرفت. توضیح آن در متن هست
۲- روش تجزیه ماتریس
و خوب مابقی جواب مشخص است. این راه حل هم به عنوان مثال با استفاده از دو دستور محاسبه مقدار ویژه و محاسبه معکوس ماتریس قابل محاسبه است. دوستانی که به این راه حل رسیده باشند نسبت به دوستان ردیف اول نمره بیشتری کسب خواهند کرد
۳- راه حل عام: اگر کسی به هر نحوی راه حل عمومی برای این مسأله از طریق تعمیم راه حل ۲ به دست آورده باشد نمره کامل را خواهد گرفت. من راه حل عمومی را در متن پاسخنامه مفصلی که به پیوست این پست قرار داده ام آوردهام. لازم است دوستان با عنایت مخصوص راه حل را بخوانند.
روش تجزیه ماتریس:
از آنجاییکه ماتریس یک ماتریس مربع است، دارای مقدار ویژه است. فرض میکنیم که این مقادیر ویژه منفرد (غیرتکراری) و غیر صفر هستند. فرض منفرد بودن مقادیر ویژه ماتریس احتمالات گذار در بسیاری از کاربردهای عملی برقرار است (به غیر از مواردی که زنجیره مارکوف کاهش پذیر و تناوبی است که در این حالت نیز با تغییراتی بحثهای آتی برقرار است). علاوه بر این مقدار ویژه صفر نیز ممکن است در میان مقادیر ویژه باشد که فعلا این حالت را نیز در نظر نمیگیریم\cite{Papoulis1991}. با این مقدمات فرض کنید که جفتهای زوج مقدار- بردار ویژه ماتریس باشند. داریم:
(۱)
یا
(۲)
که در آن ماتریسهای مربعی و به صورت زیر تعریف میشوند:
(۳)
و
(۴)
از آنجا که ها بردارهای ستونی و مستقل خطی هستند، ماتریس یک ماتریس غیرمنفرد و دارای وارون است و داریم:
(۵)
که:
(۶)
که:
(۷)
که در آن نشاندهندهی امین بردار سطری از ماتریس است و (یا ) است. از معادلهی ۵ به دست میآوریم که:
(۸)
و یا:
(۹)
به بیان سادهتر معادلات بالا بیانکننده این هستند که به ازای هر یک از مقادیر ویژه ماتریس نظیر بردارهای و مجموعه معادلات زیر را ارضا میکنند
(۱۰)
(۱۱)
به این ترتیب میتوان الگوریتمی برای محاسبه مستقیم به دست آورد:
\begin{enumerate}
\item
ابتدا مقادیر ویژه ماتریس احتمالات گذار از حل معادله به دست میآیند.
\item
برای هر یک از مقادیر ویژه با استفاده از معادلات ۱۰ و ۱۱ بردارهای و محاسبه میشوند. ضمناً چون بردارهای و وارون یکدیگر هستند مقدار ضریب نرمالکننده از رابطهی زیر محاسبه میشود
(۱۲)
(۱۳)
\item
در نهایت بر حسب مقادیر ، و احتمال گذار از به با گام از طریق رابطهی زیر محاسبه میشود:
(۱۴)
\end{enumerate}
حل مساله
برای حل مسأله در حالت کلی، اجازه بدهید که آن را به این صورت بازطرح کنیم. فرض کنید سبد خالی وجود دارد. در هر مرحله به تصادف توپی در یکی از این سبدها انداخته میشود. احتمال افتادن توپ به هر یک از این سبدها برابر است و به محتوای سبدها ربطی ندارد. ظرفیت سبدها نیز در این احتمال بیتأثیر است. فرض کنید توپ به این روش درون سبدها انداخته شده است. احتمال اینکه سبد از مجموعهی سبدها خالی و فاقد هر توپی باشد چقدر است؟
مطابق آنچه که در بخش اول گفتیم، میتوان این مسأله را به محاسبهی یک احتمال در زنجیره مارکوف سیستمی تحویل کرد که متشکل از حالت است. در این سیستم، اگر در وضعیت باشیم بدان معنی است که تا از سبدها دارای توپ و تا از سبدها فاقد توپ است.
اگر توپ درون سبدها انداخته شده باشد، احتمال اینکه سبد خالی باشد برابر است با . برای محاسبهی این احتمال لازم است توان ام ماتریس را به شکل صریح محاسبه کنیم. برای این منظور از الگوریتم بخش قبلی استفاده میکنیم.
مطابق با آنچه در این زنجیره مشاهده میشود، و به این ترتیب معادله~۱۰ مربوط به محاسبه ها به رابطهی زیر تقلیل مییابد:
(۱۵)
در حالت مقدار برای تمام ها برابر با ۱ خواهد بود. ضمناً در حالت بهازای مقدار به دست میآید و با جایگذاری مستقیم در رابطهی بالا به ازای نیز مقدار به دست میآید و به همین ترتیب تا پایان. اما مقادیر بردارهای ویژه همگی نمیتوانند صفر باشند. بنابراین باید ای وجود داشته باشد که باشد اما . در این حالت از معادلهی ~۱۵ به دست میآید که: و لذا مقادیر ویژه عبارت خواهند بود از:
(۱۶)
با این مقدار ویژه معادلهی ~۱۵ به صورت زیر تبدیل خواهد شد:
(۱۷)
از حل این معادلهی بازگشتی داریم:
(۱۸)
به روشی مشابه و با حل معادلهی~۱۱ به ازای داریم:
(۱۹)
یا:
(۲۰)
(۲۱)
اما، برای محاسبهی ضرایب نرمالکننده (چون ) به این نکته توجه میکنیم که برای مقدار و برای مقدار=”” ” است=”” و=”” در=”” نتیجه=”” از=”” معادلهی=”” ~۱۳=”” داریم=”” ” <="" p="">
با جایگذاری مقادیر روابط ~۲۱ و ~۱۸ در رابطهی ~۱۴ داریم:
(۲۲)
میدانیم که برای داریم:=””
بر اساس رابطهی ~۲۲ در حالت خاص و برای ( حالت شروع) معادلهی ۲۲ به رابطهی۲۳ کاهش مییابد
(۲۳)
رابطهی۲۳ احتمال پر بودن سبد بعد از پرتاپ تصادفی توپ بین سبد (یا خالی بودن سبد) را نشان میدهد. از این رابطه میتوانیم برای پاسخگویی به احتمال خواسته شده در مسأله استفاده کنیم.
فرض کنید تعداد سبدهای خالی در مرحلهی را نشان دهد. متغیر جدید را تعریف میکنیم بهگونهای که:
(۲۴)
برای محاسبهی حالت حدی زمانیکه و در رابطهی ۲۴ داریم:
(۲۵)
و
(۲۶)
و با جایگذاری این دو در رابطهی۲۴ داریم:
(۲۷)
(۲۸)
بر اساس این رابطه، اگر و بهگونهای تغییر یابند که محدود باقی بماند، احتمال خالی ماندن سبد، زمانیکه توپ میان سبد (بدواً خالی) به صورت تصادفی توزیع میشود از توزیع پوآسون۲۷ تبعیت میکند. به این ترتیب مثلاً احتمال اینکه روز تولد یک جمعیت ۲۰۰۰ نفری تمام ۳۶۵ روز یک سال را پوشش دهد برابر است با (با قرار دادن در ۲۷ و محاسبهی بر اساس رابطهی۲۸ )
حال با این مقدمهی نسبتاً مفصل برگردیم به مسألهی خودمان؛ برای محاسبهی این که حداقل چند نفر باید در یکجا جمع باشند تا با احتمال بیش از ۹۵٪ روز تولد آنها تمام روزهای هفته را بپوشاند بایستی مقدار ای را محاسبه کنیم که به ازای آن باشد. به این ترتیب داریم:
(۲۹)