مارکوو زنجیر

آزاد دائرۃ المعارف، ویکیپیڈیا سے
یہاں جائیں: رہنمائی، تلاش کریں
اصطلاح term

مارکوو زنجیر
حالت
حالت فضاء
حالت سمتیہ
منتقلی
تصادفی

Markov chain
state
state space
state vector
transition
random

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

مارکوو زنجیر[ترمیم]

تعریف: اگر مارکوو زنجیر کی ممکنہ حالتوں کی تعداد M ہو، جن کو ہم لکھتے ہیں۔ اب اگر نظام ابھی حالت میں ہو، تو اس احتمال کو کہ نظام کی اگلی حالت ہو گی، (اس احتمال) کو سے ظاہر کرتے ہیں۔ اس احتمال کو حالت سے حالت میں جانے کا منتقلی احتمال کہا جاتا ہے۔ اور میٹرکس کو اس مارکوو زنجیر کی منتقلی میٹرکس کہتے ہیں۔

M=3 کے لیے "منتقلی میٹرکس" کو یوں لکھیں گے:

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

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

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

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

مارکوو زنجیر[ترمیم]

"تعریف": فرض کرو تجربات کا ایک سلسلہ چلایا جاتا ہے۔ ہر تجربہ پر ممکنہ نتائج ہیں، جن (ممکنات) کی تعداد M ہے۔ اگر اویں تجربہ پر نتیجہ آنے کا احتمال ، جبکہ یہ دیا گیا ہے کہ اویں تجربہ پر نتیجہ تھا، اس کا منحصر پر نہ ہو، تو اس تجرباتی سلسلہ کو "مارکوو زنجیر" کہا جائے گا۔ ممکنہ نتائج کی فہرست کو حالت فضاء کہتے ہیں، اور کسی نتیجہ کو حالت۔ ایسی میٹرکس جس کا سائز ہے، اور اس کی اویں قطار اور اویں ستون پر جُز ہے، کو اس مارکوو زنجیر کی منتقلی میٹرکس کہتے ہیں۔

مثال[ترمیم]

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

اصطلاح term

احتمالِ واقعہ
سیڑھی
باقاعدہ
ثباتی حالت

probability of event
step
regular
steady-state

حالت سمتیہ[ترمیم]

مارکوو زنجیر جس کی حالتوں کی تعداد M ہو، کا حالت سمتیہ ایک میٹرکس ہے، جس کا i ایواں جُز اس واقعہ کا احتمال ہے کہ k ایواں تجربہ پر (یا وقت k پر) زنجیر کی حالت ہے۔

وقت k پر حالت سمتیہ کو یوں لکھا جا سکتا ہے: واضح رہے کہ اس سمتیہ کے اجزا کا جمع ایکا (1) ہے،

یہ "تصادفی سمتیہ" کہلاتا ہے۔

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

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

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

چاہے ابتدائی بیج کی رنگی تقسیم کچھ بھی ہو۔ یعنی کافی نسلوں کے بعد سرخ گلاب پھول75 فیصد ہوں گے اور سفید 25 فیصد۔

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

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

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

مسلئہ اثباتی[ترمیم]

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

جہاں مثبت اعداد ہیں، اور

مسلئہ اثباتی[ترمیم]

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

جہاں q ایک مستقل تصادفی سمتیہ ہے، اور مثبت اعداد ہیں۔

مسلئہ اثباتی[ترمیم]

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

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

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

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