संभाव्य विधि

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

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

परिचय

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

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

वैकल्पिक रूप से, संभाव्य विधि का उपयोग प्रारूप समष्टि में एक वांछित तत्व के अस्तित्व का दायित्व देने के लिए भी किया जा सकता है जो गणना किए गए अपेक्षित मान से अधिक या उसके बराबर है क्योंकि ऐसे तत्व की गैर-उपस्थिति में प्रत्येक तत्व का अर्थ प्रारूप समष्टि अपेक्षित मान से कम है यह एक विरोधाभास है।

संभाव्य विधि में उपयोग किए जाने वाले सामान्य उपकरणों में मार्कोव की असमानता, चेरनॉफ़ बाध्य और लोवाज़ स्थानीय लेम्मा सम्मिलित हैं।

एर्डोस के कारण दो उदाहरण

हालांकि इसके पहले के अन्य गणितज्ञों ने संभाव्य विधि के माध्यम से प्रमेयों को सिद्ध किया था उदाहरण के लिए स्ज़ेल के 1943 के परिणाम में हैमिल्टनियन वृत्तों की एक बड़ी संख्या वाले टूर्नामेंट (आरेख सिद्धांत) सम्मिलित हैं इस पद्धति का उपयोग करने वाले कई सबसे प्रसिद्ध प्रमाण एर्डोस के कारण हैं। नीचे दिया गया पहला उदाहरण 1947 के एक ऐसे परिणाम का वर्णन करता है जो रैमसे संख्या R(r, r) के लिए निचली सीमा का प्रमाण देता है।

पहला उदाहरण

मान लीजिए कि हमारे पास n शीर्षों पर एक पूर्ण आरेख है। हम यह दिखाना चाहते हैं कि n के पर्याप्त छोटे मानों के लिए आरेख के शीर्षों को दो रंगों (जैसे लाल और नीला) में रंगना संभव होता है जिससे r शीर्षों पर कोई पूर्ण उपआरेख न हो जो एकवर्णी के समान होता है। ऐसा करने के लिए, हम आरेख़ को अपेक्षाकृत विभिन्न रूप से रंगते हैं और प्रत्येक किनारे को स्वतंत्र रूप से 1/2 लाल होने और 1/2 नीला होने की संभाव्यता के साथ रंगते हैं और हम निम्नानुसार r शीर्षों पर एकवर्णी उपआरेख की अपेक्षित संख्या की गणना करते हैं:

किसी भी समुच्चय के लिए $S_{r}$ का $r$ हमारे आरेख से शीर्ष चर $X(S_{r})$ को परिभाषित करें और माना कि 1 और 0 यदि प्रत्येक किनारे के बीच $r$ शीर्ष मे एक ही रंग है तब ध्यान दें कि एकवर्णी समुच्चय की संख्या $r$-उपआरेख का योग $X(S_{r})$ है सभी संभावित उपसमुच्चय पर $S_{r}$ किसी भी व्यक्तिगत समुच्चय के लिए $S_{r}^{i}$ का अपेक्षित मान $X(S_{r}^{i})$ की केवल संभाव्यता है कि सभी $C(r,2)$ शीर्षों में $S_{r}^{i}$ एक ही रंग हैं:

$E[X(S_{r}^{i})]=2\cdot 2^{-{r \choose 2}}$

गुणक 2 इसीलिए प्राप्त होता है क्योंकि दो संभावित रंग हैं।

यह किसी भी $C(n,r)$ संभावित उपसमुच्चय के लिए सही है जिसे हम चुन सकते थे अर्थात $i$ की दूरी 1 $C(n,r)$ तक है। तो हमारे पास $E[X(S_{r}^{i})]$ कुल $S_{r}^{i}$ का योग है:

$\sum _{i=1}^{C(n,r)}E[X(S_{r}^{i})]={n \choose r}2^{1-{r \choose 2}}.$

अपेक्षित संख्या का योग अपेक्षित मान है यद्यपि चर सांख्यिकीय स्वतंत्र है इसलिए योग की अपेक्षा सभी एकवर्णी $r$-उपआरेख की अपेक्षित संख्या है:

$E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}.$

विचार करें कि क्या होता है यदि यह मान 1 से कम है। चूंकि एकवर्णी r-उपआरेख की अपेक्षित संख्या 1 से कम है इसलिए एक रंग सम्मिलित है जो इस नियम को संतुष्ट करता है कि एकवर्णी r-उपआरेख की संख्या 1 से अपेक्षाकृत से कम है अपेक्षित संख्या इस यादृच्छिक रंग में एकवर्णी r-उपआरेख एक गैर-ऋणात्मक पूर्णांक है। इसलिए यह 0 होना चाहिए क्योकि 0 केवल 1 से कम गैर- ऋणात्मक पूर्णांक है इससे यह पता चलता है कि यदि $E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}<1$ है उदाहरण के लिए n = 5 और r = 4 मे एक रंग सम्मिलिता होना चाहिए जिसमें कोई एकवर्णी r-उपआरेख न हो। रैमसे संख्या की परिभाषा के अनुसार इसका अर्थ यह है कि R(r, r) को n से बड़ा होना चाहिए। विशेष रूप से R(r, r) को r के साथ कम से कम घातीय रूप से विस्तृत होना आवश्यक होता है।

इस तर्क की एक दुर्बलता यह है कि यह पूर्ण रूप से असंवैधानिक है। हालांकि यह सिद्ध करता है कि (1.1)^r शीर्षों पर पूर्ण आरेख के लगभग प्रत्येक रंग में कोई एकवर्णी r-उपआरेख नहीं होता है लेकिन यह इस प्रकार के रंग का कोई स्पष्ट उदाहरण नहीं देता है। इस प्रकार के रंग को खोजने की समस्या 50 से अधिक वर्षों से विवृत है।

दूसरा उदाहरण

---

एर्डोस के 1959 के पेपर (नीचे दिए गए संदर्भ देखें) ने धनात्मक पूर्णांक g और k दिए गए आरेख सिद्धांत में निम्नलिखित समस्या को संबोधित किया कि क्या कोई आरेख G सम्मिलित है जिसमें कम से कम g की लंबाई के वृत्त (आरेख सिद्धांत) सम्मिलित हैं जैसे कि G की रंगीन संख्या कम से कम k है।

यह दिखाया जा सकता है कि ऐसा आरेख किसी भी g और k के लिए सम्मिलित है और प्रमाण अपेक्षाकृत सरल है माना कि n को बहुत बड़ा है और n शीर्षों के एक यादृच्छिक आरेख G पर विचार करें, जहाँ G में प्रत्येक शीर्ष प्रायिकता p = n^1/g −1 के साथ सम्मिलित है। हम दिखाते हैं कि धनात्मक संभाव्यता के साथ G निम्नलिखित दो गुणों को संतुष्ट करता है:

गुण 1. G में g से कम लंबाई के अधिकतम n/2 आरेख सिद्धांत सम्मिलित हैं।

प्रमाण: माना कि X, g से कम लंबाई का संख्या वृत्त है। n शीर्षों पर पूर्ण आरेख में लंबाई i के वृत्तों की संख्या है:

${\frac {n!}{2\cdot i\cdot (n-i)!}}\leq {\frac {n^{i}}{2}}$

और उनमें से प्रत्येक G में प्रायिकता pⁱ के साथ सम्मिलित है। इसलिए मार्कोव की असमानता से हमारे पास है: