Markov chain tree theorem
مارکوف زنجیروں کے ریاضیاتی نظریہ میں، مارکوف زنجیر درخت نظریہ محدود طور پر کئی حالتوں کے ساتھ مارکوف زنجیر کی ساکن تقسیم کے لیے ایک اظہار ہے۔ یہ مارکوف سلسلہ کے جڑوں پر پھیلے ہوئے درختوں کے لیے اصطلاحات کا خلاصہ کرتا ہے، جس میں ہر درخت کے لیے ایک مثبت امتزاج ہوتا ہے۔ مارکوف چین ٹری تھیوریم کا گراف کے پھیلے ہوئے درختوں کی گنتی پر کرچوف کے تھیوریم سے گہرا تعلق ہے، جس سے اسے اخذ کیا جا سکتا ہے۔ یہ سب سے پہلے تھرموڈینامکس میں پیدا ہونے والی بعض مارکوف زنجیروں کے لیے کہا گیا تھا، اور ایک متعصبانہ سکے کے امکان کے محدود میموری تخمینے میں ایک درخواست سے متاثر ہو کر مکمل عام طور پر ثابت ہوا۔ ایک محدود مارکوف سلسلہ ریاستوں کے ایک محدود سیٹ پر مشتمل ہوتا ہے، اور ریاست سے ریاست میں تبدیل ہونے کا ایک منتقلی کا امکان ہوتا ہے، اس طرح کہ ہر ریاست کے لیے سبکدوش ہونے والے منتقلی کے امکانات کا مجموعہ ایک ہو جاتا ہے۔ ریاست کے ابتدائی انتخاب سے (جو اس مسئلے سے غیر متعلقہ ثابت ہوتا ہے)، ہر یکے بعد دیگرے ریاست کو پچھلی ریاست سے منتقلی کے امکانات کے مطابق تصادفی طور پر منتخب کیا جاتا ہے۔ مارکوف سلسلہ کو اس وقت ناقابل تلافی کہا جاتا ہے جب ہر ریاست منتقلی کے کسی سلسلے کے ذریعے ہر دوسری ریاست تک پہنچ سکتی ہے، اور اگر، ہر ریاست کے لیے، اس حالت میں شروع ہونے اور ختم ہونے والے مراحل کی ممکنہ تعداد میں سب سے بڑا مشترکہ تقسیم کنندہ ہو۔ ایک ناقابل تلافی اور اپریوڈک مارکوف سلسلہ میں لازمی طور پر ایک مستحکم تقسیم ہوتی ہے، جو اس کی حالتوں پر ایک امکان کی تقسیم ہے جو ریاست کے ابتدائی انتخاب سے قطع نظر، بہت سے مراحل کے بعد دی گئی حالت میں ہونے کے امکان کو بیان کرتی ہے۔ مارکوف چین ٹری تھیوریم مارکوف چین کی حالتوں کے لیے درختوں کو پھیلانے پر غور کرتا ہے، جس کی تعریف درختوں کے طور پر کی گئی ہے، جو ایک نامزد جڑ کی طرف ہے، جس میں تمام سمت والے کنارے دی گئی مارکوف چین کی درست منتقلی ہیں۔ اگر ریاست سے ریاست میں منتقلی کا امکان ہوتا ہے، تو کنارے والے درخت کا وزن اس کی منتقلی کے امکانات کے پروڈکٹ کے برابر ہوتا ہے: آئیے ان تمام پھیلے ہوئے درختوں کے سیٹ کی نشاندہی کریں جن کی جڑ میں حالت ہوتی ہے۔ پھر، مارکوف چین ٹری تھیوریم کے مطابق، حالت کے لیے مستحکم امکان ان درختوں کے وزن کے مجموعے کے متناسب ہے جن کی جڑیں ہیں۔ یعنی، جہاں نارملائزنگ مستقل تمام پھیلے ہوئے درختوں کا مجموعہ ہے۔ حوالہ جات مارکوف پھیلے ہوئے درخت پر عمل کرتا ہے