مارکوو زنجیر

آزاد دائرۃ المعارف، ویکیپیڈیا سے
:چھلانگ بطرف رہنمائی، تلاش
اصطلاح 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}

مارکوو زنجیر کی سیڑھی 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)}=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 کے لیے حل کیا جا سکتا ہے۔


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