सशर्त संभावनाओं की विधि: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
गणित और [[कंप्यूटर विज्ञान]] में, वांछित संयोजक गुणों के साथ गणितीय वस्तुओं के अस्तित्व को साबित करने के लिए संभाव्य पद्धति का उपयोग किया जाता है। प्रमाण संभाव्य हैं - वे यह दिखाकर काम करते हैं कि कुछ संभाव्यता वितरण से चुनी गई यादृच्छिक वस्तु में सकारात्मक संभावना के साथ वांछित गुण होते हैं। नतीजतन, वे गैर-रचनात्मक प्रमाण हैं - वे वांछित वस्तुओं की गणना के लिए कुशल विधि का स्पष्ट रूप से वर्णन नहीं करते हैं।
गणित और [[कंप्यूटर विज्ञान|'''कंप्यूटर विज्ञान''']] में, वांछित संयोजक गुणों के साथ गणितीय वस्तुओं के अस्तित्व को प्रमाणित करने के लिए '''प्रोबबिलिस्टिक मेथड'''  का उपयोग किया जाता है। अतः यह प्रमाण प्रोबबिलिस्टिक  हैं - वे यह दिखाकर कार्य  करते हैं कि कुछ प्रोबबिलिस्टिक डिस्ट्रीब्यूशन  से चुनी गई रेनडोमाइसड  वस्तु में पोसिटिव संभावना के साथ वांछित गुण होते हैं। फलस्वरूप, वे नॉन-कॉनस्ट्रूकटिव  प्रमाण हैं - वे वांछित वस्तुओं की गणना के लिए कुशल विधि का स्पष्ट रूप से वर्णन नहीं करते हैं।


सशर्त संभावनाओं की विधि {{harv|Spencer|1987}}, {{harv|Raghavan|1988}} ऐसे प्रमाण को, बहुत सटीक अर्थ में, कुशल नियतात्मक एल्गोरिदम में परिवर्तित करता है, जो वांछित गुणों के साथ किसी वस्तु की गणना करने की गारंटी देता है। यानी विधि यादृच्छिकीकरण प्रमाण. मूल विचार यादृच्छिक प्रयोग में प्रत्येक यादृच्छिक विकल्प को नियतात्मक विकल्प से प्रतिस्थापित करना है, ताकि अब तक के विकल्पों को देखते हुए विफलता की सशर्त संभावना को 1 से नीचे रखा जा सके।
मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक {{harv|Spencer|1987}}, और {{harv|राघवन|1988}} इस प्रकार के प्रमाण का, अधिक स्पष्ट अर्थ है, कुशल डेटरमिनिस्टिक एल्गोरिदम में परिवर्तित करता है, जो वांछित गुणों के साथ किसी वस्तु की गणना करने का  प्रमाण  देता है। अर्थात  विधि रेनडोमाइसड प्रमाण. मूल विचार रेनडोमाइसड  प्रयोग में प्रत्येक रैंडम चॉइस  को डेटरमिनिस्टिक चॉइस से प्रतिस्थापित करना है, जिससे  अब तक के विकल्पों को देखते हुए विफलता की कंडीशनल प्रोबबिलिस्टिक को 1 से नीचे रखा जा सकता है।


यह विधि यादृच्छिक राउंडिंग के संदर्भ में विशेष रूप से प्रासंगिक है (जो सन्निकटन एल्गोरिदम को डिजाइन करने के लिए संभाव्य विधि का उपयोग करती है)।
यह विधि रेनडोमाइसड  राउंडिंग के संदर्भ में विशेष रूप से प्रासंगिक है (जो अप्प्रोक्सीमेसन एल्गोरिदम को डिजाइन करने के लिए प्रोबबिलिस्टिक विधि का उपयोग करती है)।


सशर्त संभावनाओं की पद्धति को लागू करते समय, तकनीकी शब्द निराशावादी अनुमानक प्रमाण के अंतर्निहित वास्तविक सशर्त संभाव्यता (या सशर्त अपेक्षा) के स्थान पर उपयोग की जाने वाली मात्रा को संदर्भित करता है।
कंडीशनल प्रोबबिलिस्टिक की पद्धति को प्रयुक्त  करते समय, तकनीकी शब्द पेस्सिमिस्टिक एस्टीमेटर प्रमाण के अंतर्निहित वास्तविक कंडीशनल प्रोबबिलिस्टिक  (या कंडीशनल अपेक्षा) के स्थान पर उपयोग की जाने वाली मात्रा को संदर्भित करता है।


== सिंहावलोकन ==
== अवलोकन ==
{{harv|Raghavan|1988}} यह विवरण देता है:
{{harv|राघवन|1988}} यह विवरण देता है:


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


(राघवन यादृच्छिक पूर्णांकन के संदर्भ में विधि पर चर्चा कर रहे हैं, लेकिन यह सामान्य रूप से संभाव्य विधि के साथ काम करता है।)
(राघवन रेनडोमाइसड  पूर्णांकन के संदर्भ में विधि पर चर्चा कर रहे हैं, किन्तु  यह सामान्य रूप से प्रोबबिलिस्टिक विधि के साथ कार्य  करता है।)


[[File:Method of conditional probabilities.png|thumb|450px|right|सशर्त संभावनाओं की विधि]]विधि को संभाव्य प्रमाण पर लागू करने के लिए, प्रमाण में यादृच्छिक रूप से चुनी गई वस्तु को यादृच्छिक प्रयोग द्वारा चुना जाना चाहिए जिसमें छोटे यादृच्छिक विकल्पों का अनुक्रम शामिल हो।
[[File:Method of conditional probabilities.png|thumb|450px|right|मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक]]इस प्रकार से विधि को प्रोबबिलिस्टिक  प्रमाण पर प्रयुक्त  करने के लिए, प्रमाण में रेनडोमाइसड  रूप से चुनी गई है  और वस्तु को रेनडोमाइसड  प्रयोग द्वारा चुना जाना चाहिए जिसमें छोटे रैंडम चॉइस का अनुक्रम सम्मिलित  होती है।


सिद्धांत को स्पष्ट करने के लिए यहां छोटा सा उदाहरण दिया गया है।
अतः सिद्धांत को स्पष्ट करने के लिए यहां छोटा सा उदाहरण दिया गया है।


: लेम्मा: ''तीन सिक्कों को उछालना संभव है ताकि पूंछों की संख्या कम से कम 2 हो।''
: लेम्मा: ''तीन सिक्कों को उछालना संभव है जिससे  टेल्स  की संख्या कम से कम 2 हो।''
: ''संभाव्य प्रमाण।'' यदि तीन सिक्कों को यादृच्छिक रूप से उछाला जाता है, तो पूंछों की अपेक्षित संख्या 1.5 है। इस प्रकार, कुछ परिणाम (सिक्के उछालने का तरीका) होना चाहिए ताकि पूंछों की संख्या कम से कम 1.5 हो। चूँकि पूँछों की संख्या पूर्णांक है, ऐसे परिणाम में कम से कम 2 पूँछें होती हैं। ''प्रश्न''
: ''प्रोबबिलिस्टिक  प्रमाण'' यदि तीन सिक्कों को रेनडोमाइसड  रूप से उछाला जाता है, तो टेल्स  की अपेक्षित संख्या 1.5 है। इस प्रकार, कुछ परिणाम (सिक्के उछालने का विधि ) होना चाहिए जिससे  टेल्स  की संख्या कम से कम 1.5 हो। चूँकि टेल्स की संख्या पूर्णांक है, ऐसे परिणाम में कम से कम 2 टेल्स  होती हैं। ''प्रश्न''


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


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


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


:: ''वर्तमान स्थिति को देखते हुए विफलता की सशर्त संभावना 1 से कम है।''
मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक रेनडोमाइसड  प्रयोग में रेनडोमाइसड  रूट-टू-लीफ वॉक को डेटरमिनिस्टिक रूट-टू-लीफ वॉक द्वारा प्रतिस्थापित करती है, जहां प्रत्येक चरण को निम्नलिखित अपरिवर्तनीय बनाए रखने के लिए चुना जाता है:


इस तरह, लेबल 0 वाले पत्ते पर पहुंचने की गारंटी है, यानी सफल परिणाम।
:: ''वर्तमान स्थिति को देखते हुए विफलता की कंडीशनल प्रोबबिलिस्टिक 1 से कम है।''


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


== दक्षता ==
== दक्षता ==


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


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


दुर्भाग्य से, अधिकांश अनुप्रयोगों में, विफलता की सशर्त संभावना की कुशलता से गणना करना आसान नहीं है। इससे निपटने के लिए दो मानक और संबंधित तकनीकें हैं:
दुर्भाग्य से, अधिकांश अनुप्रयोगों में, विफलता की कंडीशनल प्रोबबिलिस्टिक की कुशलता से गणना करना सरल  नहीं है। इससे निपटने के लिए दो मानक और संबंधित तकनीकें हैं:


* 'सशर्त अपेक्षा का उपयोग करना:' कई संभाव्य प्रमाण इस प्रकार काम करते हैं: वे स्पष्ट रूप से यादृच्छिक चर Q को परिभाषित करते हैं, दिखाते हैं कि (i) Q की अपेक्षा अधिकतम (या कम से कम) कुछ सीमा मूल्य है, और (ii) किसी भी परिणाम जहां Q अधिकतम (कम से कम) इस सीमा पर है, परिणाम सफल है। तब (i) का अर्थ है कि परिणाम मौजूद है जहां Q अधिकतम (कम से कम) सीमा है, और इसका और (ii) का अर्थ है कि सफल परिणाम है। (उपरोक्त उदाहरण में, क्यू पूंछों की संख्या है, जो कम से कम सीमा 1.5 होनी चाहिए। कई अनुप्रयोगों में, क्यू किसी दिए गए परिणाम में होने वाली बुरी घटनाओं (जरूरी नहीं कि असंबद्ध) की संख्या है, जहां प्रत्येक बुरी घटना मेल खाती है तरह से प्रयोग विफल हो सकता है, और घटित होने वाली बुरी घटनाओं की अपेक्षित संख्या 1 से कम है।)
* 'कंडीशनल अपेक्षा का उपयोग करना:' अनेक प्रोबबिलिस्टिक प्रमाण इस प्रकार कार्य  करते हैं: वे स्पष्ट रूप से रेनडोमाइसड  वेरिएबल Q को परिभाषित करते हैं, दिखाते हैं कि (i) Q की अपेक्षा अधिकतम (या कम से कम) कुछ सीमा मूल्य है, और (ii) किसी भी परिणाम जहां Q अधिकतम (कम से कम) इस सीमा पर है, परिणाम सफल है। तब (i) का अर्थ है कि परिणाम उपस्तिथ  है जहां Q अधिकतम (कम से कम) सीमा है, और इसका और (ii) का अर्थ है कि सफल परिणाम है। (उपरोक्त उदाहरण में, Q  टेल्स  की संख्या है, जो कम से कम सीमा 1.5 होनी चाहिए। अनेक अनुप्रयोगों में, Q  किसी दिए गए परिणाम में होने वाली बैड इवेंट्स  (आवश्यक  नहीं कि असंबद्ध) की संख्या है, जहां प्रत्येक बैड इवेंट्स  मेल खाती है तरह से प्रयोग विफल हो सकता है, और घटित होने वाली बैड इवेंट्स  की अपेक्षित संख्या 1 से कम है।)


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


* 'निराशावादी अनुमानक का उपयोग करना:' कुछ मामलों में, मात्रा Q की सटीक सशर्त अपेक्षा के लिए प्रॉक्सी के रूप में, उचित रूप से तंग सीमा का उपयोग किया जाता है जिसे निराशावादी अनुमानक कहा जाता है। निराशावादी अनुमानक वर्तमान स्थिति का कार्य है। वर्तमान स्थिति को देखते हुए यह Q की सशर्त अपेक्षा के लिए ऊपरी (या निचला) होना चाहिए, और यह प्रयोग के प्रत्येक यादृच्छिक चरण के साथ अपेक्षा में गैर-बढ़ती (या गैर-घटती) होनी चाहिए। आमतौर पर, अच्छे निराशावादी अनुमानक की गणना मूल प्रमाण के तर्क को सटीक रूप से विखंडित करके की जा सकती है।
* पेस्सिमिस्टिक एस्टीमेटर  का उपयोग करना:' कुछ स्तिथि  में, मात्रा Q की स्पष्ट  कंडीशनल अपेक्षा के लिए प्रॉक्सी के रूप में, उचित रूप से टाइट सीमा का उपयोग किया जाता है जिसे पेस्सिमिस्टिक एस्टीमेटर कहा जाता है। पेस्सिमिस्टिक एस्टीमेटर वर्तमान स्थिति का कार्य है। वर्तमान स्थिति को देखते हुए यह Q की कंडीशनल अपेक्षा के लिए ऊपरी (या निचला) होना चाहिए, और यह प्रयोग के प्रत्येक रेनडोमाइसड  चरण के साथ अपेक्षा में गैर-बढ़ती (या गैर-घटती) होनी चाहिए। सामान्यतः, अच्छे पेस्सिमिस्टिक एस्टीमेटर की गणना मूल प्रमाण के तर्क को स्पष्ट  रूप से विखंडित करके की जा सकती है।


== सशर्त अपेक्षाओं का उपयोग करने वाला उदाहरण ==
== कंडीशनल अपेक्षाओं का उपयोग करने वाला उदाहरण ==


यह उदाहरण सशर्त अपेक्षा का उपयोग करके सशर्त संभावनाओं की विधि को प्रदर्शित करता है।
यह उदाहरण कंडीशनल अपेक्षा का उपयोग करके मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक को प्रदर्शित करता है।


=== मैक्स-कट लेम्मा ===
=== मैक्स-कट लेम्मा ===


किसी भी अप्रत्यक्ष ग्राफ़ (असतत गणित) जी = (वी, ई) को देखते हुए, [[अधिकतम कटौती]] समस्या ग्राफ़ के प्रत्येक शीर्ष को दो रंगों (जैसे काले या सफेद) में से के साथ रंगना है ताकि किनारों की संख्या को अधिकतम किया जा सके जिनके अंतिम बिंदु हैं अलग - अलग रंग। (कहो ऐसी धार कटी है।)
किसी भी अप्रत्यक्ष ग्राफ़ (असतत गणित) G = (V, E) को देखते हुए, [[अधिकतम कटौती|अधिकतम कट]] समस्या ग्राफ़ के प्रत्येक शीर्ष को दो रंगों (जैसे काले या सफेद) में से के साथ रंगना है जिससे  किनारों की संख्या को अधिकतम किया जा सके जिनके अंतिम बिंदु हैं अलग - अलग रंग। (कहो ऐसी धार कटी है।)


'मैक्स-कट लेम्मा:' किसी भी ग्राफ G = (V, E) में, कम से कम |E|/2 किनारों को काटा जा सकता है।
'मैक्स-कट लेम्मा:' किसी भी ग्राफ G = (V, E) में, कम से कम |E|/2 किनारों को काटा जा सकता है।


'संभाव्य प्रमाण।' गोरा सिक्का उछालकर प्रत्येक शीर्ष को काला या सफेद रंग दें। गणना के अनुसार, ई में किसी भी किनारे ई के लिए, इसके कटने की संभावना 1/2 है। इस प्रकार, अपेक्षित मान#रैखिकता के अनुसार, काटे गए किनारों की अपेक्षित संख्या |E|/2 है। इस प्रकार, ऐसा रंग मौजूद है जो कम से कम |E|/2 किनारों को काटता है। QED
'प्रोबबिलिस्टिक  प्रमाण।' सफेद सिक्का उछालकर प्रत्येक शीर्ष को काला या सफेद रंग दें। गणना के अनुसार, ''E'' में किसी भी किनारे ''E'' के लिए, इसके कटने की संभावना 1/2 है। इस प्रकार, अपेक्षित मान या रैखिकता के अनुसार, काटे गए किनारों की अपेक्षित संख्या |E|/2 है। इस प्रकार, ऐसा रंग उपस्तिथ  है जो कम से कम |E|/2 किनारों को क्यूईडी काटता है।  


=== सशर्त अपेक्षाओं के साथ सशर्त संभावनाओं की विधि ===
=== कंडीशनल अपेक्षाओं के साथ मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक ===


सशर्त संभावनाओं की विधि को लागू करने के लिए, पहले यादृच्छिक प्रयोग को छोटे यादृच्छिक चरणों के अनुक्रम के रूप में मॉडल करें। इस मामले में प्रत्येक चरण को किसी विशेष शीर्ष के लिए रंग की पसंद के रूप में मानना ​​स्वाभाविक है (इसलिए |V| चरण हैं)।
मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक को प्रयुक्त  करने के लिए, पहले रेनडोमाइसड  प्रयोग को छोटे रेनडोमाइसड  चरणों के अनुक्रम के रूप में मॉडल किया जाता है। इस स्तिथि  में प्रत्येक चरण को किसी विशेष शीर्ष के लिए रंग की चॉइस  के रूप में मानना ​​स्वाभाविक है (इसलिए |V| चरण हैं)।


इसके बाद, प्रत्येक चरण में यादृच्छिक विकल्प को नियतात्मक विकल्प से बदलें, ताकि विफलता की सशर्त संभावना को बनाए रखा जा सके, अब तक रंगे गए शीर्षों को 1 से नीचे दिया गया है। (यहां विफलता का मतलब है कि अंततः |E|/2 से कम किनारे काटे गए हैं।)
इसके पश्चात , प्रत्येक चरण में रैंडम चॉइस  को डेटरमिनिस्टिक चॉइस  से परिवर्तन , जिससे  विफलता की कंडीशनल प्रोबबिलिस्टिक को बनाए रखा जा सके, अब तक रंगे गए शीर्षों को 1 से नीचे दिया गया है। (यहां विफलता का अर्थ है कि अंततः |E|/2 से कम किनारे काटे गए हैं।)


इस मामले में, विफलता की सशर्त संभावना की गणना करना आसान नहीं है। वास्तव में, मूल प्रमाण सीधे विफलता की संभावना की गणना नहीं करता था; इसके बजाय, सबूत ने यह दिखाकर काम किया कि कटे हुए किनारों की अपेक्षित संख्या कम से कम |ई|/2 थी।
इस स्तिथि  में, विफलता की कंडीशनल प्रोबबिलिस्टिक की गणना करना सरल  नहीं है। वास्तव में, मूल प्रमाण सीधे विफलता की संभावना की गणना नहीं करता था; इसके अतिरिक्त, प्रमाण ने यह दिखाकर कार्य  किया कि कटे हुए किनारों की अपेक्षित संख्या कम से कम |ई|/2 थी।


माना यादृच्छिक चर Q कटे हुए किनारों की संख्या है। विफलता की सशर्त संभावना को 1 से नीचे रखने के लिए, Q की सशर्त अपेक्षा को सीमा |E|/2 पर या उससे ऊपर रखना पर्याप्त है। (ऐसा इसलिए है क्योंकि जब तक Q की सशर्त अपेक्षा कम से कम |E|/2 है, तब तक कुछ अभी भी पहुंच योग्य परिणाम होना चाहिए जहां Q कम से कम |E|/2 है, इसलिए ऐसे परिणाम तक पहुंचने की सशर्त संभावना सकारात्मक है।) Q की सशर्त अपेक्षा को |E|/2 या उससे ऊपर रखने के लिए, एल्गोरिदम, प्रत्येक चरण में, विचाराधीन शीर्ष को रंग देगा ताकि Q की परिणामी सशर्त अपेक्षा को अधिकतम किया जा सके। यह पर्याप्त है, क्योंकि कुछ बच्चे होंगे जिनकी सशर्त अपेक्षा कम से कम वर्तमान स्थिति है की सशर्त अपेक्षा (और इस प्रकार कम से कम |ई|/2)।
माना रेनडोमाइसड  वेरिएबल Q कटे हुए किनारों की संख्या है। विफलता की कंडीशनल प्रोबबिलिस्टिक को 1 से नीचे रखने के लिए, Q की कंडीशनल अपेक्षा को सीमा |E|/2 पर या उससे ऊपर रखना पर्याप्त है। (ऐसा इसलिए है क्योंकि जब तक Q की कंडीशनल अपेक्षा कम से कम |E|/2 है, तब तक कुछ अभी भी पहुंच योग्य परिणाम होना चाहिए जहां Q कम से कम |E|/2 है, इसलिए ऐसे परिणाम तक पहुंचने की कंडीशनल प्रोबबिलिस्टिक धनात्मक है।) Q की कंडीशनल अपेक्षा को |E|/2 या उससे ऊपर रखने के लिए, एल्गोरिदम, प्रत्येक चरण में, विचाराधीन शीर्ष को रंग देगा जिससे  Q की परिणामी कंडीशनल अपेक्षा को अधिकतम किया जा सकता है। यह पर्याप्त है, क्योंकि कुछ चाइल्ड होंगे जिनकी कंडीशनल अपेक्षा कम से कम वर्तमान स्थिति है की कंडीशनल अपेक्षा (और इस प्रकार कम से कम |ई|/2)।


यह देखते हुए कि कुछ शीर्ष पहले से ही रंगीन हैं, यह सशर्त अपेक्षा क्या है? मूल प्रमाण के तर्क के बाद, कटे हुए किनारों की संख्या की सशर्त अपेक्षा है
यह देखते हुए कि कुछ शीर्ष पहले से ही रंगीन हैं, यह कंडीशनल अपेक्षा क्या है? मूल प्रमाण के तर्क के पश्चात, कटे हुए किनारों की संख्या की कंडीशनल अपेक्षा है


:: किनारों की संख्या जिनके अंतिम बिंदु अब तक अलग-अलग रंग के हैं
:: किनारों की संख्या जिनके अंतिम बिंदु अब तक भिन्न-भिन्न  रंग के हैं
:: + (1/2)*(कम से कम समापन बिंदु वाले किनारों की संख्या जो अभी तक रंगीन नहीं हुई है)।
:: + (1/2)*(कम से कम समापन बिंदु वाले किनारों की संख्या जो अभी तक रंगीन नहीं हुई है)।


=== एल्गोरिथम ===
=== एल्गोरिथम ===


उपरोक्त सशर्त अपेक्षा के परिणामी मूल्य को अधिकतम करने के लिए एल्गोरिदम प्रत्येक शीर्ष को रंग देता है। यह सशर्त अपेक्षा को |ई|/2 या उससे ऊपर रखने की गारंटी है, और इसलिए विफलता की सशर्त संभावना को 1 से नीचे रखने की गारंटी है, जो बदले में सफल परिणाम की गारंटी देता है। गणना द्वारा, एल्गोरिथ्म निम्नलिखित को सरल बनाता है:
इस प्रकार से उपरोक्त कंडीशनल अपेक्षा के परिणामी मूल्य को अधिकतम करने के लिए एल्गोरिदम प्रत्येक शीर्ष को रंग देता है। यह कंडीशनल अपेक्षा को |ई|/2 या उससे ऊपर रखने की प्रमाण  है, और इसलिए विफलता की कंडीशनल प्रोबबिलिस्टिक को 1 से नीचे रखने की प्रमाण  है, जो परिवर्तन  में सफल परिणाम की प्रमाण  देता है। और गणना द्वारा, एल्गोरिथ्म निम्नलिखित को सरल बनाता है:


   1. वी में प्रत्येक शीर्ष यू के लिए (किसी भी क्रम में):
   1. V में प्रत्येक शीर्ष ''u'' के लिए (किसी भी क्रम में):
   2. आप के पहले से ही रंगीन पड़ोसी शीर्षों पर विचार करें।
   2. आप के पूर्व से ही रंगीन निकटतम शीर्षों पर विचार करें।
   3. इन शीर्षों में यदि सफेद से अधिक काले हैं तो आपको सफेद रंग दें।
   3. इन शीर्षों में यदि सफेद से अधिक काले हैं तो आपको सफेद रंग दें।
   4. नहीं तो तुम्हें काला रंग दो.
   4. नहीं तो तुम्हें काला रंग प्राप्त होगा.


इसकी व्युत्पत्ति के कारण, यह नियतात्मक एल्गोरिदम दिए गए ग्राफ़ के कम से कम आधे किनारों को काटने की गारंटी देता है। (यह इसे मैक्स-कट के लिए अधिकतम कट#सन्निकटन एल्गोरिदम|0.5-सन्निकटन एल्गोरिदम बनाता है।)
इसकी व्युत्पत्ति के कारण, यह डेटरमिनिस्टिक एल्गोरिदम दिए गए ग्राफ़ के कम से कम आधे किनारों को काटने की प्रमाण  देता है। (यह इसे मैक्स-कट के लिए अधिकतम कट या अप्प्रोक्सीमेसन  एल्गोरिदम 0.5-अप्प्रोक्सीमेसन  एल्गोरिदम बनाता है।)


== निराशावादी अनुमानकों का उपयोग करने वाला उदाहरण ==
== पेस्सिमिस्टिक एस्टीमेटरों का उपयोग करने वाला उदाहरण ==


अगला उदाहरण निराशावादी अनुमानकों के उपयोग को दर्शाता है।
इसके प्रकार से उदाहरण पेस्सिमिस्टिक एस्टीमेटरों के उपयोग को दर्शाता है।


=== तुरान का प्रमेय ===
=== तुरान का प्रमेय ===


तुरान के प्रमेय को बताने का तरीका निम्नलिखित है:
तुरान के प्रमेय को बताने का विधि  निम्नलिखित है:


: किसी भी ग्राफ G = (V, E) में कम से कम |V|/(D+1) आकार का स्वतंत्र सेट (ग्राफ सिद्धांत) होता है, जहां D = 2|E|/|V| ग्राफ़ की औसत डिग्री है.
: किसी भी ग्राफ G = (V, E) में कम से कम |V|/(D+1) आकार का स्वतंत्र समुच्चय (ग्राफ सिद्धांत) होता है, जहां D = 2|E|/|V| ग्राफ़ की औसत डिग्री है.


=== तुरान के प्रमेय का संभाव्य प्रमाण ===
=== तुरान के प्रमेय का प्रोबबिलिस्टिक  प्रमाण ===


एक स्वतंत्र समुच्चय S के निर्माण के लिए निम्नलिखित यादृच्छिक प्रक्रिया पर विचार करें:
एक स्वतंत्र समुच्चय S के निर्माण के लिए निम्नलिखित रेनडोमाइसड  प्रक्रिया पर विचार करें:
   1. खाली सेट होने के लिए S को आरंभ करें।
   1. रिक्त  समुच्चय होने के लिए S को आरंभ करें।
   2. V में प्रत्येक शीर्ष u के लिए यादृच्छिक क्रम में:
   2. V में प्रत्येक शीर्ष u के लिए रेनडोमाइसड  क्रम में:
   3. यदि आपका कोई पड़ोसी S में नहीं है, तो S में u जोड़ें
   3. यदि आपका कोई निकटतम  S में नहीं है, तो S में u जोड़ें
   4. वापसी एस.
   4. वापसी एस.
स्पष्ट रूप से प्रक्रिया स्वतंत्र सेट की गणना करती है। कोई भी शीर्ष u जिसे उसके सभी पड़ोसियों से पहले माना जाता है, उसे S में जोड़ा जाएगा। इस प्रकार, d(u) को u की डिग्री को निरूपित करने पर, संभावना है कि u को S में जोड़ा जाता है, कम से कम 1/(d(u)+1) है ). अपेक्षित मान#रैखिकता के अनुसार, S का अपेक्षित आकार कम से कम है
स्पष्ट रूप से प्रक्रिया स्वतंत्र समुच्चय की गणना करती है। कोई भी शीर्ष u जिसे उसके सभी निकटतम से पहले माना जाता है, उसे S में जोड़ा जाएगा। इस प्रकार, d(u) को u की डिग्री को निरूपित करने पर, संभावना है कि u को S में जोड़ा जाता है, कम से कम 1/(d(u)+1) है ). अपेक्षित मान या रैखिकता के अनुसार, S का अपेक्षित आकार कम से कम है


: <math>\sum_{u\in V} \frac{1}{d(u)+1} ~\ge~\frac{|V|}{D+1}.</math>
: <math>\sum_{u\in V} \frac{1}{d(u)+1} ~\ge~\frac{|V|}{D+1}.</math>
(उपरोक्त असमानता इस प्रकार है क्योंकि 1/(x+1) x में उत्तल फलन है, इसलिए बाईं ओर को न्यूनतम किया जाता है, बशर्ते कि डिग्री का योग 2|E| पर तय किया जाए, जब प्रत्येक d(u) = डी = 2|ई|/|वी|.) प्रश्न
(उपरोक्त असमानता इस प्रकार है क्योंकि 1/(x+1) x में उत्तल फलन है, इसलिए बाईं ओर को न्यूनतम किया जाता है, बनियम कि डिग्री का योग 2|E| पर तय किया जाए, जब प्रत्येक d(u) = डी = 2|ई|/|वी|.) प्रश्न


=== निराशावादी अनुमानकों का उपयोग करके सशर्त संभावनाओं की विधि ===
=== पेस्सिमिस्टिक एस्टीमेटरों का उपयोग करके मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक ===


इस मामले में, यादृच्छिक प्रक्रिया में |V| है कदम। प्रत्येक चरण कुछ ऐसे शीर्षों पर विचार करता है जिन्हें अभी तक नहीं माना गया है और यदि उसके किसी भी पड़ोसी को अभी तक नहीं जोड़ा गया है तो उसे एस में जोड़ दिया जाता है। मान लें कि यादृच्छिक चर Q, S में जोड़े गए शीर्षों की संख्या है। प्रमाण से पता चलता है कि E[Q] ≥ |V|/(D+1)।
इस स्तिथि  में, रेनडोमाइसड  प्रक्रिया में |V| है पद। प्रत्येक चरण कुछ ऐसे शीर्षों पर विचार करता है जिन्हें अभी तक नहीं माना गया है और यदि उसके किसी भी निकटतम  को अभी तक नहीं जोड़ा गया है तो उसे एस में जोड़ दिया जाता है। मान लें कि रेनडोमाइसड  वेरिएबल Q, S में जोड़े गए शीर्षों की संख्या है। प्रमाण से पता चलता है कि E[Q] ≥ |V|/(D+1)।


हम प्रत्येक यादृच्छिक चरण को नियतात्मक चरण से प्रतिस्थापित करेंगे जो Q की सशर्त अपेक्षा को |V|/(D+1) पर या उससे ऊपर रखता है। यह सफल परिणाम सुनिश्चित करेगा, अर्थात, जिसमें स्वतंत्र सेट S का आकार कम से कम |V|/(D+1) हो, जो तुरान के प्रमेय में सीमा को साकार करता है।
हम प्रत्येक रेनडोमाइसड  चरण को डेटरमिनिस्टिक चरण से प्रतिस्थापित करेंगे जो Q की कंडीशनल अपेक्षा को |V|/(D+1) पर या उससे ऊपर रखता है। यह सफल परिणाम सुनिश्चित करेगा, अर्थात, जिसमें स्वतंत्र समुच्चय S का आकार कम से कम |V|/(D+1) हो, जो तुरान के प्रमेय में सीमा को साकार करता है।


यह देखते हुए कि पहला t कदम उठाया जा चुका है, मान लीजिए S<sup>(t)</sup>अब तक जोड़े गए शीर्षों को दर्शाता है। चलो आर<sup>(टी)</sup>उन शीर्षों को दर्शाता है जिन पर अभी तक विचार नहीं किया गया है, और जिनका एस में कोई पड़ोसी नहीं है<sup>(टी)</sup>. पहले t चरणों को देखते हुए, मूल प्रमाण में तर्क के बाद, R में कोई भी शीर्ष w दिया गया है<sup>(t)</sup> में S में जोड़े जाने की सशर्त संभावना कम से कम 1/(d(w)+1) है, इसलिए Q की सशर्त अपेक्षा कम से कम है
यह देखते हुए कि प्रथम t पद  उठाया जा चुका है, मान लीजिए S<sup>(t)</sup>अब तक जोड़े गए शीर्षों को दर्शाता है। जब  ''R''<sup>(''t'')</sup> उन शीर्षों को दर्शाता है जिन पर अभी तक विचार नहीं किया गया है, और जिनका S<sup>(t)</sup> में कोई निकटतम  नहीं है. पहले t चरणों को देखते हुए, मूल प्रमाण में तर्क के पश्चात, R<sup>(t)</sup> में कोई भी शीर्ष w दिया गया है में S में जोड़े जाने की कंडीशनल प्रोबबिलिस्टिक कम से कम 1/(d(w)+1) है, इसलिए Q की कंडीशनल अपेक्षा कम से कम है


: <math>|S^{(t)}| ~+~ \sum_{w\in R^{(t)}} \frac{1}{d(w)+1}. </math>
: <math>|S^{(t)}| ~+~ \sum_{w\in R^{(t)}} \frac{1}{d(w)+1}. </math>
चलो Q<sup>(t)</sup>उपर्युक्त मात्रा को दर्शाता है, जिसे सशर्त अपेक्षा के लिए 'निराशावादी अनुमानक' कहा जाता है।
मान लीजिये Q<sup>(t)</sup> उपर्युक्त मात्रा को दर्शाता है, जिसे कंडीशनल अपेक्षा के लिए पेस्सिमिस्टिक एस्टीमेटर' कहा जाता है।


प्रमाण से पता चला कि निराशावादी अनुमानक शुरू में कम से कम |V|/(D+1) है। (अर्थात्, प्र<sup>(0)</sup> ≥ |V|/(D+1).) एल्गोरिदम निराशावादी अनुमानक को घटने से रोकने के लिए प्रत्येक विकल्प चुनेगा, अर्थात, ताकि Q<sup>(t+1)</sup> ≥ Q<sup>(टी)</sup>प्रत्येक टी के लिए। चूँकि निराशावादी अनुमानक सशर्त अपेक्षा पर निचली सीमा रखता है, यह सुनिश्चित करेगा कि सशर्त अपेक्षा |V|/(D+1) से ऊपर रहे, जो बदले में यह सुनिश्चित करेगा कि विफलता की सशर्त संभावना 1 से नीचे रहे।
प्रमाण से पता चला कि पेस्सिमिस्टिक एस्टीमेटर प्रारंभ  में कम से कम |V|/(D+1) है। (अर्थात्, ''Q''<sup>(0)</sup> ≥ |''V''|/(''D''+1).) एल्गोरिदम पेस्सिमिस्टिक एस्टीमेटर को घटने से रोकने के लिए प्रत्येक विकल्प चुनेगा, अर्थात, जिससे  ''Q''<sup>(''t''+1)</sup> ≥ ''Q''<sup>(''t'')</sup> प्रत्येक t के लिए। चूँकि पेस्सिमिस्टिक एस्टीमेटर कंडीशनल अपेक्षा पर निचली सीमा रखता है, यह सुनिश्चित करेगा कि कंडीशनल अपेक्षा |V|/(D+1) से ऊपर रहे, जो परिवर्तन  में यह सुनिश्चित करेगा कि विफलता की कंडीशनल प्रोबबिलिस्टिक 1 से नीचे रहे है।


मान लीजिए कि आप अगले ((t+1)-st) चरण में एल्गोरिथम द्वारा माना गया शीर्ष है।
मान लीजिए कि आप अगले ((t+1)-st) चरण में एल्गोरिथम द्वारा माना गया शीर्ष है।


यदि आपका पहले से ही S में कोई पड़ोसी है, तो आपको S में नहीं जोड़ा जाता है और (Q के निरीक्षण द्वारा)<sup>(t)</sup>), निराशावादी अनुमानक अपरिवर्तित है। यदि S में u का कोई पड़ोसी नहीं है, तो S में u जोड़ा जाता है।
यदि आपका पहले से ही S में कोई निकटतम  है, तो आपको S में नहीं जोड़ा जाता है और (Q<sup>(t)</sup> के निरीक्षण द्वारा)), पेस्सिमिस्टिक एस्टीमेटर अपरिवर्तित है। यदि S में u का कोई निकटतम  नहीं है, तब S में u जोड़ा जाता है।


गणना के अनुसार, यदि यू को शेष शीर्षों से यादृच्छिक रूप से चुना जाता है, तो निराशावादी अनुमानक में अपेक्षित वृद्धि गैर-नकारात्मक है। ['हिसाब।' आर में शीर्ष चुनने पर शर्त<sup>(टी)</sup>, निराशावादी अनुमानक में दिए गए पद 1/(d(w)+1) को योग से हटा दिए जाने की संभावना अधिकतम (d(w)+1)/|R है<sup>(टी)</sup>|, इसलिए योग में प्रत्येक पद में अपेक्षित कमी अधिकतम 1/|आर है<sup>(टी)</sup>|. आर हैं<sup>(t)</sup>योग में शर्तें। इस प्रकार, योग में अपेक्षित कमी अधिकतम 1 है। इस बीच, S का आकार 1 बढ़ जाता है।]
गणना के अनुसार, यदि u को शेष शीर्षों से रेनडोमाइसड  रूप से चुना जाता है, तो पेस्सिमिस्टिक एस्टीमेटर में अपेक्षित वृद्धि गैर-ऋणात्मक  है। ['गणना के अनुसार।' ''R''<sup>(''t'')</sup> में शीर्ष चुनने पर नियम , पेस्सिमिस्टिक एस्टीमेटर में दिए गए पद 1/(d(w)+1) को योग से हटा दिए जाने की संभावना अधिकतम (''d''(''w'')+1)/|''R''<sup>(''t'')</sup>| है, इसलिए योग में प्रत्येक पद में अपेक्षित कमी अधिकतम 1/|''R''<sup>(''t'')</sup>| है. जहाँ ''R''<sup>(''t''))</sup> योग में नियम इस प्रकार, योग में अपेक्षित कमी अधिकतम 1 है। इस मध्य, S का आकार 1 बढ़ जाता है।]


इस प्रकार, आपके पास कुछ विकल्प मौजूद होने चाहिए जो निराशावादी अनुमानक को कम होने से रोकते हैं।
इस प्रकार, आपके पास कुछ विकल्प उपस्तिथ होने चाहिए जो पेस्सिमिस्टिक एस्टीमेटर को कम होने से रोकते हैं।


=== निराशावादी अनुमानक को अधिकतम करने वाला एल्गोरिदम ===
=== पेस्सिमिस्टिक एस्टीमेटर को अधिकतम करने वाला एल्गोरिदम ===


परिणामी निराशावादी अनुमानक को अधिकतम करने के लिए नीचे दिया गया एल्गोरिदम प्रत्येक शीर्ष यू को चुनता है। पिछले विचारों के अनुसार, यह निराशावादी अनुमानक को कम होने से रोकता है और सफल परिणाम की गारंटी देता है।
परिणामी पेस्सिमिस्टिक एस्टीमेटर को अधिकतम करने के लिए नीचे दिया गया एल्गोरिदम प्रत्येक शीर्ष u को चुनता है। पिछले विचारों के अनुसार, यह पेस्सिमिस्टिक एस्टीमेटर को कम होने से रोकता है और सफल परिणाम की प्रमाण देता है।


नीचे, एन<sup>(t)</sup>(u) R में आपके पड़ोसियों को दर्शाता है<sup>(t)</sup> (अर्थात्, आपके पड़ोसी जो न तो S में हैं और न ही उनका कोई पड़ोसी S में है)।
नीचे, ''N''<sup>(''t'')</sup>(''u'') ''R''<sup>(''t'')</sup> में u के निकटतम को दर्शाता है (अर्थात, आपके ऐसे निकटतम जो न तो S में हैं और न ही S में उनका कोई निकटतम है)।
  1. खाली सेट होने के लिए S को आरंभ करें।
  1. रिक्त समुच्चय होने के लिए S को आरंभ करें।
  2. जबकि एस में कोई पड़ोसी नहीं होने के कारण अभी तक नहीं माना जाने वाला शीर्ष यू मौजूद है:
  2. जबकि एस में कोई निकटतम  नहीं होने के कारण अभी तक नहीं माना जाने वाला शीर्ष u उपस्तिथ है:
  3. S में ऐसा शीर्ष u जोड़ें जहां u न्यूनतम हो <math>\sum_{w\in N^{(t)}(u)\cup\{u\}} \frac{1}{d(w)+1}</math>.
  3. S में ऐसा शीर्ष u जोड़ें जहां u न्यूनतम हो <math>\sum_{w\in N^{(t)}(u)\cup\{u\}} \frac{1}{d(w)+1}</math>.
  4. वापसी एस.
  4. वापसी S.


=== एल्गोरिदम जो निराशावादी अनुमानक को अधिकतम नहीं करते ===
=== एल्गोरिदम जो पेस्सिमिस्टिक एस्टीमेटर को अधिकतम नहीं करते ===


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


  1. खाली सेट होने के लिए S को आरंभ करें।
  1. रिक्त  समुच्चय होने के लिए S को आरंभ करें।
  2. जबकि ग्राफ़ में शीर्ष u मौजूद है जिसका S में कोई पड़ोसी नहीं है:
  2. जबकि ग्राफ़ में शीर्ष u उपस्तिथ  है जिसका S में कोई निकटतम  नहीं है:
  3. S में ऐसा शीर्ष u जोड़ें, जहां u, d(u) (u की प्रारंभिक डिग्री) को न्यूनतम करता है।
  3. S में ऐसा शीर्ष u जोड़ें, जहां u, d(u) (u की प्रारंभिक डिग्री) को न्यूनतम करता है।
  4. वापसी एस.
  4. वापसी एस.


  1. खाली सेट होने के लिए S को आरंभ करें।
  1. रिक्त  समुच्चय होने के लिए S को आरंभ करें।
  2. जबकि शेष ग्राफ खाली नहीं है:
  2. जबकि शेष ग्राफ रिक्त  नहीं है:
  3. S में शीर्ष u जोड़ें, जहां शेष ग्राफ़ में u की न्यूनतम डिग्री है।
  3. S में शीर्ष u जोड़ें, जहां शेष ग्राफ़ में u की न्यूनतम डिग्री है।
  4. ग्राफ़ से आप और उसके सभी पड़ोसियों को हटा दें।
  4. ग्राफ़ से आप और उसके सभी निकटतम को हटा दें।
  5. वापसी एस.
  5. वापसी S.


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


: <math>1 - \sum_{w\in N^{(t)}(u)\cup\{u\}} \frac{1}{d(w)+1},</math>
: <math>1 - \sum_{w\in N^{(t)}(u)\cup\{u\}} \frac{1}{d(w)+1},</math>
जहां एन<sup>(t)</sup>(u) शेष ग्राफ़ में (अर्थात R में) u के पड़ोसियों को दर्शाता है<sup>(टी)</sup>).
जहां ''N''<sup>(''t'')</sup>(''u'') शेष ग्राफ़ में u के निकटतम को दर्शाता है (अर्थात, ''R''<sup>(''t'')</sup> में)।.


पहले एल्गोरिदम के लिए, शुद्ध वृद्धि गैर-नकारात्मक है क्योंकि, यू की पसंद से,
प्रथम एल्गोरिदम के लिए, शुद्ध वृद्धि गैर-ऋणात्मक  है क्योंकि, u की चॉइस  से,


: <math>\sum_{w\in N^{(t)}(u)\cup\{u\}} \frac{1}{d(w)+1} \le (d(u)+1) \frac{1}{d(u)+1} = 1 </math>,
: <math>\sum_{w\in N^{(t)}(u)\cup\{u\}} \frac{1}{d(w)+1} \le (d(u)+1) \frac{1}{d(u)+1} = 1 </math>,


जहां d(u) मूल ग्राफ़ में u की डिग्री है।
जहां ''d(u)'' मूल ग्राफ़ में u की डिग्री है।


दूसरे एल्गोरिदम के लिए, शुद्ध वृद्धि गैर-नकारात्मक है क्योंकि, यू की पसंद से,
दूसरे एल्गोरिदम के लिए, शुद्ध वृद्धि गैर-ऋणात्मक  है क्योंकि, u की चॉइस से,


: <math>\sum_{w\in N^{(t)}(u)\cup\{u\}} \frac{1}{d(w)+1} \le (d'(u)+1) \frac{1}{d'(u)+1} = 1 </math>,
: <math>\sum_{w\in N^{(t)}(u)\cup\{u\}} \frac{1}{d(w)+1} \le (d'(u)+1) \frac{1}{d'(u)+1} = 1 </math>,
Line 173: Line 174:
== यह भी देखें ==
== यह भी देखें ==


* संभाव्य विधि
* प्रोबबिलिस्टिक मेथड
* व्युत्पत्तिकरण
* डेरनडोमाईज़ेसन
* यादृच्छिक गोलाई
* रेनडोमाइसड राउंडिंग


== संदर्भ ==
== संदर्भ ==

Revision as of 14:05, 3 August 2023

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

मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक (Spencer 1987), और (राघवन 1988) इस प्रकार के प्रमाण का, अधिक स्पष्ट अर्थ है, कुशल डेटरमिनिस्टिक एल्गोरिदम में परिवर्तित करता है, जो वांछित गुणों के साथ किसी वस्तु की गणना करने का प्रमाण देता है। अर्थात विधि रेनडोमाइसड प्रमाण. मूल विचार रेनडोमाइसड प्रयोग में प्रत्येक रैंडम चॉइस को डेटरमिनिस्टिक चॉइस से प्रतिस्थापित करना है, जिससे अब तक के विकल्पों को देखते हुए विफलता की कंडीशनल प्रोबबिलिस्टिक को 1 से नीचे रखा जा सकता है।

यह विधि रेनडोमाइसड राउंडिंग के संदर्भ में विशेष रूप से प्रासंगिक है (जो अप्प्रोक्सीमेसन एल्गोरिदम को डिजाइन करने के लिए प्रोबबिलिस्टिक विधि का उपयोग करती है)।

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

अवलोकन

(राघवन 1988) यह विवरण देता है:

इस प्रकार से हम प्रोबबिलिस्टिक विधि का उपयोग करके सिद्ध रूप से सही अनुमानित समाधान के अस्तित्व को दिखाते हैं... [फिर हम] दिखाते हैं कि प्रोबबिलिस्टिक अस्तित्व प्रमाण का अधिक स्पष्ट अर्थ है, कि डेटरमिनिस्टिक को अप्प्रोक्सीमेसन एल्गोरिदम में परिवर्तित किया जा सकता है।

(राघवन रेनडोमाइसड पूर्णांकन के संदर्भ में विधि पर चर्चा कर रहे हैं, किन्तु यह सामान्य रूप से प्रोबबिलिस्टिक विधि के साथ कार्य करता है।)

मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक

इस प्रकार से विधि को प्रोबबिलिस्टिक प्रमाण पर प्रयुक्त करने के लिए, प्रमाण में रेनडोमाइसड रूप से चुनी गई है और वस्तु को रेनडोमाइसड प्रयोग द्वारा चुना जाना चाहिए जिसमें छोटे रैंडम चॉइस का अनुक्रम सम्मिलित होती है।

अतः सिद्धांत को स्पष्ट करने के लिए यहां छोटा सा उदाहरण दिया गया है।

लेम्मा: तीन सिक्कों को उछालना संभव है जिससे टेल्स की संख्या कम से कम 2 हो।
प्रोबबिलिस्टिक प्रमाण यदि तीन सिक्कों को रेनडोमाइसड रूप से उछाला जाता है, तो टेल्स की अपेक्षित संख्या 1.5 है। इस प्रकार, कुछ परिणाम (सिक्के उछालने का विधि ) होना चाहिए जिससे टेल्स की संख्या कम से कम 1.5 हो। चूँकि टेल्स की संख्या पूर्णांक है, ऐसे परिणाम में कम से कम 2 टेल्स होती हैं। प्रश्न

इस उदाहरण में रेनडोमाइसड प्रयोग में तीन निष्पक्ष सिक्कों को उछालना सम्मिलित किया है। और प्रयोग को आसन्न चित्र में रूट वाले ट्री द्वारा दर्शाया गया है। अतः यह आठ परिणाम हैं, प्रत्येक ट्री में लीफ के अनुरूप है। रेनडोमाइसड प्रयोग का परीक्षण रूट (ट्री में शीर्ष नोड, जहां कोई सिक्का नहीं उछाला गया है) से लीफ तक रेनडोमाइसड चलने से मेल खाता है। सफल परिणाम वे हैं जिनमें कम से कम दो सिक्के पीछे आए। किन्तु ट्री में आंतरिक नोड्स आंशिक रूप से निर्धारित परिणामों के अनुरूप हैं, जहां अब तक केवल 0, 1, या 2 सिक्के ही उछाले गए हैं।

कंडीशनल प्रोबबिलिस्टिक की पद्धति को प्रयुक्त करने के लिए, जैसे-जैसे प्रयोग चरण दर चरण आगे बढ़ता है, अब तक के विकल्पों को देखते हुए विफलता की कंडीशनल प्रोबबिलिस्टिक पर ध्यान केंद्रित किया जाता है।

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

मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक रेनडोमाइसड प्रयोग में रेनडोमाइसड रूट-टू-लीफ वॉक को डेटरमिनिस्टिक रूट-टू-लीफ वॉक द्वारा प्रतिस्थापित करती है, जहां प्रत्येक चरण को निम्नलिखित अपरिवर्तनीय बनाए रखने के लिए चुना जाता है:

वर्तमान स्थिति को देखते हुए विफलता की कंडीशनल प्रोबबिलिस्टिक 1 से कम है।

इस प्रकार, लेबल 0 वाले लीफ पर पहुंचने की प्रमाण है, अर्थात सफल परिणाम है।

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

दक्षता

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

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

दुर्भाग्य से, अधिकांश अनुप्रयोगों में, विफलता की कंडीशनल प्रोबबिलिस्टिक की कुशलता से गणना करना सरल नहीं है। इससे निपटने के लिए दो मानक और संबंधित तकनीकें हैं:

  • 'कंडीशनल अपेक्षा का उपयोग करना:' अनेक प्रोबबिलिस्टिक प्रमाण इस प्रकार कार्य करते हैं: वे स्पष्ट रूप से रेनडोमाइसड वेरिएबल Q को परिभाषित करते हैं, दिखाते हैं कि (i) Q की अपेक्षा अधिकतम (या कम से कम) कुछ सीमा मूल्य है, और (ii) किसी भी परिणाम जहां Q अधिकतम (कम से कम) इस सीमा पर है, परिणाम सफल है। तब (i) का अर्थ है कि परिणाम उपस्तिथ है जहां Q अधिकतम (कम से कम) सीमा है, और इसका और (ii) का अर्थ है कि सफल परिणाम है। (उपरोक्त उदाहरण में, Q टेल्स की संख्या है, जो कम से कम सीमा 1.5 होनी चाहिए। अनेक अनुप्रयोगों में, Q किसी दिए गए परिणाम में होने वाली बैड इवेंट्स (आवश्यक नहीं कि असंबद्ध) की संख्या है, जहां प्रत्येक बैड इवेंट्स मेल खाती है तरह से प्रयोग विफल हो सकता है, और घटित होने वाली बैड इवेंट्स की अपेक्षित संख्या 1 से कम है।)

इस स्तिथि में, विफलता की कंडीशनल प्रोबबिलिस्टिक को 1 से नीचे रखने के लिए, Q की कंडीशनल अपेक्षा को सीमा से नीचे (या ऊपर) रखना पर्याप्त है। ऐसा करने के लिए, विफलता की कंडीशनल प्रोबबिलिस्टिक की गणना करने के अतिरिक्त , एल्गोरिदम Q की कंडीशनल अपेक्षा की गणना करता है और तदनुसार आगे बढ़ता है: प्रत्येक आंतरिक नोड पर, कुछ चाइल्ड होते हैं जिनकी कंडीशनल अपेक्षा अधिकतम (कम से कम) नोड की कंडीशनल अपेक्षा होती है; एल्गोरिथ्म वर्तमान नोड से ऐसे चाइल्ड की ओर बढ़ता है, इस प्रकार कंडीशनल अपेक्षा को सीमा से नीचे (ऊपर) रखता है।

  • पेस्सिमिस्टिक एस्टीमेटर का उपयोग करना:' कुछ स्तिथि में, मात्रा Q की स्पष्ट कंडीशनल अपेक्षा के लिए प्रॉक्सी के रूप में, उचित रूप से टाइट सीमा का उपयोग किया जाता है जिसे पेस्सिमिस्टिक एस्टीमेटर कहा जाता है। पेस्सिमिस्टिक एस्टीमेटर वर्तमान स्थिति का कार्य है। वर्तमान स्थिति को देखते हुए यह Q की कंडीशनल अपेक्षा के लिए ऊपरी (या निचला) होना चाहिए, और यह प्रयोग के प्रत्येक रेनडोमाइसड चरण के साथ अपेक्षा में गैर-बढ़ती (या गैर-घटती) होनी चाहिए। सामान्यतः, अच्छे पेस्सिमिस्टिक एस्टीमेटर की गणना मूल प्रमाण के तर्क को स्पष्ट रूप से विखंडित करके की जा सकती है।

कंडीशनल अपेक्षाओं का उपयोग करने वाला उदाहरण

यह उदाहरण कंडीशनल अपेक्षा का उपयोग करके मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक को प्रदर्शित करता है।

मैक्स-कट लेम्मा

किसी भी अप्रत्यक्ष ग्राफ़ (असतत गणित) G = (V, E) को देखते हुए, अधिकतम कट समस्या ग्राफ़ के प्रत्येक शीर्ष को दो रंगों (जैसे काले या सफेद) में से के साथ रंगना है जिससे किनारों की संख्या को अधिकतम किया जा सके जिनके अंतिम बिंदु हैं अलग - अलग रंग। (कहो ऐसी धार कटी है।)

'मैक्स-कट लेम्मा:' किसी भी ग्राफ G = (V, E) में, कम से कम |E|/2 किनारों को काटा जा सकता है।

'प्रोबबिलिस्टिक प्रमाण।' सफेद सिक्का उछालकर प्रत्येक शीर्ष को काला या सफेद रंग दें। गणना के अनुसार, E में किसी भी किनारे E के लिए, इसके कटने की संभावना 1/2 है। इस प्रकार, अपेक्षित मान या रैखिकता के अनुसार, काटे गए किनारों की अपेक्षित संख्या |E|/2 है। इस प्रकार, ऐसा रंग उपस्तिथ है जो कम से कम |E|/2 किनारों को क्यूईडी काटता है।

कंडीशनल अपेक्षाओं के साथ मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक

मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक को प्रयुक्त करने के लिए, पहले रेनडोमाइसड प्रयोग को छोटे रेनडोमाइसड चरणों के अनुक्रम के रूप में मॉडल किया जाता है। इस स्तिथि में प्रत्येक चरण को किसी विशेष शीर्ष के लिए रंग की चॉइस के रूप में मानना ​​स्वाभाविक है (इसलिए |V| चरण हैं)।

इसके पश्चात , प्रत्येक चरण में रैंडम चॉइस को डेटरमिनिस्टिक चॉइस से परिवर्तन , जिससे विफलता की कंडीशनल प्रोबबिलिस्टिक को बनाए रखा जा सके, अब तक रंगे गए शीर्षों को 1 से नीचे दिया गया है। (यहां विफलता का अर्थ है कि अंततः |E|/2 से कम किनारे काटे गए हैं।)

इस स्तिथि में, विफलता की कंडीशनल प्रोबबिलिस्टिक की गणना करना सरल नहीं है। वास्तव में, मूल प्रमाण सीधे विफलता की संभावना की गणना नहीं करता था; इसके अतिरिक्त, प्रमाण ने यह दिखाकर कार्य किया कि कटे हुए किनारों की अपेक्षित संख्या कम से कम |ई|/2 थी।

माना रेनडोमाइसड वेरिएबल Q कटे हुए किनारों की संख्या है। विफलता की कंडीशनल प्रोबबिलिस्टिक को 1 से नीचे रखने के लिए, Q की कंडीशनल अपेक्षा को सीमा |E|/2 पर या उससे ऊपर रखना पर्याप्त है। (ऐसा इसलिए है क्योंकि जब तक Q की कंडीशनल अपेक्षा कम से कम |E|/2 है, तब तक कुछ अभी भी पहुंच योग्य परिणाम होना चाहिए जहां Q कम से कम |E|/2 है, इसलिए ऐसे परिणाम तक पहुंचने की कंडीशनल प्रोबबिलिस्टिक धनात्मक है।) Q की कंडीशनल अपेक्षा को |E|/2 या उससे ऊपर रखने के लिए, एल्गोरिदम, प्रत्येक चरण में, विचाराधीन शीर्ष को रंग देगा जिससे Q की परिणामी कंडीशनल अपेक्षा को अधिकतम किया जा सकता है। यह पर्याप्त है, क्योंकि कुछ चाइल्ड होंगे जिनकी कंडीशनल अपेक्षा कम से कम वर्तमान स्थिति है की कंडीशनल अपेक्षा (और इस प्रकार कम से कम |ई|/2)।

यह देखते हुए कि कुछ शीर्ष पहले से ही रंगीन हैं, यह कंडीशनल अपेक्षा क्या है? मूल प्रमाण के तर्क के पश्चात, कटे हुए किनारों की संख्या की कंडीशनल अपेक्षा है

किनारों की संख्या जिनके अंतिम बिंदु अब तक भिन्न-भिन्न रंग के हैं
+ (1/2)*(कम से कम समापन बिंदु वाले किनारों की संख्या जो अभी तक रंगीन नहीं हुई है)।

एल्गोरिथम

इस प्रकार से उपरोक्त कंडीशनल अपेक्षा के परिणामी मूल्य को अधिकतम करने के लिए एल्गोरिदम प्रत्येक शीर्ष को रंग देता है। यह कंडीशनल अपेक्षा को |ई|/2 या उससे ऊपर रखने की प्रमाण है, और इसलिए विफलता की कंडीशनल प्रोबबिलिस्टिक को 1 से नीचे रखने की प्रमाण है, जो परिवर्तन में सफल परिणाम की प्रमाण देता है। और गणना द्वारा, एल्गोरिथ्म निम्नलिखित को सरल बनाता है: 

 1. V में प्रत्येक शीर्ष u के लिए (किसी भी क्रम में):
 2. आप के पूर्व से ही रंगीन निकटतम शीर्षों पर विचार करें।
 3. इन शीर्षों में यदि सफेद से अधिक काले हैं तो आपको सफेद रंग दें।
 4. नहीं तो तुम्हें काला रंग प्राप्त होगा.

इसकी व्युत्पत्ति के कारण, यह डेटरमिनिस्टिक एल्गोरिदम दिए गए ग्राफ़ के कम से कम आधे किनारों को काटने की प्रमाण देता है। (यह इसे मैक्स-कट के लिए अधिकतम कट या अप्प्रोक्सीमेसन एल्गोरिदम 0.5-अप्प्रोक्सीमेसन एल्गोरिदम बनाता है।)

पेस्सिमिस्टिक एस्टीमेटरों का उपयोग करने वाला उदाहरण

इसके प्रकार से उदाहरण पेस्सिमिस्टिक एस्टीमेटरों के उपयोग को दर्शाता है।

तुरान का प्रमेय

तुरान के प्रमेय को बताने का विधि निम्नलिखित है:

किसी भी ग्राफ G = (V, E) में कम से कम |V|/(D+1) आकार का स्वतंत्र समुच्चय (ग्राफ सिद्धांत) होता है, जहां D = 2|E|/|V| ग्राफ़ की औसत डिग्री है.

तुरान के प्रमेय का प्रोबबिलिस्टिक प्रमाण

एक स्वतंत्र समुच्चय S के निर्माण के लिए निम्नलिखित रेनडोमाइसड प्रक्रिया पर विचार करें: 

 1. रिक्त  समुच्चय होने के लिए S को आरंभ करें।
 2. V में प्रत्येक शीर्ष u के लिए रेनडोमाइसड  क्रम में:
 3. यदि आपका कोई निकटतम  S में नहीं है, तो S में u जोड़ें
 4. वापसी एस.

स्पष्ट रूप से प्रक्रिया स्वतंत्र समुच्चय की गणना करती है। कोई भी शीर्ष u जिसे उसके सभी निकटतम से पहले माना जाता है, उसे S में जोड़ा जाएगा। इस प्रकार, d(u) को u की डिग्री को निरूपित करने पर, संभावना है कि u को S में जोड़ा जाता है, कम से कम 1/(d(u)+1) है ). अपेक्षित मान या रैखिकता के अनुसार, S का अपेक्षित आकार कम से कम है

(उपरोक्त असमानता इस प्रकार है क्योंकि 1/(x+1) x में उत्तल फलन है, इसलिए बाईं ओर को न्यूनतम किया जाता है, बनियम कि डिग्री का योग 2|E| पर तय किया जाए, जब प्रत्येक d(u) = डी = 2|ई|/|वी|.) प्रश्न

पेस्सिमिस्टिक एस्टीमेटरों का उपयोग करके मेथड ऑफ़ कंडीशनल प्रोबबिलिस्टिक

इस स्तिथि में, रेनडोमाइसड प्रक्रिया में |V| है पद। प्रत्येक चरण कुछ ऐसे शीर्षों पर विचार करता है जिन्हें अभी तक नहीं माना गया है और यदि उसके किसी भी निकटतम को अभी तक नहीं जोड़ा गया है तो उसे एस में जोड़ दिया जाता है। मान लें कि रेनडोमाइसड वेरिएबल Q, S में जोड़े गए शीर्षों की संख्या है। प्रमाण से पता चलता है कि E[Q] ≥ |V|/(D+1)।

हम प्रत्येक रेनडोमाइसड चरण को डेटरमिनिस्टिक चरण से प्रतिस्थापित करेंगे जो Q की कंडीशनल अपेक्षा को |V|/(D+1) पर या उससे ऊपर रखता है। यह सफल परिणाम सुनिश्चित करेगा, अर्थात, जिसमें स्वतंत्र समुच्चय S का आकार कम से कम |V|/(D+1) हो, जो तुरान के प्रमेय में सीमा को साकार करता है।

यह देखते हुए कि प्रथम t पद उठाया जा चुका है, मान लीजिए S(t)अब तक जोड़े गए शीर्षों को दर्शाता है। जब R(t) उन शीर्षों को दर्शाता है जिन पर अभी तक विचार नहीं किया गया है, और जिनका S(t) में कोई निकटतम नहीं है. पहले t चरणों को देखते हुए, मूल प्रमाण में तर्क के पश्चात, R(t) में कोई भी शीर्ष w दिया गया है में S में जोड़े जाने की कंडीशनल प्रोबबिलिस्टिक कम से कम 1/(d(w)+1) है, इसलिए Q की कंडीशनल अपेक्षा कम से कम है

मान लीजिये Q(t) उपर्युक्त मात्रा को दर्शाता है, जिसे कंडीशनल अपेक्षा के लिए पेस्सिमिस्टिक एस्टीमेटर' कहा जाता है।

प्रमाण से पता चला कि पेस्सिमिस्टिक एस्टीमेटर प्रारंभ में कम से कम |V|/(D+1) है। (अर्थात्, Q(0) ≥ |V|/(D+1).) एल्गोरिदम पेस्सिमिस्टिक एस्टीमेटर को घटने से रोकने के लिए प्रत्येक विकल्प चुनेगा, अर्थात, जिससे Q(t+1) ≥ Q(t) प्रत्येक t के लिए। चूँकि पेस्सिमिस्टिक एस्टीमेटर कंडीशनल अपेक्षा पर निचली सीमा रखता है, यह सुनिश्चित करेगा कि कंडीशनल अपेक्षा |V|/(D+1) से ऊपर रहे, जो परिवर्तन में यह सुनिश्चित करेगा कि विफलता की कंडीशनल प्रोबबिलिस्टिक 1 से नीचे रहे है।

मान लीजिए कि आप अगले ((t+1)-st) चरण में एल्गोरिथम द्वारा माना गया शीर्ष है।

यदि आपका पहले से ही S में कोई निकटतम है, तो आपको S में नहीं जोड़ा जाता है और (Q(t) के निरीक्षण द्वारा)), पेस्सिमिस्टिक एस्टीमेटर अपरिवर्तित है। यदि S में u का कोई निकटतम नहीं है, तब S में u जोड़ा जाता है।

गणना के अनुसार, यदि u को शेष शीर्षों से रेनडोमाइसड रूप से चुना जाता है, तो पेस्सिमिस्टिक एस्टीमेटर में अपेक्षित वृद्धि गैर-ऋणात्मक है। ['गणना के अनुसार।' R(t) में शीर्ष चुनने पर नियम , पेस्सिमिस्टिक एस्टीमेटर में दिए गए पद 1/(d(w)+1) को योग से हटा दिए जाने की संभावना अधिकतम (d(w)+1)/|R(t)| है, इसलिए योग में प्रत्येक पद में अपेक्षित कमी अधिकतम 1/|R(t)| है. जहाँ R(t)) योग में नियम इस प्रकार, योग में अपेक्षित कमी अधिकतम 1 है। इस मध्य, S का आकार 1 बढ़ जाता है।]

इस प्रकार, आपके पास कुछ विकल्प उपस्तिथ होने चाहिए जो पेस्सिमिस्टिक एस्टीमेटर को कम होने से रोकते हैं।

पेस्सिमिस्टिक एस्टीमेटर को अधिकतम करने वाला एल्गोरिदम

परिणामी पेस्सिमिस्टिक एस्टीमेटर को अधिकतम करने के लिए नीचे दिया गया एल्गोरिदम प्रत्येक शीर्ष u को चुनता है। पिछले विचारों के अनुसार, यह पेस्सिमिस्टिक एस्टीमेटर को कम होने से रोकता है और सफल परिणाम की प्रमाण देता है।

नीचे, N(t)(u) R(t) में u के निकटतम को दर्शाता है (अर्थात, आपके ऐसे निकटतम जो न तो S में हैं और न ही S में उनका कोई निकटतम है)। 

1. रिक्त समुच्चय होने के लिए S को आरंभ करें।
2. जबकि एस में कोई निकटतम  नहीं होने के कारण अभी तक नहीं माना जाने वाला शीर्ष u उपस्तिथ है:
3. S में ऐसा शीर्ष u जोड़ें जहां u न्यूनतम हो .
4. वापसी S.

एल्गोरिदम जो पेस्सिमिस्टिक एस्टीमेटर को अधिकतम नहीं करते

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

1. रिक्त  समुच्चय होने के लिए S को आरंभ करें।
2. जबकि ग्राफ़ में शीर्ष u उपस्तिथ  है जिसका S में कोई निकटतम  नहीं है:
3. S में ऐसा शीर्ष u जोड़ें, जहां u, d(u) (u की प्रारंभिक डिग्री) को न्यूनतम करता है।
4. वापसी एस.

1. रिक्त  समुच्चय होने के लिए S को आरंभ करें।
2. जबकि शेष ग्राफ रिक्त  नहीं है:
3. S में शीर्ष u जोड़ें, जहां शेष ग्राफ़ में u की न्यूनतम डिग्री है।
4. ग्राफ़ से आप और उसके सभी निकटतम को हटा दें।
5. वापसी S.

प्रत्येक एल्गोरिदम का विश्लेषण पहले की तरह ही पेस्सिमिस्टिक एस्टीमेटर के साथ किया जाता है। किसी भी एल्गोरिदम के प्रत्येक चरण के साथ, पेस्सिमिस्टिक एस्टीमेटर में शुद्ध वृद्धि होती है

जहां N(t)(u) शेष ग्राफ़ में u के निकटतम को दर्शाता है (अर्थात, R(t) में)।.

प्रथम एल्गोरिदम के लिए, शुद्ध वृद्धि गैर-ऋणात्मक है क्योंकि, u की चॉइस से,

,

जहां d(u) मूल ग्राफ़ में u की डिग्री है।

दूसरे एल्गोरिदम के लिए, शुद्ध वृद्धि गैर-ऋणात्मक है क्योंकि, u की चॉइस से,

,

जहां d′(u) शेष ग्राफ़ में u की डिग्री है।

यह भी देखें

  • प्रोबबिलिस्टिक मेथड
  • डेरनडोमाईज़ेसन
  • रेनडोमाइसड राउंडिंग

संदर्भ

  • Spencer, Joel H. (1987), Ten lectures on the probabilistic method, SIAM, ISBN 978-0-89871-325-1


अग्रिम पठन

बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=सशर्त_संभावनाओं_की_विधि&oldid=240419’