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

این صفحه شامل مثال‌هایی از زنجیره مارکوف است.

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

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

گام‌های تصادفی متمایل به مرکز

یک حرکت تصادفی روی تعدادی خط را در نظر بگیرید، موقعیت کنونی (که x نامیده می نامیم) با احتمالات زیر می‌تواند به +۱ (به راست) یا -۱(به چپ) تغییر کند:

$P_{move~left}={\tfrac {1}{2}}+{\tfrac {1}{2}}\left({\tfrac {x}{c+|x|}}\right)$

$P_{move~right}=1-P_{move~left}$

(c یک عدد ثابت بزرگتر از ۰ است)

به عنوان مثال اگر عدد ثابت c برابر ۱ باشد، احتمال حرکت به چپ از موقعیت x=-۲,-۱٬۰٬۱٬۲ به ترتیب برابرست با: ${\tfrac {1}{6}},{\tfrac {1}{4}},{\tfrac {1}{2}},{\tfrac {3}{4}},{\tfrac {5}{6}}$.

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

یک مدل آب و هوایی بسیار ساده

احتمال وضعیت آب و هوایی که آب و هوا در طول روز را نشان می‌دهد و هم به صورت بارانی و هم آفتابی مدل می‌شود، توسط یک ماتریس انتقال ارائه داده می‌شود.

$P={\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}$

ماتریس P یک مدل آب و هوایی را نشان می‌دهد بطوری‌که روز بعد یک روز آفتابی، با احتمال %۹۰ آفتابی است و روز بعد یک روز بارانی، با احتمال %۵۰ آفتابی است. ستون‌ها و سطرها با آفتابی و بارانی برچسب‌گذاری می‌شوند.

(P)_{i j} احتمال این است که هوای امروز از نوع i باشد و فردا از نوع j باشد.

در نظر داشته باشید که حاصل جمع احتمالات سطر P برابر ۱ است.

پیش‌بینی آب و هوا

هوا در روز ۰ آفتابی تشخیص داده شده. که این توسط یک بردار که ورودی آفتابی %۱۰۰ است و بارانی %۰ است نمایش داده می‌شود.

$\mathbf {x} ^{(0)}={\begin{bmatrix}1&0\end{bmatrix}}$

آب و هوا در روز ۱ می‌تواند توسط به این صورت پیش‌بینی شود:

$\mathbf {x} ^{(1)}=\mathbf {x} ^{(0)}P={\begin{bmatrix}1&0\end{bmatrix}}{\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}={\begin{bmatrix}0.9&0.1\end{bmatrix}}$

بنابراین %۹۰ شانس این وجود دارد که روز ۱ آفتابی باشد.

آب و هوای روز ۲ به همین ترتیب پیش‌بینی می‌شود:

$\mathbf {x} ^{(2)}=\mathbf {x} ^{(1)}P=\mathbf {x} ^{(0)}P^{2}={\begin{bmatrix}1&0\end{bmatrix}}{\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}^{2}={\begin{bmatrix}0.86&0.14\end{bmatrix}}$

یا

$\mathbf {x} ^{(2)}=\mathbf {x} ^{(1)}P={\begin{bmatrix}0.9&0.1\end{bmatrix}}{\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}={\begin{bmatrix}0.86&0.14\end{bmatrix}}$

فرمول کلی به این صورت است:

$\mathbf {x} ^{(n)}=\mathbf {x} ^{(n-1)}P$

$\mathbf {x} ^{(n)}=\mathbf {x} ^{(0)}P^{n}$

حالت ثابت آب و هوا

در این مثال، پیش‌بینی هوا در روزهای دور از هم غلط از آب در می‌آید و متمایل به بردار حالت پایدار است. این بردار احتمال هوای آفتابی و بارانی را در همهٔ روزها نشان می‌دهد و مستقل از آب و هوای اولیه است.

بردار حالت ثابت به این صورت تعریف می‌شود: $\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}}$

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

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Examples of Markov chains». در دانشنامهٔ ویکی‌پدیای انگلیسی.

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

• Monopoly as a Markov chain