زنجیره مارکوف

زنجیره مارکف که به افتخار آندری مارکوف ریاضی‌دان اهل روسیه این گونه نام‌گذاری شده یک سیستم ریاضی است که در آن انتقال از یک حالت به حالت دیگر صورت می‌گیرد که البته تعداد این حالات قابل شمارش است. زنجیره مارکف یک فرایند تصادفی بدون حافظه‌است بدین معنی که توزیع احتمال شرطی حالت بعد تنها به حالت فعلی بستگی دارد و به وقایع قبل از آن وابسته نیست. این نوع بدون حافظه بودن خاصیت مارکف نام دارد. زنجیره مارکف در مدل سازی دنیای واقعی کاربردهای زیادی دارد.
معرفی
زنجیره مارکوف (Markov Approach modeling) یک فرایند تصادفی گسسته در زمان با خاصیت مارکف است. اگرچه برخی از نویسندگان در مورد فرایندهای پیوسته در زمان هم از اصطلاح زنجیره مارکف استفاده می‌کنند. یک فرایند تصادفی گسسته در زمان شامل سیستمی است که در هر مرحله در حالت خاص و مشخصی قرار دارد و به صورت تصادفی در هر مرحله تغییر حالت می‌دهد. مراحل اغلب به عنوان لحظه‌های زمانی در نظر گرفته می‌شوند ولی می‌توان آن‌ها را فاصله فیزیکی یا هر متغیر گسسته دیگری در نظر گرفت. خاصیت مارکف بیان می‌کند که توزیع احتمال شرطی برای سیستم در مرحله بعد فقط به حالت فعلی سیستم بستگی دارد و به حالت‌های قبل بستگی ندارد. چون سیستم به صورت تصادفی تغییر می‌کند به‌طور کلی پیش‌بینی حالت زنجیره مارکف در نقطه‌ای خاص در آینده غیرممکن است. با این حال ویژگی‌های آماری سیستم در آینده قابل پیش‌بینی است. در بسیاری از کاربردها چیزی که دارای اهمیت است همین ویژگی‌های آماری است.
تغییرات حالات سیستم انتقال نام دارند و احتمال‌هایی که به این تغییر حالت‌ها نسبت داده می‌شوند احتمال انتقال نام دارند. مجموعه‌ای از حالت‌ها و احتمال انتقال‌ها به‌طور کامل یک زنجیره مارکف را مشخص می‌کنند. طبق قرار داد، ما فرض می‌کنیم همیشه حالت بعدی وجود دارد و در نتیجه فرایند تا ابد ادامه پیدا می‌کند.
یکی از معروف‌ترین زنجیره‌های مارکف که موسوم به «پیاده‌روی می‌خواره» است یک پیاده‌روی تصادفی است که در آن در هر قدم موقعیت با احتمال برابر به اندازه ۱+ یا ۱- تغییر می‌کند. در هر مکان دو انتقال ممکن وجود دارد یکی به عدد صحیح بعدی(۱+) و یکی به عدد صحیح قبلی(۱-). احتمال هر انتقال فقط به حالت کنونی بستگی دارد. برای مثال احتمال انتقال از ۵ به ۶ برابر با احتمال انتقال از ۵ به ۴ است و هر دوی این احتمالات برابر با ۰٫۵ هستند. این احتمالات مستقل از حالت قبلی (که یا ۴ بوده یا ۶) هستند.
مثالی دیگر عادات غذایی که فقط انگور، پنیر و کاهو می‌خورد و عادات غذایی او از قوانین زیر پیروی می‌کند:
او فقط یک بار در روز می‌خورد.
اگر امروز پنیر بخورد فردا انگور یا کاهو را با احتمال برابر خواهد خورد.
اگر امروز انگور بخورد فردا با احتمال ۰٫۱ انگور، با احتمال ۰٫۴ پنیر و با احتمال ۰٫۵ کاهو خواهد خورد.
اگر امروز کاهو بخورد فردا با احتمال ۰٫۴ انگور و با احتمال ۰٫۶ پنیر خواهد خورد.
عادات غذایی این موجود را می‌توان با یک زنجیره مارکف مدل سازی کرد به دلیل این که چیزی که فردا می‌خورد (حالت بعدی) تنها به چیزی که امروز خورده‌است (حالت فعلی) بستگی دارد. یکی از ویژگی‌های آماری که می‌توان در مورد این زنجیره محاسبه کرد امید ریاضی (یا همان مقدار چشمداشتی Expected Value) درصد روزهایی است که انگور خورده‌است (در یک دوره طولانی).
تعریف رسمی
یک زنجیره مارکف دنباله‌ای از متغیرهای تصادفی X ۱ ،X ۲ ،X ۳ ،… است که دارای خاصیت مارکف هستند یعنی:
مقادیر ممکن برای X i مجموعه قابل شمارشی را می‌سازند که فضای حالت نام دارد.
تعریف دیگری به شرح ذیل عنوان شده‌است:
هرگاه فرایند تعمیرات برای سیستم‌های تعمیر پذیر لحظه‌ای یا به عبارتی با زمان کوتاه و قابل اغماض در مقایسه با زمان عملکرد سیستم را نتوان مفروض داشت، روشهایی مانند زنجیره پیوسته مارکوف برای تحلیل سیستم به کار گرفته می‌شود. روش مارکوف برای مدلسازی رفتار اتفاقی به صورت پیوسته و نا پیوسته نسبت به زمان یا در فضای حالت تقسیم‌بندی می‌گردد. این تغییرات پیوسته یا نا پیوسته اتفاقی را اصطلاحا فرایندهای اتفاقی می‌نامند. در حقیقت به‌کارگیری روش مارکوف نیازمند این امر است که سیستم نماینگر فقدان حافظه باشد. یعنی حالت و وضعیت آینده سیستم مستقل از وضعیتهای گذشته آن بوده و تنها به آخرین جزء آن وابسته باشد.
زنجیره‌های مارکف یکنواخت در زمان
زنجیره‌های مارکف یکنواخت در زمان، یا ایستا، زنجیره‌هایی هستند که در آن‌ها:
که رابطه بالا برای هر n صحیح است. در واقع احتمال انتقال مستقل از n است. چنین زنجیره‌هایی را می‌توان تنها با یک ماتریس احتمال انتقال توصیف کرد. ماتریس احتمال انتقال مستقل از زمان n است و درایه (i,j) ام آن، یعنی ، بیانگر احتمال انتقال از حالت i به حالت j می‌باشد.
زنجیره مارکف مرتبه m
زنجیره مارکف مرتبه m(که در آن m متناهی است) فرایندی است که در آن:
\begin{align
{ -\Pr(X_n=x_n|X_{n-1=x_{n-1, X_{n-2=x_{n-2, \dots , X_1=x_1) \\
-\Pr(X_n=x_n|X_{n-1=x_{n-1, X_{n-2=x_{n-2, \dots, X_{n-m=x_{n-m)
\text{ for n> m
\end{align
به عبارت دیگر حالت بعدی به m حالت قبلی وابسته‌است.
زنجیره مارکف افزاینده
یک زنجیره مارکف افزاینده مرتبه m با رابطه زیر توصیف می‌شود:
زنجیره مارکف
احتمال تغییر حالت از حالت iام به حالت jام در n حرکت برابر است با
این احتمال در یک حرکت برابر است با
برای یک زنجیره مارکوف یکنواخت در زمان
و
توجه کنید که برای یک زنجیره مارکوف یکنواخت در زمان، احتمال تغییر حالت از حالت iام به حالت jام در n حرکت معادل است با درایه (i,j) ام ماتریس احتمال انتقال وقتی این ماتریس n بار در خودش ضرب شده‌است:
در حرکت‌های n تایی احتمالات بدست آمده برابری چپمن-کولموگروف را ارضا می‌کنند. پس برای هر k که ۰ k داریم
در این رابطه S فضای حالت زنجیره مارکوف است.
توزیع حاشیه‌ای (Pr(X n = x مربوط به حرکت nام است. توزیع اولیه برابر است با (Pr(X ۰ = x . تعمیم یافته این توزیع برای حرکت‌های بعدی به شکل
نمایش داده می‌شود که در آن n زیروند است و نه توان.
تقلیل‌پذیری
حالت jام را قابل دسترسی از حالت iام می‌نامند (i → j) اگر در سیستمی که از حالت iام شروع شود با احتمال غیر ۰ در نهایت به حالت jام برسد. در واقع اگر عدد صحیح n ≥ ۰ وجود داشته باشد که
تساوی n با ۰ به معنای در دسترس بودن همه حالات از حالت iام است.
حالت iام را مرتبط با حالت jام می‌نامند (i ↔ j) اگر هر دو رابطه i → j و j → i برقرار باشند.
مجموعه حالات C را کلاس مرتبط می‌نامند اگر هر یک از اعضای آن با هر عضو دیگر این مجموعه مرتبط باشد و هیچ‌یک از اعضای C با حالتی که عضو آن نیست مرتبط نباشد. می‌توان نشان داد که ارتباط همان هم‌ارزی است و کلاس‌های مرتبط در واقع کلاس‌های هم‌ارزی هستند. یک کلاس هم‌ارزی را بسته می‌نامند اگر احتمال خروج از این کلاس ۰ باشد. به عبارت دیگر اگر حالت i در C باشد و حالت j در C نباشد، j قابل دسترسی از i نیست.
حالت i را ضروری می‌نامند اگر به ازای همه jهایی که i → j، رابطه j → i نیز برقرار باشد. حالت i را غیرضروری می‌نامند اگر ضروری نباشد.
اگر فضای حالت یک زنجیره مارکوف از تنها یک کلاس مرتبط تشکیل شده باشد، به آن تقلیل ناپذیر می‌گویند. در این زنجیره‌ها از هر حالت می‌توان به هر حالتی رسید.
تناوب
حالت i دارای دوره تناوب k است اگر هر مسیر بازگشت به حالت i به طول مضارب k باشد. به زبان دیگر دوره تناوب یک حالت برابر است با
که در آن gcd بزرگترین مقسوم علیه مشترک است.
اگر یک حالت دوره تناوب k داشته باشد ممکن است نتوان به این حالت با k حرکت رسید. به‌طور مثال اگر بتوان به حالت i در {۶, ۸, ۱۰, ۱۲, … حرکت بازگشت، در این صورت دوره تناوب برابر ۲ خواهد بود حتی اگر ۲ در مقادیر ذکر شده نباشد.
اگر k = ۱ باشد، در این صورت به حالت مد نظر غیر متناوب می‌گویند و بازگشت به حالت i در حرکت‌های غیر منظم انجام خواهد گرفت. در غیر این صورت (k > 1)، حالت iدارای دوره تناوب k و متناوب می‌باشد.
بازگشت‌پذیری
حالت i را گذرا می‌نامند که اگر سیستم از حالت i شروع به کار کند، احتمال این که دیگر به این حالت بازنگردد غیر صفر باشد. با در نظر گرفتن متعیر تصادفی T i ، زمان اولین بازگشت به حالت i، داریم
عدد احتمال بازگشت سیستم به حالت i برای اولین بار در حرکت nام است. در نتیجه حالت i گذرا است اگر
حالت غیر گذرای i را بازگشت‌کننده یا پایا می‌نامند.
اگر حالت i پایا باشد احتمال اولین بازگشت به این حالت در زمان متناهی برابر ۱ است.
متوسط زمان بازگشت
اگر زمان اولین بازگشت به حالت i با احتمال ۱ متناهی باشد، نمی‌توان نتیجه گرفت که امید ریاضی این زمان متناهی است. امید ریاضی زمان بازگشت به حالت i همان متوسط زمان بازگشت است که از رابطه
محاسبه می‌شود.
متوسط تعداد بازگشتها
می‌توان نشان داد که حالت i پایا است اگر و تنها اگر متوسط تعداد بازگشت‌ها به این حالت نامتناهی باشد. یعنی
حالت‌های مانا
حالت i را جذب‌کننده یا مانا می‌نامند اگر با ورود به این حالت خروج از آن غیرممکن باشد. در نتیجه حالت i مانا است اگر و تنها اگر
اگر هر حالت در یک سیستم به حالت مانایی برسد زنجیره مارکوف را زنجیره مارکوف مانا می‌نامند.
زنجیره ارگودیک و زنجیره باقاعده
یک زنجیره مارکوف ارگودیک است اگر بتوان از هر حالتی به حالت دیگر رسید (نه لزوما در یک حرکت). زنجیره ارگودیک زنجیره غیر تقلیل پذیر نیز نامیده می‌شود. زنجیره‌ای که هم غیر تقلیل پذیر باشد و هم غیر متناوب، زنجیره باقاعده (رگولار) نامیده می‌شود. در زنجیره باقاعده n ای وجود دارد که اگر ماتریس انتقال حالت به توان n برسد تمام درایه‌های آن مثبت خواهند بود. بدین معنا که با n حرکت می‌توان از هر حالتی به حالت دیگر رسید.
متوسط زمان اصابت
در یک زنجیره ارگودیک زمان اولین بار رسیدن یا اصابت به حالت j در حالی که زنجیر مارکوف در حالت i بوده‌است، زمان اصابت از i به j نامیده می‌شود. زمان اصابت با متغیر تصادفی به صورت زیر توصیف می‌شود:
متوسط زمان اصابت از i به j، یعنی ، از رابطه بازگشتی زیر بدست می‌آید:
تجزیه و تحلیل توزیع ثابت و محدود کردن توزیع‌ها
برای یک زنجیر یکنواخت در زمان، بردار یک «توزیع ثابت» (یا ایستا) نامیده می‌شود اگر‌ها نامنفی و جمع آن‌ها برابر ۱ شود و نیز در رابطه زیر صدق کنند:
یک زنجیره ارگودیک یک توزیع ثابت دارد اگر و فقط اگر همه حالت‌های آن مثبت باشند در این صورت  یکتاست و مربوط به زمان بازگشت مورد انتظار است:
اگر زنجیره باقاعده (غیر تقلیل پذیر و غیر متناوب) باشد آن گاه برای هر i و j داریم:
لازم است ذکر شود که هیچ شرطی روی نقطه شروع توزیع وجود ندارد یعنی زنجیره صرف نظر از نقطه شروع به توزیع ثابت میل می‌کند. این  «توزیع تعادل» زنجیره نامیده می‌شود. اگر زنجیره بیش از یک کلاس مرتبط بسته داشته باشد توزیع ثابت آن یکتا نخواهد بود. زنجیره غیر یکنواخت در زمان نیز می‌تواند توزیع تعادل داشته باشد.
در هر صورت اگر حالت j ام غیر متناوب باشد آن گاه:
و برای هر حالت i دیگر اگر f ij احتمال این باشد که زنجیره در حالت j قرار گیرد در صورتی که شروع زنجیره از حالت i باشد خواهیم داشت:
اگر حالت i متناوب باشد با دوره تناوب k > 1 آنگاه حد
وجود ندارد و نیز حد
برای هر r صحیح وجود ندارد.
زنجیر ه وارون پذیر
یک زنجیره مارکوف وارون پذیر نامیده می‌شود اگر یک توزیع احتمال بر روی حالتها وجود داشته باشد به‌طوری‌که برای تمام زمان‌های n و حالتهای i و j رابطه زیر برقرار باشد:
برای زنجیره‌های یکنواخت در زمان رابطه بالا به صورت ساده زیر نوشته می‌شود:
توزیع احتمال در رابطه بالا همان توزیع ثابت در زنجیره‌های ارگودیک می‌باشد.
کاربردها
فیزیک
سیستم‌های مارکفی در ترمودینامیک و مکانیک آماری بسیار ظاهر می‌شوند، جایی که احتمال برای نشان دادن ویژگی‌های ناشناخته سیستم به کار می‌رود، اگر بتوان فرض کرد که دینامیک مستقل از زمان است و احتیاجی به بررسی پیشینه تاریخی آن نیست.
علم اطلاعات
زنجیره مارکف در نظریه اطلاعات کاربرد دارد. مقاله معروف کلود شانون در سال ۱۹۴۸ با «نظریه ریاضی ارتباطات» که پایه‌گذار نظریه اطلاعات شد با معرفی آنتروپی از طریق مدل‌سازی مارکف از زبان انگلیسی آغاز می‌شود. چنین مدل‌های ایده‌آلی بسیاری از قواعد آماری سیستم را به دست می‌دهند. حتی بدون داشتن ساختار کامل سیستم این گونه مدل سازی‌ها فشرده سازی موثر داده‌ها را ممکن می‌سازند.
زنجیره‌های مارکف پایه و اساس مدل پنهان مارکف است که این مدل یکی از ابزارهای مهم در زمینه‌های گوناگون مثل شبکه‌های تلفن (برای تصحیح خطا)، تشخیص گفتار و هم چنین بیوانفورماتیک است.
نظریه صف
زنجیره‌های مارکف اساس رفتار تحلیلی صف‌ها(نظریه صف) می‌باشد و این امر وجود آن‌ها را برای بهینه‌سازی عملکرد شبکه‌های مخابراتی حیاتی می‌سازد. جایی که پیام‌ها برای منابع محدود (مانند پهنای باند) رقابت می‌کنند.
مثال‌های زنجیره مارکوف
بازی‌های تخته‌ای با تاس
بازی مار و پله یا هر بازی دیگری که حرکات بوسیله تاس تعیین می‌شود یک زنجیره مارکوف هستند. این نوع بازی‌ها در نقطه مقابل بازی‌های کارتی مانند blackjack هستند که کارت‌ها مانند حافظه حرکت قبلی عمل می‌کنند. برای درک این تفاوت‌ها احتمال یک حرکت مشخص را در بازی در نظر بگیرید. در بالا به بازی‌هایی که با تاس بازی می‌شوند اشاره کردیم، تنها چیزی که اهمیت دارد حالت کنونی روی تخته است. حالت بعدی روی تخته به حالت کنونی و چرخش بعدی تاس بستگی دارد و وابسته به اینکه که مهره‌ها چگونه در حالت کنونی قرار گرفته‌اند، نیست. در بازی مانند blackjack، بازیکن می‌تواند با به خاطر سپردن اینکه کدام کارت‌ها تاکنون نشان داده شده‌اند، برتری کسب کنند؛ بنابراین حالت بعدی بازی مستقل از حالت کنونی نیست.
گام‌های تصادفی متمایل به مرکز
یک حرکت تصادفی روی تعدادی خط را در نظر بگیرید، موقعیت کنونی (که x نامیده می‌نامیم) با احتمالات زیر می‌تواند به +۱ (به راست) یا -۱(به چپ) تغییر کند:
(c یک عدد ثابت بزرگتر از ۰ است)
به عنوان مثال اگر عدد ثابت c برابر ۱ باشد، احتمال حرکت به چپ از موقعیت x=-۲,-۱،۰،۱،۲ به ترتیب برابرست با:.
یک گام تصادفی یک اثر مرکزی دارد به‌طوری‌که با افزایش تضعیف c می‌شود. از آنجایی که احتمالات تنها به وضعیت کنونی بستگی دارد (مقدار x) و وابسته به هیچ‌یک از موقعیت‌های قبلی نیست، این گام تصادفی متمایل به مرکز در تعریف زنجیره مارکوف صدق می‌کند.
یک مدل آب و هوایی بسیار ساده
احتمال وضعیت آب و هوایی که آب و هوا در طول روز را نشان می‌دهد و هم به صورت بارانی و هم آفتابی مدل می‌شود، توسط یک ماتریس انتقال ارائه داده می‌شود.
ماتریس P یک مدل آب و هوایی را نشان می‌دهد به‌طوری‌که روز بعد یک روز آفتابی، با احتمال %۹۰ آفتابی است و روز بعد یک روز بارانی، با احتمال %۵۰ آفتابی است. ستونها و سطرها با آفتابی و بارانی برچسب‌گذاری می‌شوند.
(P) i j احتمال این است که هوای امروز از نوع i باشد و فردا از نوع j باشد.
در نظر داشته باشید که حاصل جمع احتمالات سطر P برابر ۱ است.
حالت ثابت آب و هوا
در این مثال، پیش‌بینی هوا در روزهای دور از هم ↵غلط از آب در می‌آید و متمایل به بردار حالت پایدار است. این بردار احتمال هوای آفتابی و بارانی را در همه روزها نشان می‌دهد و مستقل از آب وهوای اولیه است.
بردار حالت ثابت به این صورت تعریف می‌شود:↵
\mathbf{q = \lim_{n \to \infty \mathbf{x^{(n)
ولی تنها زمانی به یک مقدار منظم همگراست که p یک ماتریس انتقال منظم باشد (بعبارت دیگر حداکثر یک P n با ورودیهای غیر صفر وجود دارد)
از آنجایی که q مستقل از شرایط اولیه است، زمانی که بوسیله P ترجمه می‌شود، بایستی بدون تغییر بماند؛ که این باعث می‌شود که q تبدیل به بردار ویژه شود، به این معنی که از P مشتق شود. برای مثال آب و هوا:
\begin{matrix
P - = - \begin{bmatrix
0.9 - 0.1 \\
0.5 - 0.5
\end{bmatrix
\mathbf{q P - = - \mathbf{q
- \mbox{( \mathbf{q \mbox{ is unchanged by P \mbox{.)
- = - \mathbf{qI
\mathbf{q (P - I) - = - \mathbf{0 \\
- = - \mathbf{q \left( \begin{bmatrix
0.9 - 0.1 \\
0.5 - 0.5
\end{bmatrix
\begin{bmatrix
1 - 0 \\
0 - 1
\end{bmatrix
\right)
- = - \mathbf{q \begin{bmatrix
-0.1 - 0.1 \\
0.5 - -0.5
\end{bmatrix
\end{matrix
\begin{bmatrix
q_1 - q_2
\end{bmatrix
\begin{bmatrix
-0.1 - 0.1 \\
0.5 - -0.5
\end{bmatrix
\begin{bmatrix
0 - 0
\end{bmatrix
پس↵
-0.1 q_1 + 0.5 q_2 = 0
↵و از آنجایی که این دو بردارند داریم ↵
q_1 + q_2 = 1
حل این دو معادله یک توزیع حالت یکنواخت را می‌دهد:
\begin{bmatrix
q_1 - q_2
\end{bmatrix
\begin{bmatrix
0.833 - 0.167
\end{bmatrix
در نتیجه %۸۳ روزها آفتابی است.