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

زنجیرهٔ مارکوف (به انگلیسی: Markov Chain) مدلی تصادفی برای توصیف یک توالی از رویدادهای احتمالی است که در آن احتمال هر رویداد فقط به حالت رویداد قبلی بستگی دارد. زنجیرهٔ مارکوف که به افتخار آندری مارکوف ریاضی‌دان اهل روسیه این گونه نام‌گذاری شده، یک سیستم ریاضی است که در آن انتقال میان حالات شمارا، از حالتی به حالت دیگر صورت می‌گیرد. زنجیرهٔ مارکوف یک فرایند تصادفی بدون حافظه است، بدین معنی که توزیع احتمال شرطی حالت بعد تنها به حالت فعلی بستگی دارد و مستقل از گذشتهٔ آن است. این نوع بدون حافظه بودن خاصیت مارکوف نام دارد. زنجیرهٔ مارکوف در مدل‌سازی دنیای واقعی کاربردهای زیادی دارد.

نمونه‌ای از زنجیرهٔ مارکوف با سه حالت

معرفی

زنجیرهٔ مارکوف (Markov Approach modeling) یک فرایند تصادفی گسسته در زمان با خاصیت مارکوف است. اگرچه برخی از نویسندگان در مورد فرایندهای پیوسته در زمان هم از اصطلاح زنجیرهٔ مارکوف استفاده می‌کنند. یک فرایند تصادفی گسسته در زمان شامل سیستمی است که در هر مرحله در حالت خاص و مشخصی قرار دارد و به صورت تصادفی در هر مرحله تغییر حالت می‌دهد. مراحل اغلب به عنوان لحظه‌های زمانی در نظر گرفته می‌شوند ولی می‌توان آن‌ها را فاصله فیزیکی یا هر متغیر گسسته دیگری در نظر گرفت. خاصیت مارکوف بیان می‌کند که توزیع احتمال شرطی برای سیستم در مرحله بعد فقط به حالت فعلی سیستم بستگی دارد و به حالت‌های قبل بستگی ندارد. چون سیستم به صورت تصادفی تغییر می‌کند به‌طور کلی پیش‌بینی حالت زنجیره مارکوف در نقطه‌ای خاص در آینده غیرممکن است. با این حال ویژگی‌های آماری سیستم در آینده قابل پیش‌بینی است که در بسیاری از کاربردها همین ویژگی‌های آماری بسیار حائز اهمیت است.

تغییرات حالات سیستم انتقال نام دارند و احتمال‌هایی که به این تغییر حالت‌ها نسبت داده می‌شوند احتمال انتقال نام دارند. یک فرایند مارکوف با یک فضای حالت شمارا، یک ماتریس گذار برای توصیف احتمال‌های هر انتقال و یک حالت اولیه (یا توزیع اولیه) در فضای حالت مشخص می‌شود. اگر فضای حالت متناهی باشد زنجیر مارکوف را زنجیر مارکوف متناهی یا زنجیر مارکوف با فضای حالت متناهی می‌گوییم و اگر نامتناهی باشد زنجیر مارکوف را زنجیر مارکوف نامتناهی یا زنجیر مارکوف با فضای حالت نامتناهی می‌گوییم. طبق قرار داد، فرض می‌کنیم همیشه حالت بعدی وجود دارد و در نتیجه فرایند تا ابد ادامه پیدا می‌کند.

یکی از معروف‌ترین زنجیره‌های مارکوف که موسوم به «پیاده‌روی می خواره» است یک پیاده‌روی تصادفی است که در آن در هر قدم موقعیت با احتمال برابر به اندازه ۱+ یا ۱- تغییر می‌کند. در هر مکان دو انتقال ممکن وجود دارد یکی به عدد صحیح بعدی(۱+) و یکی به عدد صحیح قبلی(۱-). احتمال هر انتقال فقط به حالت کنونی بستگی دارد. برای مثال احتمال انتقال از ۵ به ۶ برابر با احتمال انتقال از ۵ به ۴ است و هر دوی این احتمالات برابر با ۰٫۵ هستند. این احتمالات مستقل از حالت قبلی (که یا ۴ بوده یا ۶) هستند.

مثالی دیگر عادات غذایی موجودی است که فقط انگور، پنیر و کاهو می‌خورد و عادات غذایی او از قوانین زیر پیروی می‌کند:

• او فقط یک بار در روز غذا می‌خورد.
• اگر امروز پنیر بخورد فردا انگور یا کاهو را با احتمال برابر خواهد خورد.
• اگر امروز انگور بخورد فردا با احتمال ۰٫۱ انگور، با احتمال ۰٫۴ پنیر و با احتمال ۰٫۵ کاهو خواهد خورد.
• اگر امروز کاهو بخورد فردا با احتمال ۰٫۴ انگور و با احتمال ۰٫۶ پنیر خواهد خورد.

عادات غذایی این موجود را می‌توان با یک زنجیره مارکوف مدل‌سازی کرد به دلیل این که چیزی که فردا می‌خورد (حالت بعدی) تنها به چیزی که امروز خورده‌است (حالت فعلی) بستگی دارد. یکی از ویژگی‌های آماری که می‌توان در مورد این زنجیره محاسبه کرد امید ریاضی درصد روزهایی است که انگور خورده‌است (در یک دوره طولانی).

مثال‌هایی از زنجیره مارکوف

ورشکستگی قمارباز

ورشکستگی قمارباز مسئله‌ای معروف از زنجیره مارکوف است. در این مسئله دو فرد سکه پرتاب می‌کنند و هر بار که سکه شیر آمد شخص A یک دلار از B می‌برد و هر بار سکه خط بیاید، شخص B یک دلار از A می‌برد. در ابتدای بازی A مقدار a دلار و B مقدار b دلار دارد. فرض کنید X_i دارایی A پس از i مرحله بازی باشد. یکی از خواص دنبالهٔ {X_i} این است که اگر در مرحلهٔ nام مقدار X_i را بدانیم در این صورت سرمایه A از آن مرحله به بعد تنها به X_n و نه به X₀, X₁, …, X_n-1 وابسته است. یعنی اگر سرمایهٔ A در زمان حال معلوم باشد، سرمایهٔ آیندهٔ او مستقل از پولی است که در هر مرحله از بازی در گذشته برنده شده یا باخته‌است.

فرایند زاد مرگ

اگر صد دانه ذرت در فری قرار دهیم، هر دانه در زمانی مستقل که از توزیع نمایی پی‌روی می‌کند، منفجر می‌شود. این مثالی از زنجیره زمان پیوسته مارکوف است. اگر X_t نشان‌دهنده تعداد دانه‌های ذرتی باشد که تا زمان t منفجر شده‌اند، مسئله را می‌توان به صورت تعداد دانه‌هایی که بعد از t منفجر می‌شوند مطرح نمود. دانستن زمان انفجار دیگر دانه‌ها اهمیتی ندارد و تنها دانستن تعداد دانه‌هایی که تا کنون منفجر شده‌اند کافیست. فرایند شرح داده شده در این‌جا، تقریبی از یک فرایند پواسونی است. در حالت کلی فرایندهای پواسون نیز فرایند مارکوف هستند.

بازی‌های تخته‌ای با تاس

بازی تخته نرد یا هر بازی دیگری که حرکات با تاس تعیین می‌شود یک زنجیرهٔ مارکوف هستند. این نوع بازی‌ها در نقطه مقابل بازی‌های کارتی مانند 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ⁿ با ورودی‌های غیر صفر وجود دارد)

از آنجایی که 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 {q} I\\\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.1q_{1}+0.5q_{2}=0$ و از آنجایی که این دو بردار احتمال هستند، داریم $q_{1}+q_{2}=1$

حل این دو معادله یک توزیع حالت یکنواخت را می‌دهد:

${\begin{bmatrix}q_{1}&q_{2}\end{bmatrix}}={\begin{bmatrix}0.833&0.167\end{bmatrix}}$

در نتیجه %۸۳ روزها آفتابی است.

تعریف رسمی

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

یک زنجیره مارکوف دنباله‌ای از متغیرهای تصادفی X_۱،X_۲،X_۳،... است که دارای خاصیت مارکوف هستند یعنی:

$\Pr(X_{n+1}=x|X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n})=\Pr(X_{n+1}=x|X_{n}=x_{n}).\,$

مقادیر ممکن برای X_i مجموعه قابل شمارشی را می‌سازند که فضای حالت نام دارد.

زنجیره مارکوف اغلب توسط دنباله‌ای از گراف‌های جهت‌دار نشان داده می‌شود، که در آن یال‌های گراف n توسط احتمال از رفتن از یک حالت در زمان n به حالت‌های دیگر در زمان n + 1 برچسب گذاری شده‌است. همان اطلاعات در ماتریس انتقال از زمان n به زمان n + 1 درج می‌شود که در آن عنصر سطر i و ستون j، احتمال تغییر وضعیت از حالت i-1 به حالت j-1 است. مجموع عناصر هر سطر برابر یک است اما الزاماً مجموع عناصر هر ستون یک نمی‌شود. در نظریه ماتریس‌ها اگر تمام عناصر ماتریسی نامنفی و مجموع عناصر هر سطر یک باشد، در این صورت آن ماتریس را ماتریس مارکوف می‌گویند. علت آن است که برای چنین ماتریس‌هایی می‌توانیم یک فضای نمونه بسازیم به طوری که عناصر ماتریس، احتمال‌های تغیر وضعیت تمام پیشامدهای فضای نمونه باشند و سپس یک زنجیر مارکوف برای فضای نمونه تعریف کنیم. با این حال، زنجیره‌های مارکوف اغلب به صورت یکنواخت در زمان فرض می‌شوند در این صورت گراف و ماتریس مستقل از n هستند و به این ترتیب به شکل یک توالی ارائه نمی‌شوند.

تعریف دیگری به شرح ذیل عنوان شده‌است: هرگاه فرایند تعمیرات برای سیستم‌های تعمیر پذیر لحظه‌ای یا به عبارتی با زمان کوتاه و قابل اغماض در مقایسه با زمان عملکرد سیستم را نتوان مفروض داشت، روش‌هایی مانند زنجیرهٔ پیوسته مارکوف برای تحلیل سیستم به کار گرفته می‌شود. روش مارکوف برای مدلسازی رفتار اتفاقی به صورت پیوسته و ناپیوسته نسبت به زمان یا در فضای حالت تقسیم‌بندی می‌گردد. این تغییرات پیوسته یا ناپیوسته اتفاقی را اصطلاحاً فرایندهای اتفاقی می‌نامند. در حقیقت به‌کارگیری روش مارکوف نیازمند این امر است که سیستم نماینگر فقدان حافظه باشد. یعنی حالت و وضعیت آیندهٔ سیستم مستقل از وضعیتهای گذشته آن بوده و تنها به آخرین جزء آن وابسته باشد.

زنجیره‌های مارکوف یکنواخت در زمان

زنجیره‌های مارکوف یکنواخت در زمان، یا ایستا، زنجیره‌هایی هستند که در آن‌ها:

$\Pr(X_{n+1}=x|X_{n}=y)=\Pr(X_{n}=x|X_{n-1}=y)\,$

که رابطه بالا برای هر n صحیح است. در واقع احتمال انتقال مستقل از n است. چنین زنجیره‌هایی را می‌توان تنها با یک ماتریس احتمال انتقال $P$ توصیف کرد. ماتریس احتمال انتقال $P$ مستقل از زمان n است و درایهٔ (i,j) ام آن، یعنی $p_{ij}$، بیانگر احتمال انتقال از حالت i به حالت j می‌باشد.

زنجیره مارکوف مرتبه m

زنجیره مارکوف مرتبه m (که در آن m متناهی است) فرایندی است که در آن:

${\begin{aligned}{}&\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{aligned}}$

به عبارت دیگر حالت بعدی به m حالت قبلی وابسته‌است. می‌توان یک {Y_n} از {X_n} ساخت به طوری که در فرم کلاسیک خاصیت مارکوف صدق کند؛ که در این صورت Y یک چندتایی مرتب از Xها است یعنی:$Y_{n}=\left(X_{n},X_{n-1},\ldots ,X_{n-m+1}\right)$

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

یک زنجیره مارکوف افزاینده مرتبه m با رابطه زیر توصیف می‌شود:

$\Pr(X_{n}=x_{n}|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{n-m}=x_{n-m})=\sum _{r=1}^{m}f(x_{n},x_{n-r},r).$

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

لامپی را در نظر بگیرید که یا روشن است یا خاموش. اگر لامپ در زمان t روشن باشد X(t) = 1 و اگر خاموش باشد X(t) = 0. در این صورت متغیر تصادفی X زمان گسسته نیست زیرا پس از ورود به حالتی برای یک مدت زمانی که خود نیز متغیری تصادفی است، در آن جا می‌ماند و سپس به حالت دیگری منتقل می‌شود. این قبیل فرایندها را زنجیره مارکوف زمان پیوسته می‌نامیم.

یک زنجیره پیوسته مارکف توسط یک فضای حالت متناهی یا شمارا، یک ماتریس نرخ انتقال Q با ابعادی برابر با فضای حالت است. برای i ≠ j، هر عنصر q_ij غیر منفی است و نرخ انتقال فرایند را از حالت i به حالت j توصیف می‌کند.

سه تعریف برای فرایندهای مارکوف زمان پیوسته وجود دارد:

تعریف حدی

اگر متغیر تصادفی وضعیت زنجیره درلحظهٔ t با X_t نشان دهیم و فرض کنیم زنجیره در زمان t در حالت i قرار دارد. با توجه به این که X_t = i و X_t+h به مقادیر گذشته وابسته نیستند، هنگامی که h → ۰ برای هر j و t داریم:

$\Pr(X(t+h)=j\mid X(t)=i)=\delta _{ij}+q_{ij}h+o(h)$

که در این معادله $\delta _{ij}$ دلتای کرونکر است و همچنین از نماد o کوچک استفاده شده‌است. q_ij می‌تواند معیاری از سرعت تغییر حالت از i به j باشد.

تعریف زنجیره پرش یا زمان نگهداری

اگر متغیر تصادفی Y_n نشان‌دهندهٔ nامین پرش (تغییر حالت) در زنجیره باشد و متغیرهای $S_{1},S_{2},S_{3},...$ زمان ایستایی در هر حالت را نشان دهند، هر کدام از S_iها از توزیعی نمایی با پارامتر $q_{Y_{i}Y_{i}}$ پیروی می‌کنند.

تعریف احتمال انتقال

برای هر مقدار $n=0,1,2,...$ و زمان‌های $t_{0},t_{1},t_{2},...$ با حالت‌های $i_{0},i_{1},i_{2},...$ داریم:

$\Pr(X_{t_{n+1}}=i_{n+1}\mid X_{t_{0}}=i_{0},X_{t_{1}}=i_{1},\ldots ,X_{t_{n}}=i_{n})=p_{i_{n}i_{n+1}}(t_{n+1}-t_{n})$

که در آن p_ij در دو مجموعه معادلات دیفرانسیلی به نام‌های معادلات پیشرو کولموگروف و معادلات پسرو کولموگروف en:Kolmogorov equations صدق می‌کنند.

تکامل گذرا

احتمال تغییر حالت از حالت iام به حالت jام در n حرکت برابر است با

$p_{ij}^{(n)}=\Pr(X_{n}=j\mid X_{0}=i)\,$

این احتمال در یک حرکت برابر است با

$p_{ij}=\Pr(X_{1}=j\mid X_{0}=i).\,$

برای یک زنجیره مارکوف یکنواخت در زمان

$p_{ij}^{(n)}=\Pr(X_{k+n}=j\mid X_{k}=i)\,$

و

$p_{ij}=\Pr(X_{k+1}=j\mid X_{k}=i)\,$

توجه کنید که برای یک زنجیره مارکوف یکنواخت در زمان، احتمال تغییر حالت از حالت iام به حالت jام در n حرکت معادل است با درایهٔ (i,j) ام ماتریس احتمال انتقال وقتی این ماتریس n بار در خودش ضرب شده‌است:

$p_{ij}^{(n)}=[P^{n}]_{ij}$

در حرکت‌های n تایی احتمالات به‌دست آمده برابری چپمن-کولموگروف را ارضا می‌کنند. پس برای هر k که ۰ <n> k داریم

$p_{ij}^{(n)}=\sum _{r\in S}p_{ir}^{(k)}p_{rj}^{(n-k)}$

در این رابطه S فضای حالت زنجیره مارکوف است. توزیع حاشیه ای (Pr(X_n = x مربوط به حرکت nام است. توزیع اولیه برابر است با (Pr(X_۰ = x. تعمیم یافته این توزیع برای حرکت‌های بعدی به شکل

$\Pr(X_{n}=j)=\sum _{r\in S}p_{rj}\Pr(X_{n-1}=r)=\sum _{r\in S}p_{rj}^{(n)}\Pr(X_{0}=r).$

نمایش داده می‌شود که در آن n زیروند است و نه توان.

رده‌بندی حالت‌های یک زنجیر مارکوف

تقلیل‌پذیری

حالت jام را قابل دسترسی از حالت iام می‌نامند (i → j) اگر در سیستمی که از حالت iام شروع شود با احتمال غیر ۰ در نهایت به حالت jام برسد. در واقع اگر عدد صحیح n ≥ ۰ وجود داشته باشد که

$\Pr(X_{n}=j|X_{0}=i)=p_{ij}^{(n)}>0.\,$

تساوی 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 باشد. به زبان دیگر دوره تناوب یک حالت برابر است با

$k=\operatorname {gcd} \{n:\Pr(X_{n}=i|X_{0}=i)>0\}$

که در آن gcd بزرگترین مقسوم علیه مشترک است. اگر یک حالت دوره تناوب k داشته باشد ممکن است نتوان به این حالت با k حرکت رسید. به‌طور مثال اگر بتوان به حالت i در {۶, ۸, ۱۰, ۱۲, ...} حرکت بازگشت، در این صورت دوره تناوب برابر ۲ خواهد بود حتی اگر ۲ در مقادیر ذکر شده نباشد. اگر k = ۱ باشد، در این صورت به حالت مد نظر غیر متناوب می‌گویند و بازگشت به حالت i در حرکت‌های غیر منظم انجام خواهد گرفت. در غیر این صورت (k > 1)، حالت iدارای دوره تناوب k و متناوب می‌باشد.

بازگشت‌پذیری

فرض کنید f_i احتمال این پیشامد باشد که زنجیر با شروع از وضعیت i بعد از تعداد متناهی تغییر وضعیت به i برگردد. به وضوح $f_{i}=\sum _{n=1}^{\infty }f_{ii}^{n}\,$. اگر $f_{i}=1$ در این صورت حالت i را بازگشتی یا پایا می‌گوییم. به این ترتیب هر بار که زنجیر در حالت i قرار می‌گیرد فرایند به‌طور احتمالی حرکت خود را از سر شروع می‌کند، لذا اولین بازگشت به i مستلزم بازگشت دوم به i، و الی آخر است؛ بنابراین اگر i حالت بازگشتی باشد، فرایند با احتمال ۱ بینهایت بار به i برمی‌گردد و احتمال اولین بازگشت به این حالت در زمان متناهی برابر ۱ است. اگر امید ریاضی تعداد تغییر وضعیت‌ها تا بازگشت مجدد به i متناهی باشد به i بازگشتی مثبت و در غیر این صورت بازگشتی پوچ می‌گوییم.

حالت i را گذرا می‌نامند هرگاه $f_{i}<1$، به این معنی که اگر سیستم از حالت i شروع به کار کند، احتمال این که دیگر به این حالت بازنگردد غیر صفر است. برای حالت گذرای i احتمال این که فرایند با شروع از i دقیقاً بعد از n بار به آن بازگردد برابر است با$(f_{i})^{n}(1-f_{i})$. پس تعداد بازگشت‌ها به i متغیر تصادفی با پارامتر $1-f_{i}$ می‌باشد، در نتیجه تعداد بازگشت‌ها بینهایت نمی‌شود.

با در نظر گرفتن متغیر تصادفی T_i، زمان اولین بازگشت به حالت i، داریم:

$T_{i}=\inf\{n\geq 1:X_{n}=i|X_{0}=i\}.$

عدد $f_{ii}^{(n)}=\Pr(T_{i}=n)$ احتمال بازگشت سیستم به حالت i برای اولین بار در حرکت nام است. در نتیجه حالت i گذرا است اگر

$\Pr(T_{i}<{\infty })=\sum _{n=1}^{\infty }f_{ii}^{(n)}<1$

متوسط زمان بازگشت

اگر زمان اولین بازگشت به حالت i با احتمال ۱ متناهی باشد، نمی‌توان نتیجه گرفت که امید ریاضی این زمان متناهی است. امید ریاضی زمان بازگشت به حالت i همان متوسط زمان بازگشت است که از رابطه

$M_{i}=E[T_{i}]=\sum _{n=1}^{\infty }n\cdot f_{ii}^{(n)}.\,$

محاسبه می‌شود.

متوسط تعداد بازگشت‌ها

می‌توان نشان داد که حالت i پایا است اگر و تنها اگر متوسط تعداد بازگشت‌ها به این حالت نامتناهی باشد. یعنی

$\sum _{n=0}^{\infty }p_{ii}^{(n)}=\infty .$

چند قضیه مهم

• اگر i گذرا باشد، زنجیره متناهی بار به i بازمی‌گردد.
• هر زنجیر مارکوف با فضای حالت متناهی حداقل یک حالت بازگشتی دارد
• بازگشتی بودن یک خاصیت رده‌ای است یعنی اگر i بازگشتی باشد و با j در ارتباط باشد، آنگاه j نیز بازگشتی است.
• گذرا بودن یک خاصیت رده‌ای است یعنی اگر i گذرا باشد و با j در ارتباط باشد، آنگاه j نیز گذرا است.
• در هر زنجیر مارکوف تقلیل‌ناپذیر یا تمام حالت‌ها گذرا یا تمام آن‌ها بازگشتی هستند. در هر زنجیر مارکوف تقلیل‌پذیر، عناصر هر رده یا همه گذرا یا همه بازگشتی هستند. در حالت اول رده را رده گذرا و در حالت دوم رده بازگشتی می‌گوییم.
• هر زنجیر مارکوف تقلیل‌ناپذیر متناهی، بازگشتی است.
• اگر در زنجیره مارکوف با فضای حالت متناهی بازگشتی باشد، در این صورت حتماً بازگشتی مثبت است.

حالت‌های مانا

حالت i را جذب‌کننده یا مانا می‌نامند اگر با ورود به این حالت خروج از آن غیرممکن باشد. در نتیجه حالت i مانا است اگر و تنها اگر

$p_{ii}=1{\text{ and }}p_{ij}=0{\text{ for }}i\not =j.$

اگر هر حالت در یک سیستم به حالت مانایی برسد زنجیره مارکوف را زنجیره مارکوف مانا می‌نامند.

زنجیره ارگودیک و زنجیره باقاعده

یک زنجیره مارکوف ارگودیک است ا اگر بتوان با تعدادی حرکت از هر حالتی به حالت دیگر رسید. زنجیره ارگودیک زنجیره تقلیل‌ناپذیر نیز نامیده می‌شود. زنجیره‌ای که هم تقلیل‌ناپذیر باشد و هم غیر متناوب، زنجیره باقاعده (regular) نامیده می‌شود. به عبارت دیگر زنجیره‌ای با قاعده است که تقلیل‌ناپذیر باشد و هر حالت آن نامتناوب و بازگشتی مثبت باشد. در زنجیره باقاعده n ای وجود دارد که اگر ماتریس انتقال حالت به توان n برسد تمام درایه‌های آن مثبت خواهند بود. بدین معنا که با n حرکت می‌توان از هر حالتی به حالت دیگر رسید.

متوسط زمان اصابت

در یک زنجیره ارگودیک زمان اولین بار رسیدن یا اصابت به حالت j در حالی که زنجیر مارکوف در حالت i بوده‌است، زمان اصابت از i به j نامیده می‌شود. زمان اصابت با متغیر تصادفی $T_{ij}$ به صورت زیر توصیف می‌شود:

$T_{ij}=\inf\{n\geq 1:X_{n}=j|X_{0}=i\}.$

متوسط زمان اصابت از i به j، یعنی $H_{ij}=E[T_{ij}]$، از رابطهٔ بازگشتی زیر به‌دست می‌آید:

$H_{ij}=\sum _{r\in S}p_{ir}H_{rj}$

تجزیه و تحلیل توزیع ثابت و محدود کردن توزیع‌ها

برای یک زنجیر یکنواخت در زمان، بردار ${\boldsymbol {\pi }}$ یک «توزیع ثابت» (یا ایستا) نامیده می‌شود اگر $\pi _{j}$‌ها نامنفی و جمع آن‌ها برابر ۱ شود و نیز در رابطه زیر صدق کنند:

$\pi _{j}=\sum _{i\in S}\pi _{i}p_{ij}.$

یک زنجیره ارگودیک یک توزیع ثابت دارد اگر و فقط اگر همه حالت‌های آن مثبت باشند در این صورت π یکتاست و مربوط به زمان بازگشت مورد انتظار است:

$\pi _{j}={\frac {1}{M_{j}}}.\,$

اگر زنجیره باقاعده (غیر تقلیل پذیر و غیر متناوب) باشد آن گاه برای هر i و j داریم:

$\lim _{n\rightarrow \infty }p_{ij}^{(n)}={\frac {1}{M_{j}}}.$

لازم است ذکر شود که هیچ شرطی روی نقطه شروع توزیع وجود ندارد یعنی زنجیره صرف نظر از نقطه شروع به توزیع ثابت میل می‌کند. این π «توزیع تعادل» زنجیره نامیده می‌شود. اگر زنجیره بیش از یک کلاس مرتبط بسته داشته باشد توزیع ثابت آن یکتا نخواهد بود. زنجیره غیر یکنواخت در زمان نیز می‌تواند توزیع تعادل داشته باشد.

در هر صورت اگر حالت j ام غیر متناوب باشد آن گاه:

$\lim _{n\rightarrow \infty }p_{jj}^{(n)}={\frac {1}{M_{j}}}$

و برای هر حالت i دیگر اگر f_ij احتمال این باشد که زنجیره در حالت j قرار گیرد در صورتی که شروع زنجیره از حالت i باشد خواهیم داشت:

$\lim _{n\rightarrow \infty }p_{ij}^{(n)}={\frac {f_{ij}}{M_{j}}}.$

اگر حالت i متناوب باشد با دوره تناوب k > 1 آنگاه حد

$\lim _{n\rightarrow \infty }p_{ii}^{(n)}$

وجود ندارد و نیز حد

$\lim _{n\rightarrow \infty }p_{ii}^{(kn+r)}$

برای هر r صحیح وجود ندارد.

زنجیره وارون پذیر

یک زنجیره مارکوف وارون پذیر نامیده می‌شود اگر یک توزیع احتمال $\pi$ بر روی حالتها وجود داشته باشد به‌طوری‌که برای تمام زمان‌های n و حالتهای i و j رابطهٔ زیر برقرار باشد:

$\pi _{i}\Pr(X_{n+1}=j\mid X_{n}=i)=\pi _{j}\Pr(X_{n+1}=i\mid X_{n}=j)$

برای زنجیره‌های یکنواخت در زمان رابطهٔ بالا به صورت سادهٔ زیر نوشته می‌شود:

$\pi _{i}p_{ij}=\pi _{j}p_{ji}\,.$

توزیع احتمال $\pi$ در رابطهٔ بالا همان توزیع ثابت در زنجیره‌های ارگودیک می‌باشد.

کاربردها

فیزیک

سیستم‌های مارکوفی در ترمودینامیک و مکانیک آماری بسیار ظاهر می‌شوند، جایی که احتمال برای نشان دادن ویژگی‌های ناشناخته سیستم به کار می‌رود، اگر بتوان فرض کرد که دینامیک مستقل از زمان است و احتیاجی به بررسی پیشینه تاریخی آن نیست. مسیرها، در فرمول انتگرال مسیر مکانیک کوانتومی، زنجیره مارکوف هستند. همچنین زنجیر مارکوف در شبیه‌سازی شبک‌های QCD استفاده می‌شود.

بهداشت عمومی

در بهداشت عمومی از زنجیره مارکوف برای مدل‌سازی ریاضی شیوع بیماری در آینده استفاده می شود. در این مدلها هر شخص با حالت فعلی (داشتن یا نداشتن یک بیماری و عامل ریسک) شناخته می شود. مدل مارکوف شیوع بیماری در آینده را با استفاده از ماتریس گذار و بردار وضعیت فعلی پیش‌بینی می کند. چنین ماتریس گذاری شامل احتمال تغییر از حالت فعلی به حالت محتمل بعدی است. در دنیای واقعی چنین مدلهای مارکوفی اغلب حالتهای زیادی دارند زیرا عوامل ریسکی مثل سیگار کشیدن و چاقی با بیماریهای مزمن زیادی در ارتباط هستند.

علم اطلاعات

زنجیره مارکوف در نظریه اطلاعات کاربرد دارد. مقاله معروف کلود شانون در سال ۱۹۴۸ با «نظریه ریاضی ارتباطات» که پایه‌گذار نظریه اطلاعات شد با معرفی آنتروپی از طریق مدل‌سازی مارکوف از زبان انگلیسی آغاز می‌شود. چنین مدل‌های ایده‌آلی بسیاری از قواعد آماری سیستم را به دست می‌دهند. حتی بدون داشتن ساختار کامل سیستم این گونه مدل‌سازی‌ها فشرده سازی مؤثر داده‌ها را ممکن می‌سازند.

زنجیره‌های مارکوف پایه و اساس مدل پنهان مارکوف است که این مدل یکی از ابزارهای مهم در زمینه‌های گوناگون مثل شبکه‌های تلفن (برای تصحیح خطا)، تشخیص گفتار و هم چنین بیوانفورماتیک است.

نظریه صف

زنجیره‌های مارکوف اساس رفتار تحلیلی صف ها(نظریه صف) می‌باشد و این امر وجود آن‌ها را برای بهینه‌سازی عملکرد شبکه‌های مخابراتی حیاتی می‌سازد. جایی که پیام‌ها برای منابع محدود (مانند پهنای باند) رقابت می‌کنند. مدل‌های صف بندی بسیاری از زنجیره مارکوف زمان پیوسته استفاده می‌کنند. برای مثال، یک صف M / M / 1 یک CTMC بر روی عدد صحیح غیر منفی است که در آن انتقال از i به i + 1 بر اساس یک فرایند پوآسون با نرخ λ رخ می‌دهد و ورود کار را توصیف می‌کند، در حالی که انتقال از i به i - 1 (برای i> 1) در نرخ μ اتفاق می‌افتد (بار خدمات شغلی از توزیع نمایی پیروی می‌کنند) و خدمات کامل یا همان خروج از صف را نشان می‌دهد.

نمایش سادهٔ شبکه‌ای از چند صفحه که با رتبه صفحه ارزیابی شده‌اند.

کاربرد اینترنتی

یکی از نتایج جالب از زنجیرهٔ مارکوف این است که با افزایش طول زنجیر (افزایش تعداد تغییر حالات)، احتمال رسیدن به یک حالت خاص به عددی ثابت همگرا خواهد شد. اکنون تمام شبکه جهانی وب را یک زنجیره مارکوف در نظر بگیرید که در آن هر صفحه یک حالت و پیوند میان آنان احتمال هر تغییر حالت را مشخص می‌کند. این نظریه می‌گوید مستقل از صفحه‌ای که از آن شروع کرده‌ایم، پس از مدتی طولانی گشتن در وب احتمال رسیدن به صفحه‌ای خاص مقدار ثابتی دارد. با این مدل‌سازی می‌توان گفت هر چه احتمال رسیدن به یک صفحه بیشتر باشد، آن صفحه از اهمیت بالاتری برخوردار است.

رتبه صفحه (Page Rank)، برای یک صفحهٔ وب که گوگل نیز از آن استفاده کرده‌است، توسط یک زنجیره مارکوف تعریف شده‌است. همچنین مدل مارکوف برای تحلیل رفتارهای وب کاربران و سیر حرکت آن‌ها میان صفحات استفاده شده‌است. انتقال کاربر به یک صفحه وب خاص از طریق یک لینک می‌تواند با استفاده از مدل‌های مارکوف مرتبه اول یا دوم مدل شود و برای پیش‌بینی‌های مربوط به حرکات آینده و شخصی‌سازی وب برای کاربر مورد استفاده قرار گیرد.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Markov chain». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۶ ژوئیهٔ ۲۰۱۲.

پیوند به بیرون

• تکنیک‌های درک شبیه‌سازی‌های رایانه: تجزیه و تحلیل زنجیره مارکوف
• فصل زنجیره مارکوف در کتاب احتمال مقدماتی انجمن ریاضی آمریکا
• ساختار کلاس در ریاضی سیاره
• کاربرد زنجیر مارکوف
• متن تولیدی: بخش ۱۵٫۳ از مرواریدهای برنامه‌نویسی
• تولید متن کاربران آنلاین حاضر در سایت: راه رفتن تصادفی مارکوف v۱٫۱