संभाव्य विधि: Difference between revisions

Revision as of 11:36, 10 May 2023

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

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

परिचय

यदि वस्तुओं के संग्रह में प्रत्येक वस्तु में एक निश्चित गुण होने में विफल रहता है तो संभाव्यता है कि संग्रह से चयनित की गई एक यादृच्छिक वस्तु में वह विशेषता शून्य होती है। इसी प्रकार यह दिखाते हुए कि संभाव्यता 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$ -उपआरेख न हो।^{[lower-alpha 1]} रैमसे संख्या की परिभाषा के अनुसार इसका अर्थ यह है कि $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 i$ के साथ सम्मिलित है। इसलिए मार्कोव की असमानता से हमारे पास है:

\Pr \left(X>{\tfrac {n}{2}}\right)\leq {\frac {2}{n}}E[X]\leq {\frac {1}{n}}\sum _{i=3}^{g-1}p^{i}n^{i}={\frac {1}{n}}\sum _{i=3}^{g-1}n^{\frac {i}{g}}\leq {\frac {g}{n}}n^{\frac {g-1}{g}}=gn^{-{\frac {1}{g}}}=o(1).

इस प्रकार पर्याप्त रूप से

n

के लिए गुण 1,

1/2

से अधिक की संभाव्यता के साथ सिद्ध है।

गुण 2.

G

में

\lceil {\tfrac {n}{2k}}\rceil

आकार का कोई स्वतंत्र समुच्चय (आरेख़ सिद्धांत) नहीं है।

प्रमाण: माना कि $Y$ , $G$ में सबसे बड़े स्वतंत्र समुच्चय का आकार है स्पष्ट रूप से हमारे पास है:

\Pr(Y\geq y)\leq {n \choose y}(1-p)^{\frac {y(y-1)}{2}}\leq n^{y}e^{-{\frac {py(y-1)}{2}}}=e^{-{\frac {y}{2}}\cdot (py-2\ln n-p)}=o(1),

जहाँ

y=\left\lceil {\frac {n}{2k}}\right\rceil \!

इस प्रकार पर्याप्त रूप से

n

के लिए, गुण 2,

1/2

से अधिक की संभाव्यता के साथ सिद्ध है।

पर्याप्त रूप से $n$ के लिए संभाव्यता है कि वितरण से एक आरेख में दोनों गुण धनात्मक है क्योंकि इन गुणों के लिए घटनाओं को अलग नहीं किया जा सकता है यदि वे उनकी संभाव्यता 1 से अधिक है। क्योंकि $G$ में ये दो गुण हैं, हम $n /2$ शीर्ष पर एक नया आरेख $G'$ प्राप्त करने के लिए $G$ से अधिकांश $n'\geq n/2$ शीर्ष को हटा सकते हैं जिसमें कम से कम $g$ की लंबाई के वृत्त सम्मिलित हैं। हम देख सकते हैं कि इस नए आरेख में आकार का कोई स्वतंत्र समुच्चय $\left\lceil {\frac {n'}{k}}\right\rceil$ नहीं है $G'$ को केवल कम से कम $k$ स्वतंत्र समुच्चयों में विभाजित किया जा सकता है और इसलिए इसकी वर्णिक संख्या कम से कम $k$ होती है।

यह परिणाम इसका संकेत देता है कि किसी आरेख की रंगीन संख्या की गणना इतनी कठिन क्यों होती है क्योकि यहां तक कि जब आरेख मे कई रंगों की आवश्यकता के लिए कोई स्थानीय कारण (जैसे छोटे वृत्त) नहीं होते हैं तब भी रंगीन संख्या अपेक्षाकृत रूप से बड़ी हो सकती है।

यह भी देखें

अतिरिक्त संसाधन

साहचर्य में संभाव्य विधि के प्रकार, एमआईटी ओपनकोर्सवेयर

संदर्भ

Alon, Noga; Spencer, Joel H. (2000). The probabilistic method (2ed). New York: Wiley-Interscience. ISBN 0-471-37046-0.

Erdős, P. (1959). "Graph theory and probability". Can. J. Math. 11: 34–38. doi:10.4153/CJM-1959-003-9. MR 0102081. S2CID 122784453.
Erdős, P. (1961). "Graph theory and probability, II". Can. J. Math. 13: 346–352. CiteSeerX 10.1.1.210.6669. doi:10.4153/CJM-1961-029-9. MR 0120168. S2CID 15134755.
J. Matoušek, J. Vondrak. The Probabilistic Method. Lecture notes.
Alon, N and Krivelevich, M (2006). Extremal and Probabilistic Combinatorics
Elishakoff I., Probabilistic Methods in the Theory of Structures: Random Strength of Materials, Random Vibration, and Buckling, World Scientific, Singapore, ISBN 978-981-3149-84-7, 2017
Elishakoff I., Lin Y.K. and Zhu L.P. , Probabilistic and Convex Modeling of Acoustically Excited Structures, Elsevier Science Publishers, Amsterdam, 1994, VIII + pp. 296; ISBN 0 444 81624 0

↑
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{n \choose r}2^{{n \choose 2}-{r \choose 2}}$ .
- Hence, if $2{n \choose r}2^{{n \choose 2}-{r \choose 2}}<2^{n \choose 2}\Leftrightarrow {n \choose r}2^{1-{r \choose 2}}<1$ , there must be at least one coloring which is not 'bad' for any subgraph.

फुटनोट्स

श्रेणी: संयोजन विज्ञान श्रेणी:गणितीय प्रमाण श्रेणी:संभाव्य तर्क

[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{n \choose r}2^{{n \choose 2}-{r \choose 2}}$ .

Hence, if $2{n \choose r}2^{{n \choose 2}-{r \choose 2}}<2^{n \choose 2}\Leftrightarrow {n \choose r}2^{1-{r \choose 2}}<1$ , there must be at least one coloring which is not 'bad' for any subgraph.

[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{n \choose r}2^{{n \choose 2}-{r \choose 2}}$ .

[6] Hence, if $2{n \choose r}2^{{n \choose 2}-{r \choose 2}}<2^{n \choose 2}\Leftrightarrow {n \choose r}2^{1-{r \choose 2}}<1$ , there must be at least one coloring which is not 'bad' for any subgraph.

[lower-alpha 1]

@@ Line 1: / Line 1: @@
 {{short description|Nonconstructive method for mathematical proofs}}
-गणित में, '''संभाव्य पद्धति''' एक गैर-रचनात्मक विधि है जो मुख्य रूप से संयोजक में प्रयोग की जाती है और एक निर्धारित प्रकार की [[गणितीय प्रमाण]] के अस्तित्व को सिद्ध करने के लिए पॉल एर्डोस द्वारा अग्रणी है। यह दिखा कर काम करता है कि यदि कोई निर्दिष्ट वर्ग से वस्तुओं को यादृच्छिक रूप से चुनता है, तो [[संभावना]] है कि निर्धारित प्रकार का परिणाम शून्य से अधिक है। यद्यपि प्रमाण संभाव्यता का उपयोग करता है, अंतिम निष्कर्ष बिना किसी संभावित त्रुटि के निश्चित रूप से निर्धारित होता है।
+गणित में, '''संभाव्य विधि''' एक गैर-रचनात्मक विधि है जिसका उपयोग [[गणितीय प्रमाण]] के एक निर्धारित प्रकार के अस्तित्व को सिद्ध करने के लिए मुख्य रूप से साहचर्य में किया जाता है। सामान्यतः पॉल एर्डोस द्वारा इस विधि को प्रस्तुत किया गया था यह विधि कार्य को प्रदर्शित करती है कि यदि कोई निर्दिष्ट वर्ग से वस्तुओं को यादृच्छिक रूप से निर्धारित करता है तब [[संभावना|संभाव्यता]] है कि निर्धारित प्रकार का परिणाम शून्य से अधिक है। यद्यपि प्रमाण संभाव्य विधि का उपयोग करता है तब अंतिम निष्कर्ष के अतिरिक्त किसी संभावित त्रुटि के निश्चित रूप से निर्धारित होता है।
-यह पद्धति अब गणित के अन्य क्षेत्रों जैसे [[संख्या सिद्धांत]], रेखीय बीजगणित और [[वास्तविक विश्लेषण]] के साथ-साथ [[कंप्यूटर विज्ञान]] (जैसे [[यादृच्छिक गोलाई]]) और [[सूचना सिद्धांत]] में प्रयुक्त की गई है।
+यह विधि अब गणित के अन्य क्षेत्रों जैसे [[संख्या सिद्धांत]], रेखीय बीजगणित और [[वास्तविक विश्लेषण]] के साथ-साथ [[कंप्यूटर विज्ञान]] (जैसे [[यादृच्छिक गोलाई]]) और [[सूचना सिद्धांत]] में प्रयुक्त की जाती है।
 == परिचय ==
-यदि वस्तुओं के संग्रह में प्रत्येक वस्तु में एक निश्चित गुण होने में विफल रहता है, तो संभावना है कि संग्रह से चुनी गई एक यादृच्छिक वस्तु में वह संपत्ति शून्य है।
+यदि वस्तुओं के संग्रह में प्रत्येक वस्तु में एक निश्चित गुण होने में विफल रहता है तो संभाव्यता है कि संग्रह से चयनित की गई एक यादृच्छिक वस्तु में वह विशेषता शून्य होती है। इसी प्रकार यह दिखाते हुए कि संभाव्यता 1 से कम है तब किसी वस्तु के अस्तित्व को सिद्ध करने के लिए इसका उपयोग किया जा सकता है जो निर्धारित गुणों को पूर्ण नहीं करती है।
-इसी तरह, यह दिखाते हुए कि संभावना (सख्ती से) 1 से कम है, किसी वस्तु के अस्तित्व को साबित करने के लिए इस्तेमाल किया जा सकता है जो निर्धारित गुणों को पूरा नहीं करता है।
+संभाव्य विधि का उपयोग करने का दूसरा तरीका कुछ यादृच्छिक चर के [[अपेक्षित मूल्य|अपेक्षित मान]] की गणना करना है। यदि यह दिखाया जा सकता है कि यादृच्छिक चर अपेक्षित मान से कम मान ले सकते है तो यह सिद्ध होता है कि यादृच्छिक चर भी अपेक्षित मान से अधिक मान ले सकते है।
-संभाव्यता पद्धति का उपयोग करने का दूसरा तरीका कुछ यादृच्छिक चर के [[अपेक्षित मूल्य]] की गणना करना है। यदि यह दिखाया जा सकता है कि यादृच्छिक चर अपेक्षित मान से कम मान ले सकता है, तो यह साबित करता है कि यादृच्छिक चर भी अपेक्षित मान से अधिक मान ले सकता है।
+वैकल्पिक रूप से, संभाव्य विधि का उपयोग प्रारूप समष्टि में एक वांछित तत्व के अस्तित्व का दायित्व देने के लिए भी किया जा सकता है जो गणना किए गए अपेक्षित मान से अधिक या उसके बराबर है क्योंकि ऐसे तत्व की गैर-उपस्थिति में प्रत्येक तत्व का अर्थ प्रारूप समष्टि अपेक्षित मान से कम है यह एक विरोधाभास है।
-वैकल्पिक रूप से, संभाव्य विधि का उपयोग नमूना स्थान में एक वांछित तत्व के अस्तित्व की गारंटी देने के लिए भी किया जा सकता है, जो गणना किए गए अपेक्षित मूल्य से अधिक या उसके बराबर है, क्योंकि ऐसे तत्व की गैर-मौजूदगी में प्रत्येक तत्व का अर्थ होगा। नमूना स्थान अपेक्षित मान से कम है, यह एक विरोधाभास है।
+संभाव्य विधि में उपयोग किए जाने वाले सामान्य उपकरणों में मार्कोव की असमानता, [[Chernoff बाध्य|चेरनॉफ़ बाध्य]] और लोवाज़ स्थानीय लेम्मा सम्मिलित हैं।
-संभाव्यता पद्धति में उपयोग किए जाने वाले सामान्य उपकरणों में मार्कोव की असमानता, [[Chernoff बाध्य]] और लोवाज़ स्थानीय लेम्मा शामिल हैं।
 == एर्डोस के कारण दो उदाहरण ==
-हालांकि उनके पहले के अन्य लोगों ने संभाव्य पद्धति के माध्यम से प्रमेयों को सिद्ध किया (उदाहरण के लिए, स्ज़ेल के 1943 के परिणाम में [[हैमिल्टनियन चक्र|हैमिल्टनियन]]  चक्रों की एक बड़ी संख्या वाले [[टूर्नामेंट (ग्राफ सिद्धांत)]] मौजूद हैं), इस पद्धति का उपयोग करने वाले कई सबसे प्रसिद्ध प्रमाण एर्डोस के कारण हैं। नीचे दिया गया पहला उदाहरण 1947 के एक ऐसे परिणाम का वर्णन करता है जो रैमसे संख्या {{math|''R''(''r'', ''r'')}} के लिए निचली सीमा का प्रमाण देता है।
+हालांकि इसके पहले के अन्य गणितज्ञों ने संभाव्य विधि के माध्यम से प्रमेयों को सिद्ध किया था उदाहरण के लिए स्ज़ेल के 1943 के परिणाम में [[हैमिल्टनियन चक्र|हैमिल्टनियन]] वृत्तों की एक बड़ी संख्या वाले [[टूर्नामेंट (ग्राफ सिद्धांत)|टूर्नामेंट (आरेख सिद्धांत)]] सम्मिलित हैं इस पद्धति का उपयोग करने वाले कई सबसे प्रसिद्ध प्रमाण एर्डोस के कारण हैं। नीचे दिया गया पहला उदाहरण 1947 के एक ऐसे परिणाम का वर्णन करता है जो रैमसे संख्या {{math|''R''(''r'', ''r'')}} के लिए निचली सीमा का प्रमाण देता है।
 === पहला उदाहरण ===
-मान लीजिए कि हमारे पास {{mvar|n}} शीर्षों पर एक पूर्ण ग्राफ है। हम यह दिखाना चाहते हैं ({{mvar|n}} के पर्याप्त छोटे मानों के लिए) कि ग्राफ के किनारों को दो रंगों (जैसे लाल और नीला) में रंगना संभव है ताकि {{mvar|r}} शीर्षों पर कोई पूर्ण सबग्राफ न हो जो मोनोक्रोमैटिक हो (हर किनारा रंगीन हो) समान रंग) है।
+मान लीजिए कि हमारे पास {{mvar|n}} शीर्षों पर एक पूर्ण आरेख है। हम यह दिखाना चाहते हैं कि {{mvar|n}} के पर्याप्त छोटे मानों के लिए आरेख के शीर्षों को दो रंगों (जैसे लाल और नीला) में रंगना संभव होता है जिससे {{mvar|r}} शीर्षों पर कोई पूर्ण उपआरेख न हो जो एकवर्णी के समान होता है। ऐसा करने के लिए, हम आरेख़ को अपेक्षाकृत विभिन्न रूप से रंगते हैं और प्रत्येक किनारे को स्वतंत्र रूप से {{math|1/2}} लाल होने और {{math|1/2}} नीला होने की संभाव्यता के साथ रंगते हैं और हम निम्नानुसार {{mvar|r}} शीर्षों पर एकवर्णी उपआरेख की अपेक्षित संख्या की गणना करते हैं:
-ऐसा करने के लिए, हम ग्राफ़ को बेतरतीब ढंग से रंगते हैं। प्रत्येक किनारे को स्वतंत्र रूप से {{math|1/2}} लाल होने और {{math|1/2}} नीला होने की संभावना के साथ रंग दें। हम निम्नानुसार {{mvar|r}} शीर्षों पर मोनोक्रोमैटिक सबग्राफ की अपेक्षित संख्या की गणना करते हैं:
-किसी भी सेट के लिए <math>S_r</math> का <math>r</math> हमारे ग्राफ से शिखर, चर को परिभाषित करें <math>X(S_r)</math> होना {{math|1}} अगर हर किनारे के बीच <math>r</math> शिखर एक ही रंग है, और {{math|0}} अन्यथा। ध्यान दें कि मोनोक्रोमैटिक की संख्या <math>r</math>-सबग्राफ का योग है <math>X(S_r)</math> सभी संभावित उपसमुच्चय पर <math>S_r</math>. किसी भी व्यक्तिगत सेट के लिए <math>S_r^i</math>, का अपेक्षित मूल्य <math>X(S_r^i)</math> केवल संभावना है कि सभी <math>C(r, 2)</math> किनारों में <math>S_r^i</math> एक ही रंग हैं:
+किसी भी समुच्चय के लिए <math>S_r</math> का <math>r</math> हमारे आरेख से शीर्ष चर <math>X(S_r)</math> को परिभाषित करें और माना कि {{math|1}} और {{math|0}} यदि प्रत्येक किनारे के बीच <math>r</math> शीर्ष मे एक ही रंग है तब ध्यान दें कि एकवर्णी समुच्चय की संख्या <math>r</math>-उपआरेख का योग <math>X(S_r)</math> है सभी संभावित उपसमुच्चय पर <math>S_r</math> किसी भी व्यक्तिगत समुच्चय के लिए <math>S_r^i</math> का अपेक्षित मान <math>X(S_r^i)</math> की केवल संभाव्यता है कि सभी <math>C(r, 2)</math> शीर्षों में <math>S_r^i</math> एक ही रंग हैं:
 :<math>E[X(S_r^i)] = 2 \cdot 2^{-{r \choose 2}}</math>
-(का कारक {{math|2}} आता है क्योंकि दो संभावित रंग हैं)।
+गुणक {{math|2}} इसीलिए प्राप्त होता है क्योंकि दो संभावित रंग हैं।
-यह किसी के लिए भी सही है <math>C(n, r)</math> संभावित उपसमुच्चय जिन्हें हम चुन सकते थे, अर्थात <math>i</math> से लेकर {{math|1}} को <math>C(n,r)</math>. तो हमारे पास इसका योग है <math>E[X(S_r^i)]</math> कुल मिलाकर <math>S_r^i</math> है
+यह किसी भी <math>C(n, r)</math> संभावित उपसमुच्चय के लिए सही है जिसे हम चुन सकते थे अर्थात <math>i</math> की दूरी 1 <math>C(n,r)</math> तक है। तो हमारे पास <math>E[X(S_r^i)]</math> कुल <math>S_r^i</math> का योग है:
 :<math>\sum_{i=1}^{C(n,r)} E[X(S_r^i)] = {n \choose r}2^{1-{r \choose 2}}.</math>
-अपेक्षाओं का योग योग की अपेक्षा है (भले ही चर [[सांख्यिकीय स्वतंत्रता]]स्वतंत्र हों), इसलिए योग की अपेक्षा (सभी मोनोक्रोमैटिक <math>r</math>-सबग्राफ की अपेक्षित संख्या) है:
+अपेक्षित संख्या का योग अपेक्षित मान है यद्यपि चर [[सांख्यिकीय स्वतंत्रता|सांख्यिकीय स्वतंत्र]] है इसलिए योग की अपेक्षा सभी एकवर्णी <math>r</math>-उपआरेख की अपेक्षित संख्या है:
 :<math>E[X(S_r)] = {n \choose r}2^{1-{r \choose 2}}.</math>
-विचार करें कि क्या होता है यदि यह मान {{math|1}} से कम है। चूंकि मोनोक्रोमैटिक {{mvar|r}}-सबग्राफ की अपेक्षित संख्या {{math|1}} से कम है, इसलिए एक रंग मौजूद है जो इस शर्त को संतुष्ट करता है कि मोनोक्रोमैटिक {{mvar|r}}-सबग्राफ की संख्या {{math|1}} से सख्ती से कम है। की संख्या इस यादृच्छिक रंग में मोनोक्रोमैटिक {{mvar|r}}-सबग्राफ एक गैर-ऋणात्मक [[पूर्णांक]] है, इसलिए यह  {{math|0}} होना चाहिए  ({{math|0}} केवल {{math|1}} से कम गैर-नकारात्मक पूर्णांक है)। इससे पता चलता है कि अगर
+विचार करें कि क्या होता है यदि यह मान {{math|1}} से कम है। चूंकि एकवर्णी {{mvar|r}}-उपआरेख की अपेक्षित संख्या {{math|1}} से कम है इसलिए एक रंग सम्मिलित है जो इस नियम को संतुष्ट करता है कि एकवर्णी {{mvar|r}}-उपआरेख की संख्या {{math|1}} से अपेक्षाकृत से कम है अपेक्षित संख्या इस यादृच्छिक रंग में एकवर्णी {{mvar|r}}-उपआरेख एक गैर-ऋणात्मक [[पूर्णांक]] है। इसलिए यह {{math|0}} होना चाहिए क्योकि {{math|0}} केवल {{math|1}} से कम गैर- ऋणात्मक पूर्णांक है इससे यह पता चलता है कि यदि <math>E[X(S_r)] = {n \choose r}2^{1-{r \choose 2}} < 1</math> है उदाहरण के लिए {{math|''n'' {{=}} 5}} और {{math|''r'' {{=}} 4}} मे एक रंग सम्मिलिता होना चाहिए जिसमें कोई एकवर्णी {{mvar|r}}-उपआरेख न हो।{{efn|
-:<math>E[X(S_r)] = {n \choose r}2^{1-{r \choose 2}} < 1</math>
-(जो रखता है, उदाहरण के लिए, के लिए {{math|''n'' {{=}} 5}} और {{math|''r'' {{=}} 4}}), एक रंग मौजूद होना चाहिए जिसमें कोई मोनोक्रोमैटिक न हो {{mvar|r}}-सबग्राफ।{{efn|
 The same fact can be proved without probability, using a simple counting argument:
 * The total number of ''r''-subgraphs is <math>{n \choose r}</math>.
@@ Line 45: / Line 38: @@
 * Hence, the total number of colorings that are bad for some (at least one) subgraph is at most <math>2 {n \choose r} 2^{{n \choose 2} - {r \choose 2}}</math>.
 * Hence, if <math>2 {n \choose r} 2^{{n \choose 2} - {r \choose 2}} < 2^{n \choose 2} \Leftrightarrow {n \choose r}2^{1-{r \choose 2}} < 1</math>, there must be at least one coloring which is not 'bad' for any subgraph.
-}}
+}} [[रैमसे संख्या]] की परिभाषा के अनुसार इसका अर्थ यह है कि {{math|''R''(''r'', ''r'')}} को {{mvar|n}} से बड़ा होना चाहिए। विशेष रूप से {{math|''R''(''r'', ''r'')}} को {{mvar|r}} के साथ कम से कम [[घातीय वृद्धि|घातीय]] रूप से विस्तृत होना आवश्यक होता है।
-[[रैमसे संख्या]] की परिभाषा के अनुसार, इसका तात्पर्य है कि {{math|''R''(''r'', ''r'')}} से बड़ा होना चाहिए {{mvar|n}}. विशेष रूप से, {{math|''R''(''r'', ''r'')}} के साथ कम से कम [[घातीय वृद्धि]] होनी चाहिए {{mvar|r}}.
-इस तर्क की एक कमजोरी यह है कि यह पूरी तरह से असंवैधानिक है। हालांकि यह साबित करता है (उदाहरण के लिए) कि {{math|(1.1)<sup>''r''</sup>}} शीर्षों पर पूर्ण ग्राफ के लगभग हर रंग में कोई मोनोक्रोमैटिक {{mvar|r}}-सबग्राफ नहीं होता है, यह इस तरह के रंग का कोई स्पष्ट उदाहरण नहीं देता है। इस तरह के रंग को खोजने की समस्या 50 से अधिक वर्षों से खुली हुई है।
+इस तर्क की एक दुर्बलता यह है कि यह पूर्ण रूप से असंवैधानिक है। हालांकि यह सिद्ध करता है कि {{math|(1.1)<sup>''r''</sup>}} शीर्षों पर पूर्ण आरेख के लगभग प्रत्येक रंग में कोई एकवर्णी {{mvar|r}}-उपआरेख नहीं होता है लेकिन यह इस प्रकार के रंग का कोई स्पष्ट उदाहरण नहीं देता है। इस प्रकार के रंग को खोजने की समस्या 50 से अधिक वर्षों से विवृत है।
 === दूसरा उदाहरण ===
-----Erdős के 1959 के पेपर (नीचे उद्धृत संदर्भ देखें) ने [[ग्राफ सिद्धांत]] में निम्नलिखित समस्या को संबोधित किया: दिए गए सकारात्मक पूर्णांक {{mvar|g}} और {{mvar|k}}, क्या कोई ग्राफ मौजूद है {{mvar|G}} कम से कम लंबाई का केवल [[चक्र (ग्राफ सिद्धांत)]] युक्त {{mvar|g}}, जैसे कि [[रंगीन संख्या]] {{mvar|G}} कम से कम है {{mvar|k}}?
+----एर्डोस के 1959 के पेपर (नीचे दिए गए संदर्भ देखें) ने धनात्मक पूर्णांक {{mvar|g}} और {{mvar|k}} दिए गए [[ग्राफ सिद्धांत|आरेख सिद्धांत]] में निम्नलिखित समस्या को संबोधित किया कि क्या कोई आरेख {{mvar|G}} सम्मिलित है जिसमें कम से कम {{mvar|g}} की लंबाई के [[चक्र (ग्राफ सिद्धांत)|वृत्त (आरेख सिद्धांत)]] सम्मिलित हैं जैसे कि {{mvar|G}} की [[रंगीन संख्या]] कम से कम {{mvar|k}} है।
-यह दिखाया जा सकता है कि ऐसा ग्राफ किसी के लिए भी मौजूद है {{mvar|g}} और {{mvar|k}}, और सबूत यथोचित सरल है। होने देना {{mvar|n}} बहुत बड़ा हो और एक यादृच्छिक ग्राफ पर विचार करें {{mvar|G}} पर {{mvar|n}} कोने, जहां हर किनारा अंदर है {{mvar|G}} संभाव्यता के साथ मौजूद है {{math|''p'' {{=}} ''n''<sup>1/''g''&hairsp;−1</sup>}}. हम दिखाते हैं कि सकारात्मक संभावना के साथ, {{mvar|G}} निम्नलिखित दो गुणों को संतुष्ट करता है:
+यह दिखाया जा सकता है कि ऐसा आरेख किसी भी {{mvar|g}} और {{mvar|k}} के लिए सम्मिलित है और प्रमाण अपेक्षाकृत सरल है माना कि {{mvar|n}} को बहुत बड़ा है और {{mvar|n}} शीर्षों के एक यादृच्छिक आरेख {{mvar|G}} पर विचार करें, जहाँ G में प्रत्येक शीर्ष प्रायिकता {{math|''p'' {{=}} ''n''<sup>1/''g''&hairsp;−1</sup>}} के साथ सम्मिलित है। हम दिखाते हैं कि धनात्मक संभाव्यता के साथ {{mvar|G}} निम्नलिखित दो गुणों को संतुष्ट करता है:
-: संपत्ति 1। {{mvar|G}} अधिक से अधिक शामिल हैं {{math|''n''/2}} से कम लंबाई के चक्र {{mvar|g}}.
+: '''गुण 1.''' {{mvar|G}} में {{mvar|g}} से कम लंबाई के अधिकतम {{math|''n''/2}} [[चक्र (ग्राफ सिद्धांत)|आरेख सिद्धांत]] सम्मिलित हैं।
-सबूत। होने देना {{mvar|X}} से कम लंबाई के संख्या चक्र हो {{mvar|g}}. लंबाई के चक्रों की संख्या {{mvar|i}} पूरे ग्राफ में {{mvar|n}} शिखर है
+'''प्रमाण:''' माना कि {{mvar|X}}, {{mvar|g}} से कम लंबाई का संख्या वृत्त है। {{mvar|n}} शीर्षों पर पूर्ण आरेख में लंबाई {{mvar|i}} के वृत्तों की संख्या है:
 :<math>\frac{n!}{2\cdot i \cdot (n-i)!} \le \frac{n^i}{2}</math>
-और उनमें से प्रत्येक में मौजूद है {{mvar|G}} संभाव्यता के साथ {{math|''p<sup>i</sup>''}}. इसलिए मार्कोव की असमानता से हमारे पास है
+और उनमें से प्रत्येक {{mvar|G}} में प्रायिकता {{math|''p<sup>i</sup>''}} के साथ सम्मिलित है। इसलिए मार्कोव की असमानता से हमारे पास है:
 :<math>\Pr \left (X> \tfrac{n}{2} \right )\le \frac{2}{n} E[X] \le \frac{1}{n} \sum_{i=3}^{g-1} p^i n^i = \frac{1}{n} \sum_{i=3}^{g-1} n^{\frac{i}{g}} \le \frac{g}{n} n^{\frac{g-1}{g}} =  gn^{-\frac{1}{g}} = o(1).</math>
-: इस प्रकार पर्याप्त रूप से बड़े के लिए {{mvar|n}}, संपत्ति 1 से अधिक की संभावना के साथ रखती है {{math|1/2}}.
+: इस प्रकार पर्याप्त रूप से {{mvar|n}} के लिए गुण 1, {{math|1/2}} से अधिक की संभाव्यता के साथ सिद्ध है।
+:'''गुण 2.''' {{mvar|G}} में <math>\lceil \tfrac{n}{2k} \rceil</math> आकार का कोई स्वतंत्र समुच्चय (आरेख़ सिद्धांत) नहीं है।
-: संपत्ति 2। {{mvar|G}} में आकार का कोई स्वतंत्र सेट (ग्राफ़ सिद्धांत) नहीं है <math>\lceil \tfrac{n}{2k} \rceil</math>.
-सबूत। होने देना {{mvar|Y}} में सबसे बड़े स्वतंत्र सेट का आकार हो {{mvar|G}}. स्पष्ट रूप से, हमारे पास है
+'''प्रमाण:''' माना कि {{mvar|Y}}, {{mvar|G}} में सबसे बड़े स्वतंत्र समुच्चय का आकार है स्पष्ट रूप से हमारे पास है:
 :<math>\Pr (Y\ge y) \le {n \choose y}(1-p)^{\frac{y(y-1)}{2}} \le n^y e^{-\frac{py(y-1)}{2}} = e^{- \frac{y}{2} \cdot (py -2\ln n - p)} = o(1),</math>
-कब
+जहाँ
-:<math>y = \left \lceil \frac{n}{2k} \right \rceil\!.</math> इस प्रकार, पर्याप्त बड़े के लिए {{mvar|n}}, संपत्ति 2 से अधिक की संभावना के साथ रखती है {{math|1/2}}.
-काफी बड़े के लिए {{mvar|n}}, संभावना है कि वितरण से एक ग्राफ में दोनों गुण हैं, सकारात्मक है, क्योंकि इन गुणों की घटनाओं को अलग नहीं किया जा सकता है (यदि वे थे, तो उनकी संभावनाएं 1 से अधिक हो जाएंगी)।
+:<math>y = \left \lceil \frac{n}{2k} \right \rceil\!</math>
+:इस प्रकार पर्याप्त रूप से {{mvar|n}} के लिए, गुण 2, {{math|1/2}} से अधिक की संभाव्यता के साथ सिद्ध है।
-यहाँ चाल आती है: चूंकि {{mvar|G}} में ये दो गुण हैं, हम अधिक से अधिक निकाल सकते हैं {{math|''n''/2}} शिखर से {{mvar|G}} एक नया ग्राफ प्राप्त करने के लिए {{math|''G′''}} पर <math>n'\geq n/2</math> वे शीर्ष जिनमें कम से कम केवल लंबाई के चक्र हों {{mvar|g}}. हम देख सकते हैं कि इस नए ग्राफ में आकार का कोई स्वतंत्र सेट नहीं है <math>\left \lceil \frac{n'}{k}\right\rceil</math>. {{math|''G′''}} को केवल कम से कम में विभाजित किया जा सकता है {{mvar|k}} स्वतंत्र सेट, और, इसलिए, कम से कम रंगीन संख्या होती है {{mvar|k}}.
+पर्याप्त रूप से {{mvar|n}} के लिए संभाव्यता है कि वितरण से एक आरेख में दोनों गुण धनात्मक है क्योंकि इन गुणों के लिए घटनाओं को अलग नहीं किया जा सकता है यदि वे उनकी संभाव्यता 1 से अधिक है। क्योंकि {{mvar|G}} में ये दो गुण हैं, हम {{math|''n''/2}} शीर्ष पर एक नया आरेख {{math|''G′''}} प्राप्त करने के लिए {{mvar|G}} से अधिकांश <math>n'\geq n/2</math> शीर्ष को हटा सकते हैं जिसमें कम से कम {{mvar|g}} की लंबाई के वृत्त सम्मिलित हैं। हम देख सकते हैं कि इस नए आरेख में आकार का कोई स्वतंत्र समुच्चय <math>\left \lceil \frac{n'}{k}\right\rceil</math> नहीं है {{math|''G′''}} को केवल कम से कम {{mvar|k}} स्वतंत्र समुच्चयों में विभाजित किया जा सकता है और इसलिए इसकी वर्णिक संख्या कम से कम {{mvar|k}} होती है।
-यह परिणाम इस बात का संकेत देता है कि किसी ग्राफ की रंगीन संख्या की गणना इतनी कठिन क्यों है: यहां तक कि जब ग्राफ के लिए कई रंगों की आवश्यकता के लिए कोई स्थानीय कारण (जैसे छोटे चक्र) नहीं होते हैं, तब भी रंगीन संख्या मनमाने ढंग से बड़ी हो सकती है।
+यह परिणाम इसका संकेत देता है कि किसी आरेख की रंगीन संख्या की गणना इतनी कठिन क्यों होती है क्योकि यहां तक कि जब आरेख मे कई रंगों की आवश्यकता के लिए कोई स्थानीय कारण (जैसे छोटे वृत्त) नहीं होते हैं तब भी रंगीन संख्या अपेक्षाकृत रूप से बड़ी हो सकती है।
 == यह भी देखें ==
@@ Line 87: / Line 76: @@
 * [[सशर्त संभावनाओं की विधि|सशर्त संभाव्यता विधि]]
 *गैर-संभाव्यता प्रमेय के संभाव्य प्रमाण
-* [[ यादृच्छिक ग्राफ | यादृच्छिक आरेख]]
+* [[ यादृच्छिक ग्राफ |यादृच्छिक आरेख]]
 == अतिरिक्त संसाधन ==
-* [https://ocw.mit.edu/courses/18-226-probabilistic-method-in-combinatorics-fall-2020/ कॉम्बिनेटरिक्स में संभाव्य तरीके], MIT OpenCourseWare
+* [https://ocw.mit.edu/courses/18-226-probabilistic-method-in-combinatorics-fall-2020/ साहचर्य में संभाव्य विधि के प्रकार], एमआईटी ओपनकोर्सवेयर
 ==संदर्भ==
-* {{notelist}}Alon, Noga; Spencer, Joel H. (2000).  ''The probabilistic method'' (2ed).  New York: Wiley-Interscience.  {{isbn|0-471-37046-0}}.
+Alon, Noga; Spencer, Joel H. (2000). ''The probabilistic method'' (2ed). New York: Wiley-Interscience. {{isbn|0-471-37046-0}}.
 * {{cite journal |doi=10.4153/CJM-1959-003-9 |author=Erdős, P. |year=1959 |title=Graph theory and probability |journal=Can. J. Math. |volume=11 |pages=34–38 |mr=0102081 |s2cid=122784453 |doi-access=free }}
 * {{cite journal |doi=10.4153/CJM-1961-029-9 |author=Erdős, P. |year=1961 |title=Graph theory and probability, II |journal=Can. J. Math. |volume=13 |pages=346–352 |mr=0120168 |url=https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/graph-theory-and-probability-ii/38F46DC839201178C2EEC2B14B1647BC|citeseerx=10.1.1.210.6669 |s2cid=15134755 }}
@@ Line 100: / Line 89: @@
 * Alon, N and Krivelevich, M (2006). [http://www.math.tau.ac.il/~nogaa/PDFS/epc7.pdf Extremal and Probabilistic Combinatorics]
 * Elishakoff I., Probabilistic Methods in the Theory of Structures: Random Strength of Materials, Random Vibration, and Buckling, World Scientific, Singapore, {{ISBN|978-981-3149-84-7}}, 2017
-* Elishakoff I., Lin Y.K. and Zhu L.P. , Probabilistic and Convex Modeling of Acoustically Excited Structures, Elsevier Science Publishers, Amsterdam, 1994, VIII + pp. 296; {{ISBN|0 444 81624 0}}
+* Elishakoff I., Lin Y.K. and Zhu L.P. , Probabilistic and Convex Modeling of Acoustically Excited Structures, Elsevier Science Publishers, Amsterdam, 1994, VIII + pp. 296; {{ISBN|0 444 81624 0}}<br />
+* {{notelist}}
 == फुटनोट्स ==
 <references/>

Anonymous

Search

संभाव्य विधि: Difference between revisions

Namespaces

More

Page actions

Revision as of 11:36, 10 May 2023

Contents

परिचय

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

पहला उदाहरण

दूसरा उदाहरण

यह भी देखें

अतिरिक्त संसाधन

संदर्भ

फुटनोट्स

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

संभाव्य विधि: Difference between revisions

Revision as of 11:36, 10 May 2023

परिचय

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

पहला उदाहरण

दूसरा उदाहरण

यह भी देखें

अतिरिक्त संसाधन

संदर्भ

फुटनोट्स

Navigation

Wiki tools

Page tools

Other projects

Hidden categories