संभाव्य विधि

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

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

परिचय

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

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

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

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

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

== Erdős == के कारण दो उदाहरण हालांकि उनके पहले के अन्य लोगों ने संभाव्य पद्धति के माध्यम से प्रमेयों को सिद्ध किया (उदाहरण के लिए, स्ज़ेल के 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$ -सबग्राफ।^{[lower-alpha 1]}

रैमसे संख्या की परिभाषा के अनुसार, इसका तात्पर्य है कि $R (r, r)$ से बड़ा होना चाहिए $n$ . विशेष रूप से, $R (r, r)$ के साथ कम से कम घातीय वृद्धि होनी चाहिए $r$ .

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

↑
The same fact can be proved without probability, using a simple counting argument:
- The total number of r-subgraphs is ${n \choose r}$ .
- Each r-subgraphs has ${r \choose 2}$ edges and thus can be colored in $2^{r \choose 2}$ different ways.
- Of these colorings, only 2 colorings are 'bad' for that subgraph (the colorings in which all vertices are red or all vertices are blue).
- Hence, the total number of colorings that are bad for some (at least one) subgraph is at most $2 StartBinomialOrMatrix n Choose r EndBinomialOrMatrix 2 Superscript StartBinomialOrMatrix n Choose 2 EndBinomialOrMatrix minus StartBinomialOrMatrix r Choose 2 EndBinomialOrMatrix$

[1] The same fact can be proved without probability, using a simple counting argument:
The total number of r-subgraphs is ${n \choose r}$ .

Each r-subgraphs has ${r \choose 2}$ edges and thus can be colored in $2^{r \choose 2}$ different ways.

Of these colorings, only 2 colorings are 'bad' for that subgraph (the colorings in which all vertices are red or all vertices are blue).

Hence, the total number of colorings that are bad for some (at least one) subgraph is at most $2 StartBinomialOrMatrix n Choose r EndBinomialOrMatrix 2 Superscript StartBinomialOrMatrix n Choose 2 EndBinomialOrMatrix minus StartBinomialOrMatrix r Choose 2 EndBinomialOrMatrix$

[2] The total number of r-subgraphs is ${n \choose r}$ .

[3] Each r-subgraphs has ${r \choose 2}$ edges and thus can be colored in $2^{r \choose 2}$ different ways.

[4] Of these colorings, only 2 colorings are 'bad' for that subgraph (the colorings in which all vertices are red or all vertices are blue).

[5] Hence, the total number of colorings that are bad for some (at least one) subgraph is at most $2 StartBinomialOrMatrix n Choose r EndBinomialOrMatrix 2 Superscript StartBinomialOrMatrix n Choose 2 EndBinomialOrMatrix minus StartBinomialOrMatrix r Choose 2 EndBinomialOrMatrix$

[lower-alpha 1]

Anonymous

Search

संभाव्य विधि

Namespaces

More

Page actions

Contents

परिचय

पहला उदाहरण