مارکوو زنجیر

اصطلاح	term
مارکوو زنجیر حالت حالت فضاء حالت سمتیہ منتقلی تصادفی	Markov chain state state space state vector transition random

فرض کرو کہ ایک طبیعیاتی نظام ایک حالت سے دوسری حالت میں منتقلی کر سکتا ہو۔ ان حالتوں کی تعدار محدود ہو۔ مثلاً کسی دن کا موسم: "دھوپ" یا "بادل" یا "بارش"۔ اگر اس نظام کی اگلی حالت کا احتمال، صرف موجودہ حالت جاننے سے معلوم ہو سکے، تو ایسے نظام کو مارکوو زنجیر یا مارکوو عملیت کہا جاتا ہے۔

مارکوو زنجیر

تعریف: اگر مارکوو زنجیر کی ممکنہ حالتوں کی تعداد M ہو، جن کو ہم $u_{1},u_{2},\cdots ,u_{M}$ لکھتے ہیں۔ اب اگر نظام ابھی حالت $u_{i}$ میں ہو، تو اس احتمال کو کہ نظام کی اگلی حالت $u_{j}$ ہو گی، (اس احتمال) کو $p_{i,j}$ سے ظاہر کرتے ہیں۔ اس احتمال کو حالت $u_{i}$ سے حالت $u_{j}$ میں جانے کا منتقلی احتمال کہا جاتا ہے۔ اور میٹرکس $\ P=[p_{i,j}]$ کو اس مارکوو زنجیر کی منتقلی میٹرکس کہتے ہیں۔

M=3 کے لیے "منتقلی میٹرکس" کو یوں لکھیں گے: $P={\begin{matrix}{\begin{matrix}{\hbox{old state}}\end{matrix}}&{\begin{matrix}\end{matrix}}&{\begin{matrix}\end{matrix}}\\{\begin{matrix}u_{1}&u_{2}&u_{3}\end{matrix}}&{\begin{matrix}\end{matrix}}&{\begin{matrix}\end{matrix}}\\\left[{\begin{matrix}p_{1,1}&p_{1,2}&p_{1,3}\\p_{2,1}&p_{2,2}&p_{2,3}\\p_{3,1}&p_{3,2}&p_{3,3}\end{matrix}}\right]&{\begin{matrix}u_{1}\\u_{2}\\u_{3}\end{matrix}}&{\begin{matrix}{\hbox{new state}}\end{matrix}}\end{matrix}}$

فائل:Markov chain from.png

مارکوو زنجیر کی سیڑھی k پر سے سیڑھی k+1 پر منتقلی

خیال رہے کہ اس مارکوو میٹرکس کے ہر ستون کے اجزا کا جمع 1 ہو گا:

$p_{1,j}+p_{2,j}+\cdots +p_{M,j}=1$

جس کی وجہ یہ ہے کہ تمام ممکنہ حالتوں سے اگلی سیڑھی پر حالت $u_{j}$ پر جانے کے احتمال کی جمع نظریہ احتمال کی رو سے ایکا (1) ہونا لازمی ہے۔ ایسی میٹرکس کو تصادفی میٹرکس کہتے ہیں۔

وضاحت کے لیے ہم مارکوو زنجیر کی تعریف دوبارہ تصادفی تجربات کی صورت میں کرتے ہیں:

مارکوو زنجیر

"تعریف": فرض کرو تجربات کا ایک سلسلہ چلایا جاتا ہے۔ ہر تجربہ پر ممکنہ نتائج $u_{1},u_{2},\cdots ,u_{M}$ ہیں، جن (ممکنات) کی تعداد M ہے۔ اگر $\ (k+1)$ اویں تجربہ پر نتیجہ $u_{j}$ آنے کا احتمال $p_{i,j}$، جبکہ یہ دیا گیا ہے کہ $k$ اویں تجربہ پر نتیجہ $u_{j}$ تھا، اس کا منحصر $k$ پر نہ ہو، تو اس تجرباتی سلسلہ کو "مارکوو زنجیر" کہا جائے گا۔ ممکنہ نتائج کی فہرست $u_{1},u_{2},\cdots ,u_{M}$ کو حالت فضاء کہتے ہیں اور کسی نتیجہ کو حالت۔ ایسی میٹرکس جس کا سائز $M\times M$ ہے اور اس کی $i$ اویں قطار اور $j$ اویں ستون پر جُز $p_{i,j}$ ہے، کو اس مارکوو زنجیر کی منتقلی میٹرکس کہتے ہیں۔

مثال

فرض کرو کہ سرخ گلاب کا بیج بونے سے پیدا ہونے والے بودے پر سرخ گلاب پھول لگنے کا امکان 80 فیصد ہے، جبکہ سفید گلاب پھول کا امکان 20 فیصد ہے۔ اور سفید گلاب بیج سے سفید گلاب پھول لگنے کا امکان 60 فیصد ہے، جبکہ سرخ پھول لگنے کا 40 فیصد۔ تو اس مارکود زنجیر، جہاں حالت "سرخ پھول$\ u_{1}=$" یا "سفید پھول$\ u_{2}=$" ہیں، کی تصادفی میٹرکس یہ ہو گی:

$P=\left[{\begin{matrix}0.8&0.6\\0.2&0.4\end{matrix}}\right]$

اصطلاح	term
احتمالِ واقعہ سیڑھی باقاعدہ ثباتی حالت	probability of event $=\Pr\{{\hbox{Event}}\}$ step regular steady-state

حالت سمتیہ

مارکوو زنجیر جس کی حالتوں کی تعداد M ہو، کا حالت سمتیہ $\ X^{(k)}$ ایک $M\times 1$ میٹرکس ہے، جس کا i ایواں جُز اس واقعہ کا احتمال ہے کہ k ایواں تجربہ پر (یا وقت k پر) زنجیر کی حالت $u_{i}$ ہے۔

وقت k پر حالت سمتیہ $\ X^{(k)}$ کو یوں لکھا جا سکتا ہے: $X^{(k)}=\left[{\begin{matrix}\Pr\{State=u_{1}\}\\\Pr\{State=u_{2}\}\\\vdots \\\Pr\{State=u_{M}\}\end{matrix}}\right]$ واضح رہے کہ اس سمتیہ کے اجزا کا جمع ایکا (1) ہے،

$\sum _{i=1}^{M}\Pr\{State=u_{i}\}=1$

یہ $\ X^{(k)}$ "تصادفی سمتیہ" کہلاتا ہے۔

سیڑھی k+1 پر مارکوو حالتوں کے تصادفی سمتیہ کو سیڑھی k پر تصادفی سمتیہ سے یوں حاصل کیا جا سکتا ہے (تصادفی منتقلی میٹرکس P کے استعمال سے ):

$\ X^{(k+1)}=PX^{(k)}$

اس فرق مساوات سے معلوم ہوتا ہے کہ

$\ X^{(k)}=P^{k}X^{(0)}$

اوپر کی مثال میں اگر فرق مساوات کی تکرار کی جائے تو معلوم ہوتا ہے کہ

$X^{(\infty )}=\left[{\begin{matrix}0.75\\0.25\end{matrix}}\right]$

چاہے ابتدائی بیج کی رنگی تقسیم $\ X^{(0)}$ کچھ بھی ہو۔ یعنی کافی نسلوں کے بعد سرخ گلاب پھول75 فیصد ہوں گے اور سفید 25 فیصد۔

اب ہم دیکھتے ہیں کہ ایسا کن صورتوں میں ممکن ہو گا کہ لمبے دور (ثباتی حالت) میں تصادفی سمتیہ ابتدا کی حالت سے آزاد پو۔

باقاعدہ منتقلی میٹرکس

مارکوو زنجیر کی منتقلی میٹرکس $P$ کو باقاعدہ کہیں گے اگر اس میٹرکس کی کسی صحیح عدد طاقت $P^{n}$ کے تمام جُز مثبت ہوں۔

مسلئہ اثباتی

اگر منتقلی میٹرکس باقاعدہ ہو، تو جسیے $\ n\to \infty$

$P^{n}\to \left[{\begin{matrix}q_{1}&q_{1}&\cdots &q_{1}\\q_{2}&q_{2}&\cdots &q_{2}\\\vdots &\vdots &&\vdots \\q_{M}&q_{M}&\cdots &q_{M}\end{matrix}}\right]$

جہاں $q_{k}$ مثبت اعداد ہیں اور $q_{1}+q_{2}+\cdots +q_{M}=1$

مسلئہ اثباتی

اگر منتقلی میٹرکس P باقاعدہ ہو اور X ایک تصادفی سمتیہ ہو، تو جسیے $\ n\to \infty$

$P^{n}X\to \left[{\begin{matrix}q_{1}\\q_{2}\\\vdots \\q_{M}\end{matrix}}\right]=q$

جہاں q ایک مستقل تصادفی سمتیہ ہے اور $q_{1},q_{2},\cdots ,q_{M}$ مثبت اعداد ہیں۔

مسلئہ اثباتی

باقاعدہ منتقلی میٹرکس P کا ثباتی حالت تصادفی سمتیہ q ایک منفرد تصادفی سمتیہ ہوتا ہے، جو اس مساوات کا حل ہو:

$Pq=q$

یعنی یہ تصادفی سمتیہ اس فنکشن $Y=PX$ کا مستقل نکتہ ہے۔ اس یکلخت لکیری مساوات کا نظام

$\ (P-I_{M})q=0$

کو q کے لیے حل کیا جا سکتا ہے۔

E=mc2     اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں LTR پڑھیٔے     ریاضی علامات