संभाव्य विधि

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

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

परिचय

यदि वस्तुओं के संग्रह में प्रत्येक वस्तु में एक निश्चित गुण होने में विफल रहता है, तो संभावना है कि संग्रह से चुनी गई एक यादृच्छिक वस्तु में वह संपत्ति शून्य है।

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

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

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

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

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

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

पहला उदाहरण

मान लीजिए कि हमारे पास n शीर्षों पर एक पूर्ण ग्राफ है। हम यह दिखाना चाहते हैं (n के पर्याप्त छोटे मानों के लिए) कि ग्राफ के किनारों को दो रंगों (जैसे लाल और नीला) में रंगना संभव है ताकि r शीर्षों पर कोई पूर्ण सबग्राफ न हो जो मोनोक्रोमैटिक हो (हर किनारा रंगीन हो) समान रंग) है।

ऐसा करने के लिए, हम ग्राफ़ को बेतरतीब ढंग से रंगते हैं। प्रत्येक किनारे को स्वतंत्र रूप से 1/2 लाल होने और 1/2 नीला होने की संभावना के साथ रंग दें। हम निम्नानुसार r शीर्षों पर मोनोक्रोमैटिक सबग्राफ की अपेक्षित संख्या की गणना करते हैं:

किसी भी सेट के लिए $S_{r}$ का $r$ हमारे ग्राफ से शिखर, चर को परिभाषित करें $X(S_{r})$ होना 1 अगर हर किनारे के बीच $r$ शिखर एक ही रंग है, और 0 अन्यथा। ध्यान दें कि मोनोक्रोमैटिक की संख्या $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 से अधिक वर्षों से खुली हुई है।

दूसरा उदाहरण

---

Erdős के 1959 के पेपर (नीचे उद्धृत संदर्भ देखें) ने ग्राफ सिद्धांत में निम्नलिखित समस्या को संबोधित किया: दिए गए सकारात्मक पूर्णांक g और k, क्या कोई ग्राफ मौजूद है G कम से कम लंबाई का केवल चक्र (ग्राफ सिद्धांत) युक्त g, जैसे कि रंगीन संख्या G कम से कम है k?

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

संपत्ति 1। G अधिक से अधिक शामिल हैं n/2 से कम लंबाई के चक्र g.

सबूत। होने देना X से कम लंबाई के संख्या चक्र हो g. लंबाई के चक्रों की संख्या i पूरे ग्राफ में n शिखर है

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

और उनमें से प्रत्येक में मौजूद है G संभाव्यता के साथ pⁱ. इसलिए मार्कोव की असमानता से हमारे पास है