Markov chain tree theorem
માર્કોવ સાંકળોના ગાણિતિક સિદ્ધાંતમાં, માર્કોવ સાંકળ વૃક્ષ પ્રમેય એ મર્યાદિત રીતે ઘણી સ્થિતિઓ સાથે માર્કોવ સાંકળના સ્થિર વિતરણ માટેની અભિવ્યક્તિ છે. તે દરેક વૃક્ષ માટે હકારાત્મક સંયોજન સાથે માર્કોવ સાંકળના મૂળમાં ફેલાયેલા વૃક્ષો માટેની શરતોનો સારાંશ આપે છે. માર્કોવ સાંકળ વૃક્ષ પ્રમેય ગ્રાફના ફેલાયેલા વૃક્ષોની ગણતરી પર કિર્ચોફના પ્રમેય સાથે નજીકથી સંબંધિત છે, જેમાંથી તે મેળવી શકાય છે. તે સૌપ્રથમ થર્મોડાયનેમિક્સમાં ઉદ્ભવતા ચોક્કસ માર્કોવ સાંકળો દ્વારા જણાવવામાં આવ્યું હતું, અને પક્ષપાતી સિક્કાની સંભાવનાના મર્યાદિત-મેમરી અંદાજમાં એપ્લિકેશન દ્વારા પ્રેરિત, દ્વારા સંપૂર્ણ સામાન્યતામાં સાબિત થયું હતું. મર્યાદિત માર્કોવ સાંકળમાં સ્થિતિઓનો મર્યાદિત સમૂહ હોય છે, અને રાજ્યથી રાજ્યમાં બદલવાની સંક્રમણ સંભાવના હોય છે, જેમ કે દરેક રાજ્ય માટે બહાર જવાની સંક્રમણ સંભાવનાઓનો સરવાળો એક થાય છે. રાજ્યની પ્રારંભિક પસંદગીમાંથી (જે આ સમસ્યા માટે અપ્રસ્તુત સાબિત થાય છે), દરેક ક્રમિક સ્થિતિ અગાઉની સ્થિતિમાંથી સંક્રમણની સંભાવનાઓ અનુસાર યાદૃચ્છિક રીતે પસંદ કરવામાં આવે છે. માર્કોવ સાંકળને ત્યારે ઈરીડ્યુસિબલ કહેવામાં આવે છે જ્યારે દરેક રાજ્ય સંક્રમણના અમુક ક્રમ દ્વારા દરેક અન્ય રાજ્ય સુધી પહોંચી શકે છે, અને જો, દરેક રાજ્ય માટે, તે સ્થિતિમાં શરૂ થતા અને સમાપ્ત થતા ક્રમમાં પગલાંની સંભવિત સંખ્યાઓમાં સૌથી મોટો સામાન્ય ભાજક હોય તો અપેરિયોડિક કહેવાય છે. ઈરીડ્યુસિબલ અને એપેરિયોડિક માર્કોવ સાંકળમાં આવશ્યકપણે સ્થિર વિતરણ હોય છે, જે તેની સ્થિતિઓ પર સંભાવના વિતરણ છે જે સ્થિતિની પ્રારંભિક પસંદગીને ધ્યાનમાં લીધા વિના, ઘણા પગલાઓ પછી આપેલ સ્થિતિ પર હોવાની સંભાવનાનું વર્ણન કરે છે. માર્કોવ સાંકળ વૃક્ષ પ્રમેય માર્કોવ સાંકળની સ્થિતિઓ માટે વૃક્ષોના ફેલાવાને ધ્યાનમાં લે છે, જેને વૃક્ષો તરીકે વ્યાખ્યાયિત કરવામાં આવે છે, જે નિયુક્ત મૂળ તરફ નિર્દેશિત હોય છે, જેમાં તમામ નિર્દેશિત ધાર આપેલ માર્કોવ સાંકળના માન્ય સંક્રમણો છે. જો રાજ્યમાંથી રાજ્યમાં સંક્રમણની સંભાવના હોય, તો ધાર સમૂહવાળા વૃક્ષનું વજન તેની સંક્રમણ સંભાવનાઓના ગુણાકાર જેટલું હોય તેવું વ્યાખ્યાયિત કરવામાં આવે છેઃ ચાલો તેમના મૂળમાં સ્થિતિ ધરાવતા તમામ ફેલાયેલા વૃક્ષોના સમૂહને સૂચવીએ. પછી, માર્કોવ સાંકળ વૃક્ષ પ્રમેય અનુસાર, સ્થિતિ માટેની સ્થિર સંભાવના મૂળ ધરાવતા વૃક્ષોના વજનના સરવાળાના પ્રમાણમાં હોય છે. એટલે કે, જ્યાં નોર્મલાઇઝિંગ કોન્સ્ટન્ટ એ તમામ ફેલાયેલા વૃક્ષોનો સરવાળો છે. માર્કોવ સ્પ્રેનિંગ ટ્રી પર પ્રક્રિયા કરે છે