زنجیره‌های ناپیوسته مارکوف (Discrete Markov Chains)
تعداد بازدید: 4026
زمان مطالعه: 16 دقیقه
مقدمه
روش‌های تحلیلی متعددی برای ارزیابی قابلیت اطمینان سیستم‌های تعمیرناپذیر و همچنین تعمیرپذیر در وجود دارد. فرآیند تعمیرات برای سیستم‌های تعمیرپذیر لحظه‌ای و یا به عبارتی با زمانی کوتاه و قابل اغماض در مقایسه با زمان عملکرد سیستم مفروض گرفته شد. هرگاه چنین فرضی برای تحلیل و ارزیابی قابلیت اطمینان مناسب نباشد نیاز به روش‌های دیگری خواهیم داشت.
یکی از روش‌های مهمی که برای این مورد، مناسب است و به ویژه در سال‌های اخیر مورد توجه زیادی قرار گرفته است به نام روش مدلسازی مارکوف شناخته می‌شود. در منابع متعددی کاربرد زنجیره‌های مارکوف در تحلیل قابلیت اطمینان آورده شده است. روش مارکوف برای مدلسازی رفتار اتفاقی سیستم‌هایی کاربردپذیر است که به طور پیوسته و یا ناپیوسته نسبت به زمان و یا در فضای حالت در تغییرند. این تغییرات پیوسته و یا ناپیوسته اتفاقی را اصطلاحاً فرآیند اتفاقی می‌نامند. البته همه فرآیندهای اتفاقی را نمی‌توان توسط روش مقدماتی مارکوف مدلسازی کرد ولی می‌توان از روش‌های دیگری بر مبنای همین روش مقدماتی استفاده کرد.
برای این که بتوان روش مارکوف را به کار برد رفتار سیستم باید نمایانگر فقدان حافظه باشد، یعنی حالت و وضعیت آینده سیستم باید مستقل از وضعیت‌های گذشته، به جز آخرین وضعیت آن باشد. بنابراین رفتار اتفاقی آتی یک سیستم صرفاً باید بستگی به وضعیت حال آن داشته و هیچ‌گونه وابستگی به گذشته آن و یا چگونگی حصول وضعیت حال نداشته باشد. به عبارت دیگر رفتار سیستم باید در همه مقاطع زمانی یکسان و احتمال تبدیل وضعیت آن به وضعیت‌های دیگر همواره در همه زمان‌ها ثابت بماند. مفهوم فوق به بیان توزیع احتمال به معنای آهنگ ثابت وقوع خطر است و از این رو تابع‌های پواسون و نمایی برای این منظور مورد توجه می‌باشد. هرگاه احتمال تغییرات در فرآیندی تابع زمان باشد آن فرآیند را غیرمارکوفی می‌نامند.
به طور کلی در مدل‌های مارکوف، هم زمان و هم فضا به شکل پیوسته و یا ناپیوسته قابل تلقی است. در ارزیابی قابلیت اطمینان به طور اخص، معمولاً فضا را به عنوان تابع ناپیوسته ارائه می‌کنند زیرا موقعیت مکانی به صورت ناپیوسته هویت‌پذیر و مشخص کننده محل استقراری برای یک سیستم و اجزای آن است. در حالی که زمان، هم به صورت پیوسته و هم ناپیوسته می‌تواند منظور شود. حالت ناپیوسته به عنوان زنجیره مارکوف شناخته شده و موضوع بحث این پست است. حالت پیوسته با عنوان فرآیند شناخته می‌شود. اگرچه ممکن است فرآیند مارکوف مورد نظر خواننده باشد ولی برای مطالعه آن نیاز به حصول آشنایی با مفاهیم و روش‌هایی است که در این پست بیان می‌شود.
همچنین باید توجه شود که اگرچه روش مارکوف به ویژه در ارتباط با حل مسائل سیستم‌های تعمیرپذیر با مدت تعمیر طولانی مطرح شد ولی از این روش برای ارزیابی سیستم‌های تعمیرناپذیر هم می‌توان استفاده کرد. بنابراین برای امکان‌پذیری کاربرد روش مارکوف کافی است تا الزامات سه‌گانه زیر فراهم باشد:
1- سکون رفتار سیستم
2- فقدان حافظه فرآیندهای سیستم
3- هویت‌پذیری وضعیت و حالت‌های سیستم
مفاهیم کلی در مدلسازی (General Modelling Concepts)
مفاهیم پایه در مدلسازی مارکوف بر مبنای سیستم ساده به صورت شکل (1) نمایش‌پذیر است.
شکل 1
در این سیستم صرفاً دو حالت 1 و 2 شناسایی می‌شود. احتمال استمرار و یا تغییر هر حالت از سیستم در همه زمان‌ها ثابت و در شکل (1) نشان داده شده است.
این مورد یک زنجیره ناپیوسته مارکوف محسوب می‌شود زیرا هم رفتار سیستم ساکن است و هم تغییر حالت به نحو مشخص و در گام‌های منفصل صورت می‌گیرد.
تحلیل احتمالات را با استقرار سیستم در حالت 1 برای اولین دامنه زمانی آغاز می‌کنیم. سیستم می‌تواند با احتمال $\frac{1}{2}$ در حالت 1 باقی مانده و یا با احتمال $\frac{1}{2}$ به حالت 2 تغییر کند. توجه شود که جمع احتمال حالت‌ها همواره باید برابر یک شود و این اصلی است که مستقل از درجه پیچیدگی مسئله و یا تعداد طرق میسر برای تغییر حالت همواره برقرار می‌باشد. همچنین وقتی سیستم نشان داده شده در شکل (1) در حالت 2 قرار داشته باشد با احتمال $\frac{3}{4}$ در همین حالت باقی مانده و یا با احتمال $\frac{1}{4}$ به حالت 1 تغییر حالت خواهد داد.
رفتار این سیستم به سهولت توسط نمودار درختی مطابق شکل (2) نمایش‌پذیر است. در این شکل با شروع فرضی از حالت 1، و احتمال حالت‌های محتمل طی چهار مرحله یا چهار دامنه زمانی مورد بررسی قرار گرفته است. همان‌گونه که قبلاً برای نمودار درخت مطرح شد احتمال هر شاخه انشعاب از حالت‌ها از حاصلضرب احتمال مراحل آن شاخه به دست می‌آید.
شکل 2
احتمال استقرار در یک حالت معین پس از طی تعدادی از مراحل، با جمع احتمالات حالت در مرحله مورد نظر تعیین می‌شود. بدین ترتیب می‌توان جمع احتمال هر حالت را پس از طی مراحل، به دست آورده و در جدولی مانند جدول (1) انعکاس داد و به صورت ترسیمی مانند شکل (3) نشان داد. بدیهی است که در هر مرحله مجموع احتمالات حالت‌ها برابر یک می‌شود و این می‌تواند مبنایی برای آزمایش دقت محاسبات باشد. چنانچه ملاحظه می‌شود مجموع احتمالات حالت 1 پس از طی چهار مرحله برابر $\frac{{43}}{{128}}$ و متناظراً مجموع احتمالات حالت 2 در این مرحله برابر $\frac{{85}}{{128}}$ و مجموع احتمالات این دو حالت برابر یک است. نتایج ارائه شده در جدول (1) و یا شکل (3) نمایانگر رفتار گذرای سیستم و یا مقادیر احتمالات حالت‌ها در وابستگی به زمان می‌باشد. همان‌گونه که از شکل (3) ملاحظه می‌شود با افزایش تعداد مراحل، مقادیر احتمالات حالت‌ها تمایل به مقادیر حدی یا ثابتی می‌یابند. این ویژگی برای اکثر سیستم‌هایی که شرایط روش مارکوف را ارضاء نمایند صادق است. به مقادیر حدی احتمالات، مقادیر احتمالات مستقل از زمان نیز اطلاق می‌شود.
شکل 3
جدول 1
حالت سیستم در شروع (در مرحله 0) در اکثر مسائل ارزیابی قابلیت اطمینان مانند این مسئله معلوم است و منظور از بررسی، تعیین قابلیت اطمینان سیستم در روند گذشت زمان به سوی آینده است.
رفتار گذرای سیستم وابستگی زیادی به شرایط اولیه آن دارد و در اینجا نیز می‌توان گراف مشابهی برای وقتی که سیستم در مرحله صفر در حالت 2 استقرار داشته باشد ترسیم نمود. چنین ارزیابی از سیستم نتیجه مهم و جالبی به دست می‌دهد و آن این که مقادیر حدی احتمالات حالت‌ها کاملاً مستقل از شرایط اولیه است و در هر صورت همان مقادیر نشان داده شده در شکل (3) حاصل می‌شود. سیستم و یا فرآیندی با یک چنین ویژگی را اصطلاحاً ارگودیک می‌نامند و باید توجه شود که همه سیستم‌ها دارای این ویژگی نیستند. در برخی از سیستم‌ها حالت‌هایی وجود دارد که در صورت وقوع، امکان خروج از آن‌ها میسر نیست. این‌گونه سیستم‌ها را غیرارگودیک و چنین حالت‌هایی را حالت‌های ماندگار (Absorbing States) می‌نامند و در ادامه مورد بررسی قرار می‌گیرد.
اگرچه مقادیر حدی احتمالات حالت‌ها در یک سیستم ارگودیک مستقل از شرایط اولیه است ولی روند تغییرات در حصول مقادیر حدی به شرایط اولیه بستگی داشته و وابستگی زیادی به مقادیر احتمالات تغییر حالت دارد.
روش نمودار درختی، شیوه مفیدی در نمایش مفاهیم زنجیره‌های مارکوف است ولی برای سیستم‌های بزرگ و همچنین تعداد مراحل زیاد حتی برای سیستم‌های کوچک اجراناپذیر می‌باشد و لذا نیاز به روش‌های دیگری است که در دنباله این پست مورد بحث قرار می‌گیرد.
مفاهیم کلی در مدلسازی (General Modelling Concepts)
هرگاه کاربرد روش مبنا برای تحلیل سیستم‌ها، عملاً میسر نباشد شیوه حل ماتریسی معمولاً مورد توجه قرار می‌گیرد. تحلیل قابلیت اطمینان سیستم‌ها نیز از این امر مستثناء نیست. برای کاربرد شیوه ماتریسی در ارزیابی قابلیت اطمینان سیستم‌ها در ابتدا باید ماتریسی نمایانگر احتمالات تغییر گذرا از یک حالت به حالت دیگر سیستم را برای یک مرحله زمانی تشکیل داد. مجدداً با ارجاع به سیستم ارائه شده در شکل (1)، احتمال تغییر حالت‌های سیستم را در نظر گرفته و در قالب ماتریس به صورت زیر نمایش می‌دهیم:
رابطه (1)
$$P = \left[ {\begin{array}{*{20}{c}}
{{P_{11}}}&{{P_{12}}}\\
{{P_{21}}}&{{P_{22}}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{\frac{1}{2}}&{\frac{1}{2}}\\
{\frac{1}{4}}&{\frac{3}{4}}
\end{array}} \right]$$
که در آن ${P_{ij}}$ عبارت از احتمال تغییر سیستم به حالت پس از یک مرحله زمانی است مشروط بر آن که در ابتدای مرحله در حالت قرار داشته باشد. با اعمال این مفهوم برای سیستم شکل (1) در اولین مرحله زمانی خواهیم داشت:
$${P_{11}} = \frac{1}{2}\;\;,\;\;{P_{12}} = \frac{1}{2}\;\;,\;\;{P_{21}} = \frac{1}{4}\;\;,\;\;{P_{22}} = \frac{3}{4}$$
تعریف فوق برای ${P_{ij}}$ نمایانگر آن است که موقعیت ردیفی ماتریس مبیّن وضعیتی است که تغییر از آن شروع می‌شود و موقعیت ستونی ماتریس مبیّن وضعیتی است که تغییر به آن ختم می‌شود. بنابراین ماتریس فوق برای یک سیستم $n$ حالتی همواره یک ماتریس مربع به شکل در پی آمده می‌شود:
رابطه (2)
$$\begin{array}{l}
\;\;\;\;\;\;\;\;\;\;\begin{array}{*{20}{c}}
{1\;\;\;\;}&{2\;}&{ \cdots \;}&n
\end{array}\\
P = \begin{array}{*{20}{c}}
1\\
2\\
\vdots \\
n
\end{array}\left[ {\begin{array}{*{20}{c}}
{{P_{11}}}&{{P_{12}}}& \cdots &{{P_{1n}}}\\
{{P_{21}}}&{{P_{22}}}& \cdots &{{P_{2n}}}\\
\vdots & \vdots & \vdots & \vdots \\
{{P_{n1}}}&{{P_{n2}}}& \cdots &{{P_{nn}}}
\end{array}} \right]
\end{array}$$
این ماتریس به نام ماتریس احتمالات تغییر حالت اتفاقی سیستم شناخته می‌شود زیرا که مبیّن چنین محتوای مفهومی است. باید توجه شود که مجموع احتمالات هر ردیف از ماتریس برابر یک می‌شود.
تعیین احتمالات وابسته به زمان (Time Dependent Probability Evaluation)
برای ارائه روش استفاده از ماتریس احتمالات تغییر حالت اتفاقی در تعیین رفتار گذرای یک سیستم مجدداً سیستم نشان داده شده در شکل (1) را در نظر بگیرید. با ضرب کردن این ماتریس در خودش می‌توان به ماتریس مربع جدیدی رسید که اجزای آن مبیّن احتمالات حالت‌های سیستم پس از طی یک مرحله زمانی است بنابراین:
رابطه (3)
$$\begin{array}{l}
{P^2} = \left[ {\begin{array}{*{20}{c}}
{{P_{11}}}&{{P_{12}}}\\
{{P_{21}}}&{{P_{22}}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{P_{11}}}&{{P_{12}}}\\
{{P_{21}}}&{{P_{22}}}
\end{array}} \right]\\
\;\;\;\; = \left[ {\begin{array}{*{20}{c}}
{({P_{11}}{P_{11}} + {P_{12}}{P_{21}})}&{({P_{11}}{P_{12}} + {P_{12}}{P_{22}})}\\
{({P_{21}}{P_{11}} + {P_{22}}{P_{11}})}&{({P_{21}}{P_{12}} + {P_{22}}{P_{22}})}
\end{array}} \right]
\end{array}$$
که با منظور کردن مقادیر ${P_{ij}}$ از معادله (1) خواهیم داشت:
رابطه (4)
$${P^2} = \left[ {\begin{array}{*{20}{c}}
{\frac{3}{8}}&{\frac{5}{8}}\\
{\frac{5}{{16}}}&{\frac{{11}}{{16}}}
\end{array}} \right]$$
که در این ماتریس، اولین جزء ردیف 1 $(\frac{3}{8})$ نمایانگر احتمال باقی ماندن سیستم در حالت 1 پس از یک مرحله زمانی است و متناظراً دومین جزء ردیف 1 $(\frac{5}{8})$ نمایانگر احتمال تغییر سیستم از حالت 1 به حالت 2 پس از یک مرحله زمانی می‌باشد. ردیف دوم ماتریس نیز به نحو مشابهی تفسیرپذیر است.
مقادیر به دست آمده در ردیف 1 ماتریس با نتایج منعکس در جدول (1) تطبیق‌پذیر است و در صورتی که مطالعه احتمالات تغییر حالت با شروع از حالت 2 صورت می‌گرفت، تطبیقی با مقادیر به دست آمده در ردیف 2 ماتریس در اختیار می‌بود. بنابراین اجزای ماتریس ${P^2}$ احتمالات همه حالت‌های یک سیستم را در مرحله دوم برای شروع از هر دو حالت 1 و یا 2 در اختیار می‌گذارد.
اصول ارائه شده فوق برای هر توانی از $P$ تعمیم‌پذیر است و بنابراین اجزای ماتریس $P_{ij}^n$ نمایانگر احتمالات حالت $j$ در مرحله زمانی $n$ ام می‌باشد. از آنجایی که معمولاً حالت سیستم در شروع یا به عبارتی در مقطع زمانی صفر یقیناً مشخص است، احتمال آن حالت برابر با یک و احتمال سایر حالت‌ها برابر با صفر می‌باشد. مع‌الوصف در صورتی که حالت یک سیستم در شروع با درجه‌ای از قطعیت مطرح باشد، ماتریس ${P^n}$ باید با ضریبی به نام بردار احتمال شرایط اولیه $P(0)$، که خود نمایانگر احتمال حالت اولیه است مورد ارزیابی قرار گیرد. بدیهی است که جمع احتمالات مندرج در این بردار برابر یک می‌شود. هرگاه حالت شروع برای سیستم دو حالتی شکل (1)، حالت 1 به طور قطعی مشخص شده باشد بردار احتمال شرایط اولیه به صورت زیر درمی‌آید:
رابطه (4-الف)
$$\begin{array}{l}
\;\;\;\;\;\;\;\;\;\;\;1\;\;\;\;2\\
P(0) = \left[ {\begin{array}{*{20}{c}}
1&0
\end{array}} \right]
\end{array}$$
و چون احتمال حالت 1 برابر واحد است احتمال حالت 2 برابر صفر می‌شود. حال در صورتی که احتمال یکسانی برای وضعیت‌های دوگانه سیستم در شروع مطرح باشد خواهیم داشت:
رابطه (4-ب)
$$\begin{array}{l}
\;\;\;\;\;\;\;\;\;\;\,\;\;1\;\;\;\;2\\
P(0) = \left[ {\begin{array}{*{20}{c}}
{\frac{1}{2}}&{\frac{1}{2}}
\end{array}} \right]
\end{array}$$
حال به بررسی نتیجه تأثیر ضریب برداری در ماتریس احتمالات حالت‌ها در مرحله دوم پرداخته می‌شود. در ابتدا حالت 1 به عنوان حالت قطعی سیستم در شروع منظور می‌شود:
رابطه (5-الف)
$$\begin{array}{l}
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\,\;\;\;\,\;\;\;\;\,\,\,\,\,\,\;\;\;\,\;\;\;1\;\;\;\;2\\
P(2) = P(0){P^2} = \left[ {\begin{array}{*{20}{c}}
1&0
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{\frac{3}{8}}&{\frac{5}{8}}\\
{\frac{5}{{16}}}&{\frac{{11}}{{16}}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{\frac{3}{8}}&{\frac{5}{8}}
\end{array}} \right]
\end{array}$$
که نتیجه‌ای در انطباق با جدول (1) به دست می‌آید.
اما تحت شرایطی که احتمال یکسانی برای شروع سیستم از حالت‌های 1 و 2 مطرح باشد خواهیم داشت:
رابطه (5-ب)
$$P(2) = P(0){P^2} = \left[ {\begin{array}{*{20}{c}}
{\frac{1}{2}}&{\frac{1}{2}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{\frac{3}{8}}&{\frac{5}{8}}\\
{\frac{5}{{16}}}&{\frac{{11}}{{16}}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{\frac{{11}}{{32}}}&{\frac{{21}}{{32}}}
\end{array}} \right]$$
اصول فوق برای هر تعداد مرحله از تغییرات سیستم قابل گسترش و تعمیم‌پذیر است لذا:
رابطه (5-ج)
$$P(n) = P(0){P^n}$$
از بحث فوق نتیجه می‌شود که با ضرب ماتریسی می‌توان احتمال هر حالت از سیستم را در هر مرحله زمانی برای هر احتمالی از حالت شروع سیستم به دست آورد و در صورتی که به اندازه کافی بزرگ باشد مقادیر احتمال حدی از حالت‌های سیستم حاصل می‌شود.
تعیین احتمالات حدی حالت‌ها (Limiting State Probability Evaluation)
احتمالات حدی حالت‌های یک سیستم ارگودیک با کاربرد شیوه ماتریسی تعیین‌پذیر است، و هرگاه رفتار گذرای سیستم نیز مورد نظر باشد استفاده از این شیوه معقول می‌باشد ولی اگر صرفاً تعیین احتمالات حدی حالت‌های سیستم مورد نظر باشد شیوه ضرب ماتریسی خسته کننده و وقت‌گیر خواهد بود و به جای آن شیوه مؤثر دیگری با شرح در پی آمده توصیه می‌شود.
با این استدلال که با ادامه عمل ضرب ماتریسی سرانجام شرایط حدی حاصل می‌شود و تغییری در مقادیر اجزای ماتریس که نمایانگر احتمالات حدی حالت‌های سیستم می‌باشد رخ نمی‌دهد؛ هرگاه $\alpha $ نمایانگر بردار احتمالات حدی باشد و $P$ ماتریس احتمالات تغییر حالت اتفاقی، در این صورت خواهیم داشت:
رابطه (6)
$$\alpha P = \alpha $$
هرگاه این اصل برای سیستم ساده دو حالتی شکل (1) به کار برود با معرفی ${P_1}$ و ${P_2}$ به عنوان احتمالات حدی حالت‌های 1 و 2 خواهیم داشت:
$$\begin{array}{l}
\left[ {\begin{array}{*{20}{c}}
{{P_1}}&{{P_2}}
\end{array}} \right]P = \left[ {\begin{array}{*{20}{c}}
{{P_1}}&{{P_2}}
\end{array}} \right]\\
\left[ {\begin{array}{*{20}{c}}
{{P_1}}&{{P_2}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{\frac{1}{2}}&{\frac{1}{2}}\\
{\frac{1}{4}}&{\frac{3}{4}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{{P_1}}&{{P_2}}
\end{array}} \right]
\end{array}$$
رابطه (7)
$$\left\{ {\begin{array}{*{20}{c}}
{\frac{1}{2}{P_1} + \frac{1}{4}{P_2} = {P_1}}\\
{\frac{1}{2}{P_1} + \frac{3}{4}{P_2} = {P_2}}
\end{array}} \right.$$
رابطه (8)
$$\left\{ {\begin{array}{*{20}{c}}
{ - \frac{1}{2}{P_1} + \frac{1}{4}{P_2} = 0}\\
{\frac{1}{2}{P_1} - \frac{1}{4}{P_2} = 0}
\end{array}} \right.$$
بدیهی است که دستگاه معادلات فوق شامل معادلات متناظر است و برای تعیین مجهولات ${P_1}$ و ${P_2}$ نیاز به معادله دیگری مستقل از معادلات فوق می‌باشد. این معادله تکمیل کننده عبارت است از:
رابطه (9)
$${P_1} + {P_2} = 1$$
دستگاه معادلات سیستم با هر بزرگی، همواره دارای یک معادله مانند دیگر معادلات می‌شود و همواره نیاز به معادله (9) در تکمیل دستگاه معادلات، برای یافتن مجهولات می‌باشد. دستگاه معادلات سیستم دو حالتی به شکل ماتریسی در پی آمده نمایش‌پذیر است:
رابطه (10)
$$\left[ {\begin{array}{*{20}{c}}
{ - \frac{1}{2}}&{\frac{1}{4}}\\
1&1
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{P_1}}\\
{{P_2}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
0\\
1
\end{array}} \right]$$
که به صورت $AX = b$ نمایش‌پذیر و برای مجهول مورد نظر معادله $X = {A^{ – 1}}b$ تعیین کننده است.
${A^{ – 1}}$ را اصطلاحاً وارون ماتریس $A$ می‌نامند. وارون یک ماتریس طبق قاعده کرامر به سهولت محاسبه‌پذیر است. این قاعده به علت خطای محاسبات برای محاسبه رایانه‌ای مناسب نیست و برای این موارد شیوه‌های دیگری در اختیار می‌باشد. در اینجا با کاربرد قاعده کرامر داریم:
$$\begin{array}{l}
{P_1} = \frac{{(1 \times 0) - (\frac{1}{4} \times 1)}}{{\left| {\begin{array}{*{20}{c}}
{ - \frac{1}{2}}&{\frac{1}{4}}\\
1&1
\end{array}} \right|}} = \frac{{ - \frac{1}{4}}}{{ - \frac{3}{4}}} = 0.333\\
{P_2} = \frac{{( - \frac{1}{2} \times 1) - (1 \times 0)}}{{ - \frac{3}{4}}} = \frac{{ - \frac{1}{2}}}{{ - \frac{3}{4}}} = 0.667
\end{array}$$
یعنی نهایتاً مقادیری برابر با مقادیر مشخصه نشان داده شده در شکل (3) حاصل می‌شود.
حالت‌های ماندگار (Absorbing States)
حالت ماندگار به حالتی اطلاق می‌شود که با وقوع آن امکان خروج سیستم از آن حالت میسر نباشد، مگر آن که مأموریت جدیدی با شروع از یکی از حالت‌های غیرماندگار آغاز شود. چنین حالت‌هایی برای سیستم ویژه انجام مأموریت، شکست فاجعه‌آمیز تلقی می‌شود و باید احتمال وقوع آن را به حداقل ممکنه رساند تا عملکرد مطمئن‌تری برای سیستم فراهم شود. در چنین مواردی یکی از الزامات قابلیت اطمینان، دستیابی به تعداد قابل قبولی از مراحل زمانی است که سیستم را از ورود به حالت ماندگار بازدارد.
اصول حاکم در این سیستم‌ها در ارتباط با تحلیل سیستم‌های تعمیرپذیر مطرح می‌باشد و منظور از آن تعیین تعداد دفعات متوسطی است که سیستم قبل از ورود به حالت نامطلوب به نحو مناسبی عمل نماید. در این مورد البته حالت نامطلوب یک حالت ماندگار نیست و با انجام تعمیرات می‌توان سیستم را از آن حالت خارج کرد ولی عملاً آن را به عنوان حالت ماندگار تلقی می‌نمایند تا با توسل به این روش‌ها تعداد دفعات مراحل زمانی، در احتراز از وقوع آن حالت ارزیابی شود.
می‌شود که هرگاه سیستم از حالت شماره 1 شروع نماید، احتمال تداوم این حالت با افزایش دفعات مراحل زمانی، کاهش می‌یابد و سرانجام حالت 2 برای سیستم حاصل خواهد شد. از نظر ریاضی نیز:
رابطه (11)
$$\mathop {\lim }\limits_{n \to \infty } {(\frac{1}{2})^n} = 0$$
که در آن $n$ تعداد مراحل زمانی و $(\frac{1}{2})$ احتمال باقی ماندن در حالت 1 می‌باشد. هرگاه حالت 2 به عنوان حالت ماندگار در نظر گرفته شود نهایتاً سیستم به این حالت در خواهد آمد و مسئله اصلی تعیین تعداد دفعات مراحل قبل از ورود به این حالت است.
هرگاه $P$ عبارت از ماتریس احتمالات تغییر حالت اتفاقی باشد، ماتریس $Q$ بر مبنای آن و با حذف سطر و ستون‌های مربوط به حالت ماندگار تشکیل داده می‌شود. در صورت تشکیل چنین ماتریسی برای سیستم دو حالتی (شکل (1)) با تعریف حالت 2 به عنوان حالت ماندگار، ماتریسی با یک جزء به صورت $\left[ {{P_{11}}} \right]$ شکل می‌گیرد. این ماتریس نمایانگر مجموعه‌ای از حالت‌های گذرا است و با تعیین تعداد انتظاری از دفعات مراحل زمانی که سیستم در یکی از حالت‌های ارائه شده در این ماتریس باقی می‌ماند دفعات مورد نظر به دست آورده می‌شود.
رابطه (12)
$$E(x) = \sum\limits_{i = 1}^\infty {{x_i}} {P_i}$$
معادله فوق نه تنها برای عضوهای یک احتمالی با احتمال ${P_i}$ به کار می‌رود بلکه برای عضوهای چند احتمالی با ماتریس احتمال $Q$ نیز قابل استفاده است. بنابراین هرگاه $N$ نمایانگر تعداد دفعات انتظاری از تکرار مراحل زمانی برای حالت‌های گذرا باشد خواهیم داشت:
رابطه (13)
$$N = 1.I + 1.Q + 1.{Q^2} + ... + 1.{Q^{n - 1}}$$
که در آن $I$ ماتریس هویت (یا واحد) می‌باشد.
در معادله (13) ماتریس واحد، نمایانگر احتمال همه شرایط اولیه ممکن است و عدد یک در هر ردیف از آن مبیّن سهم حالت با شماره همان ردیف می‌باشد. هر کدام از اعداد یک در معادله فوق نمایانگر یک مرحله از مراحل متوالی است و معادل ${x_i}$ در معادله (12) است. اولین مرحله زمانی با ماتریس احتمال $I$ اتفاق می‌افتد. دومین مرحله با ماتریس احتمال $Q$، سومین مرحله با ماتریس احتمال ${Q^2}$ و نهایتاً سیستم در $n$ امین مرحله زمانی به حالت ماندگار درمی‌آید. معادله (13) به صورت در پی آمده نمایش‌پذیر است:
رابطه (14)
$$N = I + Q + {Q^2} + ... + {Q^{n - 1}}$$
معادله (14) به سادگی ارزیابی‌پذیر نیست و به جای آن از معادله در پی آمده که در واقع بسط دوجمله‌ای است استفاده می‌شود.
رابطه (15)
$$\left[ {I - Q} \right]\left[ {I + Q + {Q^2} + ... + {Q^{n - 1}}} \right] = 1 - {Q^n}$$
با تعمیم معادله (11) داریم: $\mathop {\lim }\limits_{n \to \infty } {Q^n} = 0$ بنابراین بر اساس $n\; \to \;\infty $ خواهیم داشت:
$$\begin{array}{l}
I - {Q^n}\; \to \;I\\
\left[ {I - Q} \right]\left[ {1 + Q + {Q^2} + ... + {Q^{n - 1}}} \right] = I
\end{array}$$
و یا:
رابطه (16)
$$I + Q + {Q^2} + ... + {Q^{n - 1}} = {(I - Q)^{ - 1}}I = {\left[ {I - Q} \right]^{ - 1}}$$
به عبارت دیگر بر اساس معادله‌های (14) و (16) خواهیم داشت:
رابطه (17)
$$N = {\left[ {I - Q} \right]^{ - 1}}$$
کاربرد این معادله در مقایسه با معادله (14) برای تعیین $N$ سهولت بیشتری فراهم می‌سازد. به عنوان مثال برای سیستم دو حالتی که در آن حالت شماره 2 حالت ماندگار است همان‌گونه که قبلاً ذکر شد $Q = {P_{11}} = \frac{1}{2}$ و لذا:
$$N = {\left[ {1 - \frac{1}{2}} \right]^{ - 1}} = 2$$
بدین ترتیب با شروع سیستم از مرحله 1، انتظار می‌رود به طور متوسط پس از دو مرحله زمانی سیستم به حالت ماندگار 2 درآید.
کاربرد شیوه ناپیوسته مارکوف (Application of Discrete Markov Techniques)
حال با ارائه دو مثال عددی، چگونگی کاربرد روش‌های تشریح شده را نشان می‌دهیم.
مثال (1): در سیستم سه وضعیتی با احتمالات گذر از حالت‌های آن که در شکل (4) نشان داده شده است مطلوب است ارزیابی:
الف) احتمالات حدی هر یک از حالت‌ها
ب) تعداد متوسط مراحل زمانی برای هر حالت قبل از این که سیستم به حالت 3 به عنوان حالت ماندگار درآید.
الف) در ابتدا ماتریس احتمال تغییر حالت اتفاقی تشکیل داده می‌شود:
$$\begin{array}{l}
\;\;\;\;\;\;\;\;\;\;\;\;1\;\;\;\;\;\;\;2\;\;\;\;\;\;3\\
P = \begin{array}{*{20}{c}}
1\\
2\\
3
\end{array}\;\left[ {\begin{array}{*{20}{c}}
{\frac{3}{4}}&{\frac{1}{4}}&0\\
0&{\frac{1}{2}}&{\frac{1}{2}}\\
{\frac{1}{3}}&{\frac{1}{3}}&{\frac{1}{3}}
\end{array}} \right]
\end{array}$$
هرگاه احتمالات حدی به ترتیب با ${P_1}$، ${P_2}$ و ${P_3}$ نشان داده شود، بر مبنای معادله (6) خواهیم داشت:
$$\left[ {{{\begin{array}{*{20}{c}}
{{P_1}}&{{P_2}}&P
\end{array}}_3}} \right]\;\left[ {\begin{array}{*{20}{c}}
{\frac{3}{4}}&{\frac{1}{4}}&0\\
0&{\frac{1}{2}}&{\frac{1}{2}}\\
{\frac{1}{3}}&{\frac{1}{3}}&{\frac{1}{3}}
\end{array}} \right] = \left[ {{{\begin{array}{*{20}{c}}
{{P_1}}&{{P_2}}&P
\end{array}}_3}} \right]$$
شکل 4
که به مفهوم دستگاه معادلات زیر است:
رابطه (18)
$$\frac{3}{4}P1 + \frac{1}{3}{P_3} = {P_1}$$
رابطه (19)
$$\frac{1}{2}{P_2} + \frac{1}{3}{P_3} = {P_3}$$
رابطه (20)
$$\frac{1}{2}{P_2} + \frac{1}{3}{P_3} = {P_3}$$
یکی از معادلات دستگاه فوق باید حذف شده و معادله زیر جایگزین آن شود:
رابطه (21)
$${P_1} + {P_2} + {P_3} = 1$$
با حذف معادله (20) از دستگاه فوق، دستگاه معادلات به شکل ماتریسی به صورت در پی آمده نمایش‌پذیر است.
$$\left[ {\begin{array}{*{20}{c}}
{ - \frac{1}{4}}&0&{\frac{1}{3}}\\
{\frac{1}{4}}&{ - \frac{1}{2}}&{\frac{1}{3}}\\
1&1&1
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{P_1}}\\
{{P_2}}\\
{{P_3}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
0\\
0\\
1
\end{array}} \right]$$
طبق قاعده کرامر:
$${P_1} = \frac{{\left| {\begin{array}{*{20}{c}}
0&0&{\frac{1}{3}}\\
0&{ - \frac{1}{2}}&{\frac{1}{3}}\\
1&1&1
\end{array}} \right|}}{{\left| {\begin{array}{*{20}{c}}
{ - \frac{1}{4}}&0&{\frac{1}{3}}\\
{\frac{1}{4}}&{ - \frac{1}{2}}&{\frac{1}{3}}\\
1&1&1
\end{array}} \right|}} = \frac{4}{{11}}$$
و مشابهاً: ${P_3} = \frac{3}{{11}}$ و ${P_2} = \frac{4}{{11}}$
ب) ماتریس با حذف ردیف و ستون مربوط به حالت ماندگار به شکل در پی آمده تشکیل می‌شود.
$$\begin{array}{l}
\;\;\;\;\;\;\;\;\;\;\;\;1\;\;\;\;\;\;\;2\\
Q = \begin{array}{*{20}{c}}
1\\
2
\end{array}\;\left[ {\begin{array}{*{20}{c}}
{\frac{3}{4}}&{\frac{1}{4}}\\
0&{\frac{1}{2}}
\end{array}} \right]\\
I - Q = \left[ {\begin{array}{*{20}{c}}
1&0\\
0&1
\end{array}} \right] - \left[ {\begin{array}{*{20}{c}}
{\frac{3}{4}}&{\frac{1}{4}}\\
0&{\frac{1}{2}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{\frac{1}{4}}&{\frac{{ - 1}}{4}}\\
0&{\frac{1}{2}}
\end{array}} \right]\\
{\left[ {I - Q} \right]^{ - 1}} = \frac{{\left[ {\begin{array}{*{20}{c}}
{\frac{1}{2}}&{\frac{1}{4}}\\
0&{\frac{1}{4}}
\end{array}} \right]}}{{\left[ {\begin{array}{*{20}{c}}
{\frac{1}{4}}&{ - \frac{1}{4}}\\
0&{\frac{1}{2}}
\end{array}} \right]}} = 8\left[ {\begin{array}{*{20}{c}}
{\frac{1}{2}}&{\frac{1}{4}}\\
0&{\frac{1}{4}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
4&2\\
0&2
\end{array}} \right]
\end{array}$$
بنابراین با استفاده از معادله (17) داریم:
$$\begin{array}{l}
\;\;\;\;\;\;\;\;\;\;\;1\;\;\;\;2\\
N = \begin{array}{*{20}{c}}
1\\
2
\end{array}\;\left[ {\begin{array}{*{20}{c}}
4&2\\
0&2
\end{array}} \right]
\end{array}$$
یا ${N_{11}} = 4$، ${N_{12}} = 2$، ${N_{21}} = 0$، ${N_{22}} = 2$.
مقادیر فوق نشان می‌دهند که هرگاه سیستم از حالت 1 شروع نماید انتظار می‌رود که قبل از رسیدن به حالت ماندگار 3 به طور متوسط تعداد 4 مرحله زمانی در حالت 1 $\left( {{N_{11}}} \right)$ و تعداد 2 مرحله زمانی در حالت 2 به سر برد $\left( {{N_{12}}} \right)$.
یکی از این مقادیر یعنی ${N_{21}}$ برابر صفر است و نمایانگر عدم استقرار سیستم در حالت 1 است مشروط بر آن که سیستم از حالت 2 شروع کرده باشد. زیرا هیچ طریق مستقیمی برای حصول حالت 1 از حالت 2 وجود نداشته و تنها مسیر میسر از طریق حالت ماندگار 3 است که از آن هم امکان گذر وجود ندارد.
مثال (2): شخصی برای رسیدن به محل کار خود هم از اتومبیل شخصی و هم از قطار استفاده می‌کند. با فرض این که هیچ‌گاه از قطار در دو روز متوالی استفاده نشود ولی روز بعد از استفاده از اتومبیل شخصی احتمال استفاده مجدد از آن و یا استفاده از قطار به طور یکسان وجود داشته باشد مطلوب است ارزیابی:
الف- احتمال استفاده از اتومبیل شخصی پس از: $(i$ دو روز، $(ii$ گذشت زمان طولانی.
ب- احتمال استفاده از اتومبیل شخصی پس از $(i$ دو روز، $(ii$ گذشت مدت طولانی، مشروط بر آن که روز اول برای استفاده از اتومبیل انداختن تاس و رؤیت نتیجه 2 مبنای انتخاب قرار گیرد.
در ابتدا ماتریس احتمالات تغییر حالت اتفاقی برای این فرآیند مارکوف تشکیل داده می‌شود:
$$\begin{array}{l}
\;\;\;\;\;\;\;\;\;\;\;\;t\;\;\;\;\;\,d\\
P = \begin{array}{*{20}{c}}
t\\
d
\end{array}\;\left[ {\begin{array}{*{20}{c}}
0&1\\
{\frac{1}{2}}&{\frac{1}{2}}
\end{array}} \right]
\end{array}$$
که در آن $t$ نمایانگر استفاده از قطار و $d$ نمایانگر استفاده از اتومبیل شخصی است. در تشکیل این ماتریس ردیف 1 نشان‌دهنده احتمال استفاده از قطار و یا اتومبیل (در مرحله زمانی بعدی) پس از استفاده از قطار است و چون هیچ‌گاه از قطار برای دو روز متوالی استفاده نمی‌شود بنابراین اجزاء این ردیف باید صفر و یک منظور شود و ردیف 2 ارائه کننده احتمال استفاده از قطار و یا اتومبیل پس از استفاده از اتومبیل است و لذا احتمال یکسانی برایشان منظور شده است.
الف-1) احتمال حالت‌های گذرا پس از 2 روز یا دو مرحله زمانی توسط ماتریس ${P^2}$ تعیین می‌شود:
$$\begin{array}{l}
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\,\;\;t\;\;\;\;\;\,d\\
{P^2} = \left[ {\begin{array}{*{20}{c}}
0&1\\
{\frac{1}{2}}&{\frac{1}{2}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
0&1\\
{\frac{1}{2}}&{\frac{1}{2}}
\end{array}} \right] = \begin{array}{*{20}{c}}
t\\
d
\end{array}\;\left[ {\begin{array}{*{20}{c}}
{\frac{1}{2}}&{\frac{1}{2}}\\
{\frac{1}{4}}&{\frac{3}{4}}
\end{array}} \right]
\end{array}$$
حال با فرض این که روز اول از قطار استفاده شده باشد برای بردار شرایط اولیه $P(0)$ داریم:
$$\begin{array}{l}
\;\;\;\;\;\;\;\;\;\,\;\;t\;\;\,d\\
P(0) = \left[ {\begin{array}{*{20}{c}}
1&0
\end{array}} \right]
\end{array}$$
و احتمالات حالت‌ها پس از 2 روز خواهد شد:
$$\begin{array}{l}
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\,\;\;\;\;\;\,\;\;t\;\;\,\,\;\;\;d\\
P(2) = \left[ {\begin{array}{*{20}{c}}
1&0
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{\frac{1}{2}}&{\frac{1}{2}}\\
{\frac{1}{4}}&{\frac{3}{4}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{\frac{1}{2}}&{\frac{1}{2}}
\end{array}} \right]
\end{array}$$
که به مفهوم احتمال یکسان در استفاده از اتومبیل و یا قطار پس از گذشت دو روز است ولی وقتی روز اول از اتومبیل استفاده شود:
$$\begin{array}{l}
\;\;\;\;\;\;\;\;\;\,\;\;t\;\;\,d\\
P(0) = \left[ {\begin{array}{*{20}{c}}
0&1
\end{array}} \right]\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\,\;\;\;\;\;\,\;\;t\;\;\,\,\;\;\;d\\
P(2) = \left[ {\begin{array}{*{20}{c}}
0&1
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{\frac{1}{2}}&{\frac{1}{2}}\\
{\frac{1}{4}}&{\frac{3}{4}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{\frac{1}{4}}&{\frac{3}{4}}
\end{array}} \right]
\end{array}$$
که به مفهوم استفاده از اتومبیل با احتمالی سه برابر احتمال استفاده از قطار است.
الف-2): برای ارزیابی احتمالات پس از مدت طولانی باید احتمالات حدی محاسبه شود.
با معرفی ${P_t}$ و ${P_d}$ به عنوان احتمال حدی استفاده از قطار و اتومبیل خواهیم داشت:
$$\begin{array}{l}
\left[ {\begin{array}{*{20}{c}}
{{P_t}}&{{P_d}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
0&1\\
{\frac{1}{2}}&{\frac{1}{2}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{{P_t}}&{{P_d}}
\end{array}} \right]\\
\left\{ {\begin{array}{*{20}{c}}
{\frac{1}{2}{P_d} = {P_t}}\\
{{P_t} + {P_d} = 1}
\end{array}} \right.
\end{array}$$
در نتیجه: ${P_t} = \frac{1}{3}$ و ${P_d} = \frac{2}{3}$ و بنابراین در دراز مدت $\frac{2}{3}$ اوقات از اتومبیل استفاده خواهد شد.
ب-1): با توجه به احتمال یک وجه از شش وجه تاس برابر $\frac{1}{6}$ بردار شرایط اولیه به شکل زیر درمی‌آید:
$$\begin{array}{l}
\;\;\;\;\;\;\;\;\;\,\;\;\;\;t\;\;\;\;\;\;\,d\\
P(0) = \left[ {\begin{array}{*{20}{c}}
{\frac{5}{6}}&{\frac{1}{6}}
\end{array}} \right]\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\,\;\;\;\;\;\;\;\;\;\;\;\;\,\;\;t\;\;\,\,\;\;\;\;\;\;\;d\\
P(2) = \left[ {\begin{array}{*{20}{c}}
{\frac{5}{6}}&{\frac{1}{6}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{\frac{1}{2}}&{\frac{1}{2}}\\
{\frac{1}{4}}&{\frac{3}{4}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{\frac{{11}}{{24}}}&{\frac{{13}}{{24}}}
\end{array}} \right]
\end{array}$$
بنابراین احتمال استفاده از اتومبیل دو روز بعد معادل $\frac{{13}}{{24}}$ می‌باشد.
ب-2): از آنجایی که این مسئله، ارگودیک است مقادیر حدی احتمالات بستگی به شرایط اولیه نداشته و می‌توان نشان داد که همان نتایج قسمت (الف-2) از مسئله حاصل خواهد شد. لذا ${P_t} = \frac{1}{3}$ و ${P_d} = \frac{2}{3}$ می‌شود.