مارکوو زنجیر

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

### مارکوو زنجیر
*تعریف*: اگر مارکوو زنجیر کی ممکنہ حالتوں کی تعداد *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}


تصغیر|بائیں|مارکوو زنجیر کی سیڑھی 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]


### حالت سمتیہ
مارکوو زنجیر جس کی حالتوں کی تعداد *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)}=P X^{(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* کے لیے حل کیا جا سکتا ہے۔

زمرہ:احتمال نظریہ

زمرہ:نظریہ گراف
زمرہ:نگاری نظریہ
زمرہ:عشوائی عملیت
زمرہ:نظریۂ شمارندیت
زمرہ:تحقیق عملیات
زمرہ:شماریات