Markov chain tree theorem
মার্কভ চেইনের গাণিতিক তত্ত্বে, মার্কভ চেইন ট্রি উপপাদ্যটি সীমিতভাবে অনেকগুলি অবস্থার সাথে একটি মার্কভ চেইনের স্থির বিতরণের জন্য একটি অভিব্যক্তি। এটি প্রতিটি গাছের জন্য একটি ইতিবাচক সংমিশ্রণ সহ মার্কভ শৃঙ্খলের শিকড়যুক্ত বিস্তৃত গাছের শর্তাবলী সংক্ষিপ্ত করে। মার্কভ চেইন ট্রি উপপাদ্যটি একটি গ্রাফের বিস্তৃত গাছ গণনা করার বিষয়ে কির্চফের উপপাদ্যের সাথে ঘনিষ্ঠভাবে সম্পর্কিত, যেখান থেকে এটি উদ্ভূত করা যেতে পারে। এটি প্রথম বলা হয়েছিল, তাপগতিবিদ্যায় উদ্ভূত কিছু মার্কভ চেইনের জন্য, এবং একটি পক্ষপাতদুষ্ট মুদ্রার সম্ভাবনার সীমিত-মেমরি অনুমানের প্রয়োগ দ্বারা অনুপ্রাণিত হয়ে সম্পূর্ণ সাধারণভাবে প্রমাণিত হয়েছিল। একটি সীমাবদ্ধ মার্কভ শৃঙ্খল অবস্থার একটি সীমাবদ্ধ সেট এবং একটি রাজ্য থেকে অন্য রাজ্যে পরিবর্তনের জন্য একটি রূপান্তর সম্ভাবনা নিয়ে গঠিত, যাতে প্রতিটি রাজ্যের জন্য বহির্গামী রূপান্তর সম্ভাবনার যোগফল এক হয়। রাষ্ট্রের প্রাথমিক পছন্দ থেকে (যা এই সমস্যার সাথে অপ্রাসঙ্গিক বলে প্রমাণিত হয়), প্রতিটি ধারাবাহিক রাজ্য পূর্ববর্তী অবস্থা থেকে রূপান্তর সম্ভাবনা অনুযায়ী এলোমেলোভাবে বেছে নেওয়া হয়। একটি মার্কভ শৃঙ্খলকে বলা হয় অপরিবর্তনীয় যখন প্রতিটি রাজ্য পরিবর্তনের কিছু ক্রমের মাধ্যমে প্রতিটি অন্য রাজ্যে পৌঁছতে পারে, এবং অপেরিওডিক যদি, প্রতিটি রাজ্যের জন্য, সেই অবস্থায় শুরু এবং শেষ হওয়া ক্রমের সম্ভাব্য সংখ্যক ধাপের সর্বাধিক সাধারণ বিভাজক থাকে। একটি অপরিবর্তনীয় এবং অপেরিওডিক মার্কভ শৃঙ্খলের অপরিহার্যভাবে একটি স্থির বন্টন থাকে, যা তার অবস্থার উপর একটি সম্ভাব্যতা বন্টন যা অবস্থার প্রাথমিক পছন্দ নির্বিশেষে অনেক ধাপের পরে একটি প্রদত্ত অবস্থায় থাকার সম্ভাবনা বর্ণনা করে। মার্কভ শৃঙ্খল বৃক্ষ উপপাদ্যটি মার্কভ শৃঙ্খলের অবস্থার জন্য বিস্তৃত গাছগুলিকে বিবেচনা করে, যা গাছ হিসাবে সংজ্ঞায়িত, একটি নির্দিষ্ট মূলের দিকে পরিচালিত, যেখানে সমস্ত নির্দেশিত প্রান্ত প্রদত্ত মার্কভ শৃঙ্খলের বৈধ রূপান্তর। যদি একটি রাজ্য থেকে অন্য রাজ্যে রূপান্তরের সম্ভাবনা থাকে, তবে প্রান্ত সেট সহ একটি গাছের ওজন তার রূপান্তর সম্ভাবনার গুণফলের সমান বলে সংজ্ঞায়িত করা হয়ঃ আসুন তাদের মূলে অবস্থা থাকা সমস্ত বিস্তৃত গাছের সেটকে বোঝাই। তারপর, মার্কভ চেইন ট্রি উপপাদ্য অনুসারে, অবস্থার জন্য স্থির সম্ভাব্যতা মূলযুক্ত গাছের ওজনের যোগফলের সাথে আনুপাতিক। অর্থাৎ, যেখানে স্বাভাবিককরণ ধ্রুবক হল সমস্ত বিস্তৃত গাছের সমষ্টি। মার্কভ স্প্রেনিং ট্রি প্রক্রিয়া করে