Markov chain tree theorem
मार्कोव श्रृंखलाओं के गणितीय सिद्धांत में, मार्कोव श्रृंखला वृक्ष प्रमेय सीमित रूप से कई अवस्थाओं के साथ मार्कोव श्रृंखला के स्थिर वितरण के लिए एक अभिव्यक्ति है। यह प्रत्येक पेड़ के लिए एक सकारात्मक संयोजन के साथ मार्कोव श्रृंखला के जड़ों से फैले पेड़ों के लिए शब्दों का सारांश देता है। मार्कोव चेन ट्री थ्योरम एक ग्राफ के फैले हुए पेड़ों की गिनती पर किरचॉफ के प्रमेय से निकटता से संबंधित है, जिससे इसे प्राप्त किया जा सकता है। यह पहली बार थर्मोडायनामिक्स में उत्पन्न होने वाली कुछ मार्कोव श्रृंखलाओं के लिए कहा गया था, और एक पक्षपाती सिक्के की संभावना के सीमित-स्मृति अनुमान में एक अनुप्रयोग से प्रेरित होकर पूरी तरह से साबित हुआ। एक परिमित मार्कोव श्रृंखला में अवस्थाओं का एक सीमित समूह होता है, और एक राज्य से दूसरे राज्य में बदलने की एक संक्रमण संभावना होती है, जैसे कि प्रत्येक राज्य के लिए निवर्तमान संक्रमण संभावनाओं का योग एक होता है। राज्य के प्रारंभिक चयन से (जो इस समस्या के लिए अप्रासंगिक साबित होता है), प्रत्येक क्रमिक राज्य को पिछले राज्य से संक्रमण संभावनाओं के अनुसार यादृच्छिक रूप से चुना जाता है। एक मार्कोव श्रृंखला को तब अपरिवर्तनीय कहा जाता है जब प्रत्येक राज्य संक्रमण के कुछ अनुक्रम के माध्यम से हर दूसरे राज्य तक पहुंच सकता है, और अपेरियोडिक यदि, प्रत्येक राज्य के लिए, उस राज्य में शुरू होने और समाप्त होने वाले अनुक्रमों में चरणों की संभावित संख्या में सबसे बड़ा सामान्य भाजक है। एक अपरिवर्तनीय और अपेरियोडिक मार्कोव श्रृंखला में आवश्यक रूप से एक स्थिर वितरण होता है, जो इसकी अवस्थाओं पर एक संभाव्यता वितरण है जो स्थिति के प्रारंभिक विकल्प की परवाह किए बिना कई चरणों के बाद दी गई स्थिति में होने की संभावना का वर्णन करता है। मार्कोव श्रृंखला वृक्ष प्रमेय मार्कोव श्रृंखला की अवस्थाओं के लिए पेड़ों को फैलाने पर विचार करता है, जिन्हें पेड़ों के रूप में परिभाषित किया गया है, जो एक निर्दिष्ट जड़ की ओर निर्देशित हैं, जिसमें सभी निर्देशित किनारे दिए गए मार्कोव श्रृंखला के वैध संक्रमण हैं। यदि एक राज्य से दूसरे राज्य में संक्रमण की संभावना है, तो किनारे वाले वृक्ष का वजन उसकी संक्रमण संभावनाओं के उत्पाद के बराबर होने के लिए परिभाषित किया जाता हैः आइए उन सभी फैले हुए वृक्षों के समूह को दर्शाते हैं जिनकी जड़ में अवस्था होती है। फिर, मार्कोव श्रृंखला वृक्ष प्रमेय के अनुसार, अवस्था के लिए स्थिर संभावना पेड़ों के वजन के योग के समानुपाती होती है। अर्थात्, जहाँ सामान्यीकरण स्थिरांक सभी फैले हुए पेड़ों का योग है। संदर्भ मार्कोव वृक्ष के फैलाव को संसाधित करता है