मार्कोव श्रृंखला का संक्षिप्त परिचय

1998 में, लॉरेंस पेज, सर्गेई ब्रिन, राजीव मोटवानी और टेरी विनोग्राद ने "द पेजरैंक प्रशस्ति रैंकिंग: ब्रिंगिंग ऑर्डर टू द वेब" लेख प्रकाशित किया, जिसने अब प्रसिद्ध पेजरैंक एल्गोरिदम का वर्णन किया, जो Google की नींव बन गया। दो दशकों से कुछ कम समय के बाद, Google एक विशालकाय बन गया, और भले ही इसका एल्गोरिथ्म बहुत विकसित हो गया हो, पेजरैंक अभी भी Google रैंकिंग एल्गोरिदम का "प्रतीक" है (हालाँकि कुछ ही लोग वास्तव में बता सकते हैं कि एल्गोरिथम में आज कितना वजन है) ।

सैद्धांतिक दृष्टिकोण से, यह ध्यान रखना दिलचस्प है कि पेजरैंक एल्गोरिदम की मानक व्याख्याओं में से एक मार्कोव श्रृंखला की एक सरल लेकिन मौलिक अवधारणा पर आधारित है। लेख से हम देखेंगे कि मार्कोव चेन स्टोकेस्टिक मॉडलिंग के लिए शक्तिशाली उपकरण हैं जो किसी भी डेटा वैज्ञानिक के लिए उपयोगी हो सकते हैं। विशेष रूप से, हम ऐसे बुनियादी सवालों के जवाब देंगे: मार्कोव चेन क्या हैं, उनके पास क्या अच्छे गुण हैं और उनकी मदद से क्या किया जा सकता है?

संक्षिप्त समीक्षा

पहले खंड में, हम मार्कोव श्रृंखला को समझने के लिए आवश्यक मूल परिभाषाएँ देते हैं। दूसरे खंड में, हम एक सीमित स्थिति में मार्कोव श्रृंखला के विशेष मामले पर विचार करते हैं। तीसरे खंड में, हम मार्कोव श्रृंखला के कुछ प्राथमिक गुणों पर विचार करते हैं और कई छोटे उदाहरणों के साथ इन गुणों को चित्रित करते हैं। अंत में, चौथे खंड में, हम मार्कोव श्रृंखला को पेजरैंक एल्गोरिथ्म के साथ जोड़ते हैं और एक कृत्रिम उदाहरण के साथ देखते हैं कि मार्कोव श्रृंखला का उपयोग ग्राफ के नोड्स को रैंक करने के लिए कैसे किया जा सकता है।

नोट। इस पद को समझने के लिए संभाव्यता और रैखिक बीजगणित की मूल बातों के ज्ञान की आवश्यकता होती है। विशेष रूप से, निम्नलिखित अवधारणाओं का उपयोग किया जाएगा: सशर्त संभावना , eigenvector, और पूर्ण संभावना सूत्र ।

---

मार्कोव चेन क्या हैं?

यादृच्छिक चर और यादृच्छिक प्रक्रियाएं

मार्कोव श्रृंखला की अवधारणा को शुरू करने से पहले, आइए हम संक्षेप में मूल, लेकिन संभाव्यता सिद्धांत की महत्वपूर्ण अवधारणाओं को याद करते हैं।

सबसे पहले, गणित की भाषा के बाहर, एक यादृच्छिक चर एक्स एक मात्रा है जो एक यादृच्छिक घटना के परिणाम से निर्धारित होता है। इसका परिणाम एक संख्या (या "एक संख्या की समानता", उदाहरण के लिए, वैक्टर) या कुछ और हो सकता है। उदाहरण के लिए, हम एक रैंडम वेरिएबल को डाई रोल (संख्या) के परिणाम के रूप में या सिक्का टॉस के परिणाम के रूप में परिभाषित कर सकते हैं (संख्या नहीं, जब तक हम नामित नहीं करते हैं, उदाहरण के लिए, "ईगल" को 0 के रूप में, लेकिन "1 के रूप में" पूंछ)। हम यह भी उल्लेख करते हैं कि एक यादृच्छिक चर के संभावित परिणामों का स्थान असतत या निरंतर हो सकता है: उदाहरण के लिए, एक सामान्य यादृच्छिक चर निरंतर है, और एक पॉइसन यादृच्छिक चर असतत है।

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


विभिन्न प्रकार की यादृच्छिक प्रक्रियाएं (अंतरिक्ष / समय में असतत / निरंतर)।

मार्कोव संपत्ति और मार्कोव श्रृंखला

यादृच्छिक प्रक्रियाओं के प्रसिद्ध परिवार हैं: गाऊसी प्रक्रियाएं, पॉसन प्रक्रियाएं, ऑटोरेग्रेसिव मॉडल, चलती औसत मॉडल, मार्कोव चेन, और अन्य। इन व्यक्तिगत मामलों में से प्रत्येक में कुछ गुण होते हैं जो हमें बेहतर खोज और उन्हें समझने की अनुमति देते हैं।

गुणों में से एक जो यादृच्छिक प्रक्रिया के अध्ययन को बहुत सरल करता है वह मार्कोव संपत्ति है। यदि हम इसे बहुत ही अनौपचारिक भाषा में समझाते हैं, तो मार्कोव संपत्ति हमें बताती है कि यदि हम किसी निश्चित समय में कुछ यादृच्छिक प्रक्रिया द्वारा प्राप्त मूल्य को जानते हैं, तो हम प्रक्रिया के भविष्य के व्यवहार के बारे में कोई अतिरिक्त जानकारी प्राप्त नहीं करेंगे, जो आपके अतीत के बारे में अन्य जानकारी एकत्र करेंगे। अधिक गणितीय भाषा में: किसी भी क्षण में, वर्तमान और भूतपूर्व राज्यों के साथ एक प्रक्रिया के भविष्य के राज्यों का सशर्त वितरण केवल वर्तमान स्थिति पर निर्भर करता है, न कि पिछले राज्यों ( स्मृति की कमी की संपत्ति ) पर। मार्कोव संपत्ति के साथ एक यादृच्छिक प्रक्रिया को मार्कोव प्रक्रिया कहा जाता है।


मार्कोव संपत्ति का अर्थ है कि यदि हम एक निश्चित समय में वर्तमान स्थिति को जानते हैं, तो हमें अतीत से एकत्रित भविष्य के बारे में किसी भी अतिरिक्त जानकारी की आवश्यकता नहीं है।

इस परिभाषा के आधार पर, हम "असतत समय के साथ सजातीय मार्कोव श्रृंखला" की परिभाषा तैयार कर सकते हैं (बाद में सरलता के लिए हम उन्हें "मार्कोव चेन" कहेंगे)। मार्कोव श्रृंखला एक मार्कोव प्रक्रिया है जिसमें असतत समय और असतत राज्य स्थान होता है। तो, एक मार्कोव श्रृंखला राज्यों का एक असतत क्रम है, जिनमें से प्रत्येक को एक असतत राज्य स्थान (परिमित या अनंत) से लिया गया है, जो मार्कोव संपत्ति को संतुष्ट करता है।

गणितीय रूप से, हम मार्कोव श्रृंखला को निम्नानुसार निरूपित कर सकते हैं:


जहां समय के प्रत्येक क्षण में प्रक्रिया अपने मानों को असतत सेट E से लेती है, ऐसे


फिर मार्कोव संपत्ति का मतलब है कि हमारे पास है


फिर से ध्यान दें कि यह अंतिम सूत्र इस तथ्य को दर्शाता है कि कालक्रम के लिए (जहां मैं अभी और जहां मैं पहले था) अगले राज्य की संभावना वितरण (जहां मैं अगला होगा) वर्तमान स्थिति पर निर्भर करता है, लेकिन पिछले राज्यों पर नहीं।

नोट। इस परिचयात्मक पोस्ट में, हमने केवल असतत समय के साथ सरल सजातीय मार्कोव श्रृंखला के बारे में बात करने का फैसला किया। हालांकि, इसमें अमानवीय (समय पर निर्भर) मार्कोव श्रृंखला और / या निरंतर-समय श्रृंखलाएं भी हैं। इस लेख में हम मॉडल के ऐसे बदलावों पर विचार नहीं करेंगे। यह भी ध्यान देने योग्य है कि एक मार्कोव संपत्ति की उपरोक्त परिभाषा बेहद सरल है: सही गणितीय परिभाषा फ़िल्टरिंग की अवधारणा का उपयोग करती है, जो मॉडल के साथ हमारे परिचयात्मक परिचित से बहुत आगे जाती है।

हम एक मार्कोव श्रृंखला की यादृच्छिकता गतिशीलता की विशेषता है

पिछली उपधारा में, हम किसी भी मार्कोव श्रृंखला के अनुरूप सामान्य संरचना से परिचित हो गए। आइए देखें कि हमें इस तरह की यादृच्छिक प्रक्रिया का एक विशिष्ट "उदाहरण" सेट करने की आवश्यकता है।

सबसे पहले, हम ध्यान दें कि असतत समय के साथ एक यादृच्छिक प्रक्रिया की विशेषताओं का पूर्ण निर्धारण जो मार्कोव संपत्ति को संतुष्ट नहीं करता है वह मुश्किल हो सकता है: समय में किसी दिए गए बिंदु पर संभावना वितरण अतीत और / या भविष्य में एक या एक से अधिक क्षणों पर निर्भर हो सकता है। ये सभी संभावित समय निर्भरता संभावित रूप से एक प्रक्रिया परिभाषा के निर्माण को जटिल कर सकते हैं।

हालांकि, मार्कोव संपत्ति के कारण, मार्कोव श्रृंखला की गतिशीलता निर्धारित करने के लिए काफी सरल है। और वास्तव में। हमें केवल दो पहलुओं को निर्धारित करने की आवश्यकता है: प्रारंभिक संभावना वितरण (यानी, समय n = 0 पर संभाव्यता वितरण)


और संक्रमण संभावना मैट्रिक्स (जो हमें संभावनाएं देता है कि समय n + 1 पर राज्य किसी भी जोड़ी के राज्यों के लिए किसी अन्य राज्य के लिए अगला है), द्वारा निरूपित


यदि इन दो पहलुओं को जाना जाता है, तो प्रक्रिया की पूर्ण (संभावित) गतिशीलता स्पष्ट रूप से परिभाषित है। और वास्तव में, प्रक्रिया के किसी भी परिणाम की संभावना को तब चक्रीय रूप से गणना की जा सकती है।

उदाहरण: मान लें कि हम इस संभावना को जानना चाहते हैं कि प्रक्रिया के पहले 3 राज्यों में मान (s0, s1, s2) होंगे। यही है, हम संभावना की गणना करना चाहते हैं


यहां हम कुल संभावना के लिए सूत्र लागू करते हैं, जिसमें कहा गया है कि प्राप्त करने की संभावना (s0, s1, s2) s1 प्राप्त करने की संभावना से पहले s0 को गुणा करने की संभावना के बराबर है, यह देखते हुए कि हमने पहले s0 को s2 प्राप्त करने की संभावना से गुणा किया है, इस तथ्य को ध्यान में रखते हुए। हमें पहले क्रम में s0 और s1 मिला। गणितीय रूप से, इसे इस प्रकार लिखा जा सकता है


और फिर सरलीकरण का पता चला है, जो मार्कोव धारणा द्वारा निर्धारित किया गया है। और वास्तव में, लंबी श्रृंखलाओं के मामले में, हम बाद के राज्यों के लिए दृढ़ता से सशर्त संभावनाएं प्राप्त करते हैं। हालाँकि, मार्कोव श्रृंखला के मामले में, हम इस तथ्य का लाभ उठाकर इस अभिव्यक्ति को सरल बना सकते हैं


इस तरह से


चूंकि वे प्रक्रिया की संभाव्य गतिशीलता की पूरी तरह से विशेषता रखते हैं, कई जटिल घटनाओं की गणना केवल प्रारंभिक संभावना वितरण q0 और संक्रमण संभाव्यता मैट्रिक्स पी के आधार पर की जा सकती है। यह एक और बुनियादी संबंध का उल्लेख करने योग्य भी है: समय n + 1 पर संभाव्यता वितरण की अभिव्यक्ति, समय पर संभाव्यता वितरण के संबंध में व्यक्त

मार्कोव परिमित राज्य के स्थानों में जंजीर

मैट्रिक्स और ग्राफ प्रतिनिधित्व

यहां हम मानते हैं कि सेट E में संभावित राज्यों N की सीमित संख्या है:


फिर प्रारंभिक संभाव्यता वितरण को आकार N की एक पंक्ति वेक्टर q0 के रूप में वर्णित किया जा सकता है, और संक्रमण संभावनाओं को N के आकार N के मैट्रिक्स p के रूप में वर्णित किया जा सकता है, जैसे कि


इस संकेतन का लाभ यह है कि यदि हम पंक्ति सदिश qn के द्वारा n में चरण n में प्रायिकता वितरण को निरूपित करते हैं जैसे कि इसके घटक निर्दिष्ट हैं


तब सरल मैट्रिक्स संबंध संरक्षित होते हैं


(यहां हम प्रमाण पर विचार नहीं करेंगे, लेकिन इसे पुन: पेश करना बहुत सरल है)।


यदि हम दाईं ओर पंक्ति वेक्टर को गुणा करते हैं, जो कि संक्रमण प्रायिकता मैट्रिक्स द्वारा किसी निश्चित समय पर संभावना वितरण का वर्णन करता है, तो हमें अगली बार चरण में संभावना वितरण मिलता है।

इसलिए, जैसा कि हम देखते हैं, किसी दिए गए चरण से अगले तक संभाव्यता वितरण के परिवर्तन को केवल मैट्रिक्स पी द्वारा प्रारंभिक चरण की संभावनाओं की पंक्ति वेक्टर के सही गुणन के रूप में परिभाषित किया गया है। इसके अलावा, इसका मतलब है कि हमारे पास है


एक परिमित राज्य स्थान में मार्कोव श्रृंखला की यादृच्छिक गतिशीलता को आसानी से एक सामान्यीकृत उन्मुख ग्राफ के रूप में दर्शाया जा सकता है जैसे कि ग्राफ का प्रत्येक नोड एक राज्य है, और प्रत्येक जोड़ी राज्यों (ईआई, ईजे) के लिए ई से ईजे तक जाने वाली एक बढ़त मौजूद है यदि पी (ईआई, ईजे) )> 0। तब किनारे का मूल्य समान संभावना पी (ईआई, ईजे) होगा।

उदाहरण: हमारी साइट का एक पाठक

आइए एक सरल उदाहरण के साथ यह सब स्पष्ट करते हैं। किसी साइट पर एक काल्पनिक आगंतुक के रोजमर्रा के व्यवहार पर विचार करें। हर दिन उनकी 3 संभावित स्थितियां होती हैं: पाठक उस दिन (एन) साइट पर नहीं जाता है, पाठक साइट पर जाता है, लेकिन पूरी पोस्ट (वी) को नहीं पढ़ता है, और पाठक साइट पर जाकर एक पूरी पोस्ट (आर) पढ़ता है। तो, हमारे पास निम्नलिखित राज्य स्थान है:


मान लीजिए, पहले दिन, इस पाठक के पास केवल साइट तक पहुँचने का 50% मौका है और साइट पर जाने और कम से कम एक लेख पढ़ने का 50% मौका है। प्रारंभिक संभाव्यता वितरण का वर्णन करने वाला वेक्टर (n = 0) तब इस तरह दिखता है:


यह भी कल्पना कीजिए कि निम्नलिखित संभावनाएँ देखी जाती हैं:

• जब पाठक एक दिन नहीं जाता है, तो उसके अगले दिन 25% की यात्रा न करने की संभावना होती है, केवल 50% की संभावना उसे देखने के लिए और 25% यात्रा करने और लेख पढ़ने के लिए
• जब पाठक एक दिन साइट पर जाता है, लेकिन वह नहीं पढ़ता है, तो उसके पास अगले दिन फिर से यात्रा करने का 50% मौका होता है और लेख नहीं पढ़ा जाता है, और यात्रा करने और पढ़ने का 50% मौका होता है
• जब कोई पाठक एक ही दिन में किसी लेख पर जाता है और उसे पढ़ता है, तो उसके पास अगले दिन लॉग इन न करने का 33% मौका होता है (मुझे उम्मीद है कि इस पोस्ट का इतना असर नहीं होगा!) , केवल 33% साइट पर लॉग इन करने और 34% बार लेख को देखने और पढ़ने का मौका मिलता है !

फिर हमारे पास निम्नलिखित संक्रमण मैट्रिक्स है:


पिछली उपधारा से, हम जानते हैं कि इस पाठक के लिए अगले दिन प्रत्येक राज्य की संभावना की गणना कैसे करें (n = 1)


इस मार्कोव श्रृंखला की संभाव्य गतिकी का रेखांकन निम्न प्रकार से किया जा सकता है:


मार्कोव श्रृंखला के ग्राफ के रूप में प्रस्तुति, साइट पर हमारे आविष्कृत आगंतुक के व्यवहार को मॉडलिंग करती है।

मार्कोव श्रृंखला के गुण

इस खंड में, हम केवल मार्कोव श्रृंखला के कुछ सबसे बुनियादी गुणों या विशेषताओं के बारे में बात करेंगे। हम गणितीय विवरणों में नहीं जाएंगे, लेकिन मार्कोव श्रृंखला का उपयोग करने के लिए अध्ययन किए जाने वाले दिलचस्प बिंदुओं का एक संक्षिप्त अवलोकन प्रदान करेंगे। जैसा कि हमने देखा है, एक परिमित राज्य स्थान के मामले में, मार्कोव श्रृंखला को एक ग्राफ के रूप में दर्शाया जा सकता है। भविष्य में, हम कुछ गुणों की व्याख्या करने के लिए चित्रमय प्रतिनिधित्व का उपयोग करेंगे। हालांकि, यह मत भूलो कि ये गुण आवश्यक रूप से एक सीमित राज्य स्थान के मामले तक सीमित नहीं हैं।

विकृति, आवधिकता, अपरिवर्तनीयता और पुनर्प्राप्ति

इस उपधारा में, चलो एक राज्य या संपूर्ण मार्कोव श्रृंखला को चिह्नित करने के कई क्लासिक तरीकों से शुरू करते हैं।

सबसे पहले, हम उल्लेख करते हैं कि मार्कोव श्रृंखला अनिर्णायक है यदि किसी अन्य राज्य से किसी भी राज्य तक पहुंचना संभव है (यह आवश्यक नहीं है कि एक चरण में)। यदि राज्य स्थान परिमित है और श्रृंखला को एक ग्राफ के रूप में दर्शाया जा सकता है, तो हम कह सकते हैं कि एक इंडोकोमायलेट मार्कोव श्रृंखला का ग्राफ दृढ़ता से जुड़ा हुआ है (ग्राफ सिद्धांत)।


अनिर्णय (चिड़चिड़ापन) की संपत्ति का चित्रण। बाईं ओर की श्रृंखला को छोटा नहीं किया जा सकता है: 3 या 4 से हम 1 या 2 में नहीं मिल सकते। दाईं ओर की श्रृंखला (एक किनारे को जोड़ा जाता है) को छोटा किया जा सकता है: प्रत्येक राज्य को किसी अन्य से पहुंचा जा सकता है।

एक राज्य में एक पीरियड k होता है, यदि इसे छोड़ने पर, इस राज्य में किसी भी वापसी के लिए, समय कदमों की संख्या कई k होती है (k, वापसी रास्तों के सभी संभावित लंबाई का सबसे बड़ा सामान्य कारक है)। यदि k = 1 है, तो वे कहते हैं कि राज्य aperiodic है, और संपूर्ण मार्कोव श्रृंखला aperiodic है यदि इसके सभी राज्य aperiodic हैं। एक चिड़चिड़ा मार्कोव श्रृंखला के मामले में, हम यह भी उल्लेख कर सकते हैं कि यदि एक राज्य एपेरियोडिक है, तो अन्य सभी भी एपेरियोडिक हैं।


आवधिक संपत्ति का चित्रण। बाईं ओर की श्रृंखला k = 2 के साथ आवधिक है: किसी भी राज्य को छोड़ते समय, इसे वापस करने के लिए हमेशा चरण 2 की संख्या की आवश्यकता होती है। दाईं ओर की श्रृंखला में 3 की अवधि होती है।

एक राज्य अपरिवर्तनीय है यदि, राज्य छोड़ने पर, एक गैर-शून्य संभावना है कि हम कभी भी इसे वापस नहीं करेंगे। इसके विपरीत, एक राज्य को वापस करने योग्य माना जाता है यदि हम जानते हैं कि राज्य छोड़ने के बाद हम भविष्य में संभावना 1 (यदि यह अपरिवर्तनीय नहीं है) के साथ वापस आ सकते हैं।


वापसी / अपरिवर्तनीय संपत्ति का चित्रण। बाईं ओर की श्रृंखला में निम्नलिखित गुण हैं: 1, 2 और 3 अपरिवर्तनीय हैं (इन बिंदुओं को छोड़ते समय हम पूरी तरह से सुनिश्चित नहीं हो सकते हैं कि हम उनके पास लौट आएंगे) और 3 की अवधि है, और 4 और 5 वापसी योग्य हैं (इन बिंदुओं को छोड़ते समय हम बिल्कुल निश्चित हैं किसी दिन हम उनके पास लौटेंगे) और 2 की अवधि है। दाईं ओर की श्रृंखला में एक और रिब है, जिससे पूरी श्रृंखला वापस आ सकती है और एपेरियोडिक है।

वापसी राज्य के लिए, हम औसत रिटर्न समय की गणना कर सकते हैं, जो कि राज्य छोड़ने पर अपेक्षित वापसी समय है । ध्यान दें कि वापसी की संभावना 1 भी है, इसका मतलब यह नहीं है कि वापसी का समय निश्चित है। इसलिए, सभी रिटर्न स्टेट्स के बीच, हम पॉजिटिव रिटर्न स्टेट्स (एक परिमित अपेक्षित रिटर्न टाइम के साथ) और जीरो रिटर्न स्टेट्स (अनंत अपेक्षित रिटर्न टाइम के साथ) के बीच अंतर कर सकते हैं।

स्थिर वितरण, सीमांत व्यवहार और ergodicity

इस उपधारा में, हम उन गुणों पर विचार करते हैं जो मार्कोव श्रृंखला द्वारा वर्णित (यादृच्छिक) गतिशीलता के कुछ पहलुओं की विशेषता रखते हैं।

राज्य स्पेस ई पर संभावना वितरण prob को स्थिर वितरण कहा जाता है यदि यह अभिव्यक्ति को संतुष्ट करता है


चूंकि हमारे पास है


फिर स्थिर वितरण अभिव्यक्ति को संतुष्ट करता है


परिभाषा के अनुसार, स्थिर संभावना वितरण समय के साथ नहीं बदलता है। यही है, यदि प्रारंभिक वितरण q स्थिर है, तो यह समय के सभी चरणों में समान होगा। यदि राज्य स्थान परिमित है, तो p को एक मैट्रिक्स के रूप में और, एक पंक्ति वेक्टर के रूप में प्रतिनिधित्व किया जा सकता है, और फिर हम प्राप्त करते हैं


यह फिर से इस तथ्य को व्यक्त करता है कि स्थिर संभावना वितरण समय के साथ नहीं बदलता है (जैसा कि हम देखते हैं, पी द्वारा दाईं ओर संभावना वितरण को गुणा करने से हमें समय के अगले चरण में संभावना वितरण की गणना करने की अनुमति मिलती है)। ध्यान रखें कि एक अविशिष्ट प्रयोजनीय मार्कोव श्रृंखला में एक स्थिर संभाव्यता वितरण होता है, यदि और केवल यदि इसका एक राज्य सकारात्मक प्रतिफल हो।

स्टेशनरी संभाव्यता वितरण से संबंधित एक और दिलचस्प संपत्ति इस प्रकार है। यदि श्रृंखला सकारात्मक रिटर्न है (यानी, इसमें एक स्थिर वितरण है) और एपेरियोडिक, तो, जो भी प्रारंभिक संभावनाएं हैं, श्रृंखला की संभाव्यता वितरण समय के अंतराल के रूप में परिवर्तित होती है: एक स्थिर वितरण के रूप में। सामान्य तौर पर, इसे इस तरह लिखा जा सकता है:


, : ( ) .

, — , . , , «», . , f(.), E ( , , ). , ( ). n-


हम सेट ई पर फ़ंक्शन एफ के औसत मूल्य की गणना भी कर सकते हैं, स्थिर वितरण (स्थानिक औसत) द्वारा भारित, जिसे निरूपित किया जाता है।


तब एर्गोडिक प्रमेय हमें बताता है कि जब प्रक्षेपवक्र असीम रूप से लंबा हो जाता है, तो समय औसत स्थानिक औसत (स्थिर वितरण द्वारा भारित) के बराबर होता है। एर्गोडिसिटी प्रॉपर्टी को इस प्रकार लिखा जा सकता है:


दूसरे शब्दों में, इसका अर्थ है कि पहले की सीमा में प्रक्षेपवक्र का व्यवहार महत्वहीन हो जाता है और लौकिक औसत की गणना करते समय केवल दीर्घकालिक स्थिर व्यवहार महत्वपूर्ण होता है।

साइट रीडर के साथ उदाहरण पर वापस जाते हैं

. , , .

, , R ( « »). , : , , ? , .




, m(R,R). , R,


हालाँकि, इस अभिव्यक्ति के लिए आवश्यक है कि m (R, R) की गणना के लिए हम m (N, R) और m (V, R) को जानें। इन दो मात्राओं को एक समान तरीके से व्यक्त किया जा सकता है:


तो, हमें 3 अज्ञात के साथ 3 समीकरण मिले और उन्हें हल करने के बाद हमें m (N, R) = 2.67, m (V, R) = 2.00 और m (R, R) = 2.54 मिला। राज्य आर में लौटने का औसत समय 2.54 है। यही है, रैखिक बीजगणित का उपयोग करते हुए, हम राज्य आर में लौटने के औसत समय (साथ ही एन से आर के संक्रमण का औसत समय और वी से आर के संक्रमण का औसत समय) की गणना करने में सक्षम थे।

इस उदाहरण के साथ समाप्त करने के लिए, आइए देखें कि मार्कोव श्रृंखला का स्थिर वितरण क्या होगा। स्थिर वितरण को निर्धारित करने के लिए, हमें रैखिक बीजगणित के निम्नलिखित समीकरण को हल करना होगा:


p, 1. , :


.

, π( R ) = 1/m(R,R), , ( ).

, , ( ). , , , π(N) , , π(V) , , , π® , . , , , () :


3 (, ) ().

: PageRank

PageRank! , , PageRank, , , . , .

-

PageRank : ( , , , - ) ?

, PageRank . , . , , (, , , ). .

: — , ( , ), . , ( ), « » . , ( ) , .

PageRank : ( , , ). PageRank.

, . , - 7 , 1 7, .


. , «» ( « »), : K ( K ) 1/K. :


0.0 ".". , , , . , ,


ऐसा करने से, हमें प्रत्येक पृष्ठ के लिए निम्न पेजरेंक मान (स्थिर वितरण मान) मिलते हैं


पेजरैंक मान 7 पृष्ठों के हमारे कृत्रिम उदाहरण के लिए गणना की जाती है।

फिर इस छोटी वेबसाइट की पेजरैंक रैंकिंग 1> 7> 4> 2> 5 = 6> 3 है।

---

निष्कर्ष

इस लेख से मुख्य निष्कर्ष:

• यादृच्छिक प्रक्रियाएं यादृच्छिक चर का समूह होती हैं जिन्हें अक्सर समय से अनुक्रमित किया जाता है (सूचक अक्सर असतत या निरंतर समय का संकेत देते हैं)
• एक यादृच्छिक प्रक्रिया के लिए, मार्कोव संपत्ति का मतलब है कि किसी दिए गए वर्तमान के लिए, भविष्य की संभावना अतीत पर निर्भर नहीं करती है (इस संपत्ति को "स्मृति की कमी" भी कहा जाता है)
• असतत-समय मार्कोव श्रृंखला मार्कोव संपत्ति को संतुष्ट करने वाले असतत-समय सूचक के साथ यादृच्छिक प्रक्रियाएं हैं
• ( , …)
• PageRank ( ) -, ; ( , , , )

, , . , , ( , , ), ( - ), ( ), ( ), .

, , , , . , , .