یک تمرین زنجیره مارکوف وسوسه‌انگیز

به قول علما، مسألتاٌ: حداقل چند نفر آدم باید در یک جا جمع باشند تا روز تولد تک تک آنها با یکدیگر و با احتمال بیش از ۹۵٪ همه روزهای هفته را تشکیل دهد

 http://www.beytoote.com/images/stories/fun/fu395.jpgبرای حل این تمرین – که البته مساله مشهوری هم هست در عالم ریاضیات- به کمک زنجیره‌های مارکوف ۱.۵ نمره مازاد امتحانی درنظر گرفته شده است (البته مشروط بر اینکه این جواب تا پایان آبانماه به ایمیل بنده ارسال شده باشد). اما برای حل آن یک راهنمایی هم می‌کنم. فرض کنید n تعداد نفرات مجهولی را نشان دهد که ما به دنبال تعیین آن هستیم. سیستمی را در نظر بگیری که ۸ حالت یا وضعیت دارد (مطابق با ۷ روز هفته از شنبه تا جمعه و یک وضعیت شروع خالی) . به این ترتیب که اگر سیستم در وضعیت k باشد بدان معناست که روزهای تولد جمعیت K روز هفته را تشکیل می‌دهند. بدیهی است که وقتی سیستم در وضعیت k قرار دارد به وضعیت قبلی خود بر نمی‌گردد. با پرسیدن روز تولد نفر بعدی سیستم ممکن است در همان وضعیت باقی بماند و یا ممکن است به وضعیت k+1 برود. احتمال  ماندن در همان وضعیت قطعا k/۷ است و احتمال تغییر وضعیت به k+1 هم که روشن است. سیستم مدنظر از حالت ۰ شروع می‌کند و با احتمال ۱ به حالت ۱ تغییر وضعیت می‌دهد و …… . حال سوال این است که چه توانی از این زنجیره مارکوف تضمیین می‌کند که احتمال حرکت از ۰ به ۷ بزرگتر از ۹۵٪ باشد…… به همین سادگی. فقط یک مشکل وجود دارد و آن هم این است که باید به نحوی توان n ام این ماتریس را محاسبه کرد که از این جا به بعد داستان را دانشجوی علاقمند و صدالبته طالب نمره باید پیدا کند…….. پس منتظر ایمیل‌هایتان هستم

لطفا نظر خود را بنویسید

یک دیدگاه

  • با  استفاده از قضیه ی ch-k میشه در مرحله اول به این مسئله نیگاه کرد. یعنیp(1,1)*p(1,2)*p(2,2)
    *p(2,3)*p(3,3)*p(3,4)*
    p(4,4)*p(4,5)*p(5,5)*
    p(5,6)*p(6,6)*p(6,7)*p(7,7)
    سوالی که الان پیش میاد اینه کهطبقی فرمایشاتی استادما باید ببینیم چه چوری میشه از ۰ به ۷ رسید که حاصلضربها بزرگتر از ۰.۹۵ بشه؟؟!!!من فکر میکنم با توجه به جواب جواب ch-k یه همچین معادله ای بشه جور کرد:.۰۰۶۲^x=.95x=log.95درمبنای..۰۰۶۲دوستان کسی اگه نظری داره راهنمایی کنه تا مسئله را حل کنیم سپاس گرازم