मार्कोव श्रृंखला (अवशोषण)
मैंने अभी मार्कोव चेन सीखना शुरू किया है और मैं इस समस्या को हल करने के तरीके के बारे में स्पष्ट हूं
एक आदमी एक 40 मीटर ऊँची पहाड़ी पर एक बोल्डर लुढ़कता है। प्रत्येक मिनट, संभावना 1/3 के साथ वह बोल्डर को 1 मीटर ऊपर रोल करने का प्रबंधन करता है, जबकि प्रायिकता 2/3 के साथ बोल्डर 1 मीटर नीचे लुढ़कता है। यदि आदमी वर्तमान में शिखर की ओर आधा है, तो क्या संभावना है कि वह तलहटी में उतरने से पहले शिखर पर पहुंच जाएगा?
जवाब
मार्कोव चेन सिद्धांत का उपयोग करके इस समस्या को हल करना अधिक कठिन होगा : लेकिन अंतर्निहित अवधारणाएं इसे एक तरह से फ्रेम करने में मदद करेंगी जो एक सरल समाधान को स्वीकार करता है।
समस्या का निरूपण
सबसे मौलिक अवधारणा एक राज्य की है: हम इस स्थिति को 41 अलग-अलग पदों या "राज्यों" के संदर्भ में मॉडल कर सकते हैं, जो नीचे (ऊंचाई -40) से एक मीटर ऊंचाई के अंतराल पर स्थित है (ऊंचाई 0) पहाड। वर्तमान राज्य, पहाड़ी से आधा ऊपर, -20 की ऊँचाई है।
दूसरी मौलिक अवधारणा अतीत की घटनाओं से स्वतंत्रता की है: आगे क्या होता है इसकी संभावना केवल राज्य पर निर्भर करती है, न कि किसी भी विवरण पर कि आदमी वहां कैसे पहुंचा । नतीजतन, शिखर तक पहुंचने का मौका केवल राज्य पर निर्भर करता है। तदनुसार, यदि हम लिखते हैं$s$ एक राज्य के लिए, शिखर तक पहुंचने का मौका बस लिखा जा सकता है $p(s).$ हमें खोजने के लिए कहा जाता है $p(-20).$
किसी भी राज्य से $s$ के बीच $-40$ तथा $0$ वहां एक है $1/3$ मौका है कि $s+1$ अगला राज्य होगा और ए $2/3$ मौका है कि $s-1$अगला राज्य होगा सशर्त प्रायिकता के सबसे बुनियादी नियम तब लागू होते हैं
$$p(s) = (1/3)p(s+1) + (2/3)p(s-1) = \frac{p(s+1)+2p(s-1)}{3}.\tag{*}$$
समस्या को तैयार करने का अंतिम चरण समापन बिंदुओं, या "अवशोषित राज्यों" का इलाज करता है $s=0$ तथा $s=-40.$ यह स्पष्ट होना चाहिए कि
$$p(0)=1;\ p(-40)=0.\tag{**}$$
विश्लेषण
इस बिंदु पर काम दुर्जेय लग सकता है: कौन 40 समीकरणों के अनुक्रम को हल करना चाहता है? एक अच्छी समाधान विधि सभी समीकरणों को एक गणितीय वस्तु में जोड़ती है। लेकिन इससे पहले कि हम आगे बढ़ें, मुझे टिप्पणी करने की अनुमति दें कि आपको इस विश्लेषण का पालन करने की आवश्यकता नहीं है: यह जांचने के लिए पर्याप्त होगा कि अंतिम सूत्र (नीचे हाइलाइट किया गया) समस्या द्वारा स्थापित सभी स्थितियों को संतुष्ट करता है - और यह सिर्फ एक मामला है साधारण बीजगणित।
इस समय यह सामान्य समस्या को हल करने में सहायक है। मान लीजिए कि राज्यों का एक क्रम है$s=0,1,2,\ldots, n$ और वह प्रत्येक राज्य $s$ के बीच $1$ तथा $n-1$ के लिए संक्रमण $s-1$ संभाव्यता के साथ $p$ और करने के लिए $s+1$ संभाव्यता के साथ $1-p.$ सबके लिए $s$ चलो $a_s$ राज्य में पहुंचने का मौका हो $0$ राज्य मारने से पहले $n.$ (मैं पिछले गिरा दिया है "$p(-s)$"नोटेशन क्योंकि यह बहुत अधिक पी की ओर जाता है और मैंने अनुक्रमण राज्यों से नकारात्मक संख्याओं के साथ उन्हें सक्रिय संख्याओं के साथ अनुक्रमणित करने के लिए स्विच किया है।"
जैसा कि हमने देखा, $a_0=1,$ $a_n=0,$ और अन्यथा $a_{s} = pa_{s-1} + (1-p)a_{s+1}$("पुनरावृत्ति संबंध")। समीकरणों के इस सेट को एक बहुपद द्वारा बड़े करीने से एन्कोड किया गया है
$$P(t) = a_0 + a_1 t + a_2 t^2 + \cdots + a_n t^n = a_0 + \sum_{s=1}^{n} a_s t^s.$$
पुनरावृत्ति संबंध में प्लगिंग और फिर आम शक्तियों को एकत्रित करना $t$ (लिख रहे हैं $a_{n+1}=0$ सुविधा के लिए) देता है
$$\begin{aligned} P(t) &= a_0 + \sum_{s=1}^n \left[pa_{s-1} + (1-p)a_{s+1}\right]t^s \\ &= a_0 + p\sum_{s=1}^n a_{s-1} t^s + (1-p)\sum_{s=1}^n a_{s+1}t^s\\ &= a_0 + pt\sum_{s=1}^n a_{s-1} t^{s-1} + \frac{1-p}{t}\sum_{s=1}^n a_{s+1}t^{s+1}\\ &= a_0 + pt\sum_{s=0}^{n-1} a_{s} t^{s} + \frac{1-p}{t}\sum_{s=2}^{n+1} a_{s}t^{s}\\ &= a_0 + pt(P(t) - a_nt^n) + \frac{1-p}{t}(P(t) - a_0 - a_1t) \end{aligned}$$
यह बहुपद के लिए एक एकल समीकरण है$P$ (कम से कम तक $t^n;$ मैं किसी भी गुणांक की उपेक्षा करूंगा $t^n$या उच्चतर शक्तियां जो समीकरण को ठीक बनाने के लिए आवश्यक हो सकती हैं।) प्रारंभिक स्थिति का उपयोग करके इस समीकरण को थोड़ा सरल करें $a_0=1$ और के लिए हल $P$ लेना
$$P(t) = \frac{(1-p) + (-1 + (1-p)a_1)t}{pt^2 - t + (1-p)}.$$
अब हर गुणांक$P$ (अभी भी अज्ञात) संख्या के संदर्भ में व्यक्त किया जा सकता है $a_1.$ का मूल्य $a_1$ अंतिम स्थिति द्वारा निर्धारित किया जाता है $a_n=0.$
एक आंशिक सूत्र के रूप में दाहिने हाथ की ओर का विस्तार करके एक बंद सूत्र संभव है। यह देखने के लिए नीचे आता है
$$\frac{1}{pt^2 - t + (1-p)} = \frac{1}{1-2p}\left(\frac{1}{1-t} - \frac{\lambda}{1 - \lambda t}\right)$$
और ज्यामितीय श्रृंखलाओं के रूप में अंशों का विस्तार करना, दोनों फॉर्म में हैं
$$\frac{\rho}{1 - \rho t} = \rho + \rho^2 t + \rho^3 t^2 + \cdots$$
और अंश से गुणा करना $(1-p) + (-1 + (1-p)a_1)t$ प्राप्त करना $P(t).$ यह हर पद के लिए एक बंद सूत्र देता है $P(t)$ के एक समारोह के रूप में $a_1.$
के लिये $p\ne 1/2$ और लेखन $\lambda = p/(1-p)$ यह दृष्टिकोण सामान्य परिणाम देता है
$$a_s = \frac{\lambda^s - \lambda^n}{1 - \lambda^n}$$
के लिये $s=1, 2, \ldots, n$ (और यह काम करने के लिए होता है $s=0,$भी)। (कब$p=1/2,$ $\lambda=1$इस सूत्र को अपरिभाषित बनाता है। आप आसानी से इसे एक सरल सूत्र समझ सकते हैं, हालांकि, सीमा की सीमा को ले कर$a_s$ जैसा $\lambda\to 1$ L'Hopital के नियम के एकल अनुप्रयोग का उपयोग करना।)
जाँच के रूप में, यह स्पष्ट है कि यह सूत्र देता है $a_0=1$ तथा $a_n=0.$ यह सत्यापित करने के लिए बना हुआ है कि यह पुनरावृत्ति संबंध को संतुष्ट करता है, लेकिन यह दिखाने की बात है
$$\frac{\lambda^s - \lambda^n}{1 - \lambda^n} = a_s = pa_{s-1} + (1-p)a_{s+1} = p\frac{\lambda^{s-1} - \lambda^n}{1 - \lambda^n} + (1-p)\frac{\lambda^{s+1} - \lambda^n}{1 - \lambda^n},$$
जो सीधा है।
आवेदन
दी गई समस्या में $n=40,$ $p=1/3,$ और हमें खोजने के लिए कहा गया है $a_{20}.$ इसके फलस्वरूप $\lambda = (1/3)\,/\,(1-1/3) = 1/2$ तथा
$$a_{20} = \frac{2^{-20} - 2^{-40}}{1 - 2^{-40}} = 2^{-20} - 2^{-40} + 2^{-60} - 2^{-80} + \cdots.$$
दाहिने हाथ की तरफ विस्तार को पहले दो शब्दों के बाद समाप्त किया जा सकता है जब दोहरे सटीक फ्लोटिंग पॉइंट (जिसकी एक सटीक सटीकता होती है) में गणना की जाती है $52$ बाइनरी जगह), दे रहे हैं
$$a_{20} \approx 2^{-20} - 2^{-40} \approx 9.53673406911546\times 10^{-7};$$
एक लाख में एक से थोड़ा कम।
कल्पना कीजिए कि पहाड़ी पर चढ़ने वाली यात्रा में 41 राज्य शामिल हैं, प्रत्येक मीटर के लिए एक संभव है, इसलिए राज्य 0, 1, 3, ...., 40। संक्रमण संभाव्यता मैट्रिक्स तब 41x41 मैट्रिक्स बन जाता है, जो एक राज्य से दूसरे राज्य में जाने की विभिन्न संभावनाओं का प्रतिनिधित्व करता है। यह निम्नलिखित की तरह दिखता है:
0 1 2 -- 40
0 0 1 0 -- 0
1 2/3 0 1/3 -- 0
2 0 2/3 0 -- 0
| | | | -- |
| | | | -- |
40 0 0 0 -- 0
चलो इस मैट्रिक्स को बुलाओ P। हम राज्य में 20 में 20 मीटर की दूरी, दूसरे शब्दों के साथ कम से शुरू करते हैं, हम प्रत्येक राज्य में शुरू करने की संभावनाओं, कहा जाता है के साथ (41 तत्वों लंबे) एक वेक्टर के रूप में इस का प्रतिनिधित्व कर सकते u, u=[0,0, ... , 0, 1, 0 ... 0, 0]है, जहां 120 मीटर की दूरी पर शुरू की एक 100% संभावना का प्रतिनिधित्व ।
मैट्रिक्स गुणन, u*Pफिर टाइमस्टेप टी +1 पर अन्य सभी राज्यों में समाप्त होने की संभावनाएं बन जाती हैं । यदि हम इस मैट्रिक्स को बार-बार करना जारी रखते हैं u*P^t, जहां टी अनंतता की ओर जाता है, तो हम एक स्थिर स्थिति मैट्रिक्स पी * तक पहुंच जाएंगे। यह स्थिर स्थिति मैट्रिक्स अन्य सभी राज्यों में समाप्त होने की संभावनाओं का प्रतिनिधित्व करता है।
तो आपके मामले में, आप अपनी पसंद की प्रोग्रामिंग भाषा में इस मैट्रिक्स गुणन को कई बार करेंगे (उदाहरण। 100+), और आप बस ऊपर देखेंगे P[20,40], जो आपको 20 मीटर से शुरू होने और यह सब बनाने की संभावना देगा। पहाड़ी के ऊपर रास्ता!