संभाव्य विधि

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

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

परिचय

यदि वस्तुओं के संग्रह में प्रत्येक वस्तु में एक निश्चित गुण होने में विफल रहता है तो संभाव्यता है कि संग्रह से चयनित की गई एक यादृच्छिक वस्तु में वह विशेषता शून्य होती है। इसी प्रकार यह दिखाते हुए कि संभाव्यता 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]

Anonymous

Search

संभाव्य विधि

Namespaces

More

Page actions

Contents

परिचय

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

पहला उदाहरण

दूसरा उदाहरण

यह भी देखें

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

संदर्भ

फुटनोट्स

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

संभाव्य विधि

परिचय

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

पहला उदाहरण

दूसरा उदाहरण

यह भी देखें

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

संदर्भ

फुटनोट्स

Navigation

Wiki tools

Page tools

Other projects

Hidden categories